T -vágások. Balog Dóra. Jüttner Alpár. Matematika BSc szakdolgozat. Témavezet : Operációkutatási Tanszék. Eötvös Loránd Tudományegyetem

T -vágások

és

T -kötések

pakolása

Matematika BSc szakdolgozat

Balog Dóra Témavezet®:

Jüttner Alpár Operációkutatási Tanszék

Eötvös Loránd Tudományegyetem Természettudományi Kar 2016

Köszönetnyilvánítás

Szeretnék köszönetet mondani témavezet®mnek, Jüttner Alpárnak a téma kiválasztásában, a szakirodalom összegy¶jtésében és feldolgozásában nyújtott segítségéért, valamint a szakdolgozat elkészítéséhez adott hasznos tanácsokért.

2

Tartalomjegyzék

1. Bevezetés

5

2. T -kötések, T -vágások

6

3. A feladatok poliéderes felírása

8

3.1. A teljes párosítás poliéder . . . . . . . . . . . . . . . . . . . . . . . .

9

3.2. A minimális T -kötés feladat . . . . . . . . . . . . . . . . . . . . . . . 10 3.3. Blokkoló poliéderpárok és a minimális T -vágás feladat . . . . . . . . . 10

4. Minimális súlyú T -kötések és maximális T -vágás pakolás

11

4.1. Teljes párosítások maximalitása és az Edmonds lemma . . . . . . . . 12 4.2. Az Edmonds algoritmus . . . . . . . . . . . . . . . . . . . . . . . . . 13 4.3. Az algoritmus súlyozott esetben . . . . . . . . . . . . . . . . . . . . . 14 4.4. Egy algoritmus minimális T -kötések és a maximális T -vágás pakolás megkereséséhez . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

5. Minimális súlyú T -vágás keresése

18

5.1. A Padberg-Rao algoritmus . . . . . . . . . . . . . . . . . . . . . . . . 18 5.2. Az algoritmus futása egyszer¶bben a Gomory-Hu fa felhasználásával . 19

6. Maximális súlyú T -kötés pakolás meghatározása 6.1. Adott tulajdonságú T -kötés keresése

20

. . . . . . . . . . . . . . . . . . 21

6.2. Egy T -kötéshez tartozó αU érték kiszámítása . . . . . . . . . . . . . . 23

3

6.3. Lamináris halmazrendszer b®vítése a halmazok feszességének megtartásásval . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 6.4. Az algoritmus lépései az el®z® fejezetek felhasználásával . . . . . . . . 25

7. A minimális T -kötés és a minimális T -vágás keresés algoritmusának programozása 26 Hivatkozások

30

Függelék

31

4

1. Bevezetés

A szakdolgozatban szeretném összefoglalni a gráfokon értelmezett T -kötések és T vágások fontosabb tulajdonságait, továbbá az ezekhez kapcsolódó, gyakorlatban is használható algoritmusokat. A T -kötések, T -vágások denícióját, tulajdonságait, és a közöttük fennálló egyszer¶bb összefüggéseket a 2. fejezetben ismertetem. A 3. fejezetben bemutatom a teljes párosítás, a minimális T -vágás és duálisának poliéderét, illetve a maximális T -vágás pakolás és duálisának poliéderét. A 4. fejezetben az alábbi három ismert probléma és azok T -kötések, illetve T -vágások segítségével történ® megoldása szerepel. A kínai postás:

A G(V, E) gráfon adott c : E → R súlyfüggvény mellett keressük

az élek c szerinti legrövidebb bejárását, ha a kezd®- és végpont azonos (adott pont). Másképp felírva olyan minimális súlyú élhalmazt keresünk G-ben, amit megduplázva Euler-gráfot kapunk. Útkeresés konzervatív gráfon:

Adott G(V, E) gráf és ezen egy konzervatív c : E →

R súlyfüggvény. Az s, t ∈ V pontok között keressünk minimális súlyú s−t utat. Euler-részgráf:

A feladat a G(V, E) gráfban megkeresni a legnagyobb súlyú Euler-

részgráfot, azaz egy olyan G0 (V 0 , E 0 ) gráfot, amelyre V 0 ⊆ V, E 0 ⊆ E és minden pont foka páros. Az 5. és a 6. fejezetekben a Padberg-Rao minimális vágáskeres® és a Barahona által leírt, maximális T -kötés pakolás megoldására használt algoritmusokat ismertetem. A 7. fejezetben a minimális T -kötés és a minimális T -vágás keresésére a LEMON programcsomag segítségével megírt programkódomat mutatom be.

5

2.

T -kötések, T -vágások

Ennek a fejezetnek a célja kés®bbiekben használt deníciók, fogalmak, egyszer¶bb tulajdonságok és jelölések bevezetése. A T -kötések témakörében az ehhez kapcsolódó tulajdonságok miatt sokszor használt m¶velet a szimmetrikus dierencia. Ezért jelölje az A, B halmazokra a szimmetrikus dierenciát A ⊗ B = (A \ B) ∪ (B \ A).

2.1. Deníció. A, B

halmazok laminárisak, ha diszjunktak vagy A ⊆ B vagy

B ⊆ A.

2.2. Deníció. Az A, B halmazokra azt mondjuk, hogy keresztez®k, ha A\B , B \A és A ∩ B egyike sem üres. Fontos megjegyezni, hogy a keresztez® és metsz® fogalmak itt nem azonosak, mert ahhoz, hogy két halmazt metsz®nek nevezzünk elég, ha A ∩ B nem üres. Tehát a 2.2. denícióban a keresztez® halmazok fogalma megegyezik azzal, hogy a halmazok nem laminárisak.

2.3. Deníció. G(V, E)

gráfon, s, t ∈ V pontokra egy S ⊂ V ponthalmazt s − t

vágásnak nevezünk, ha s ∈ S és t ∈ / S . A vágás élei a V \ S és S között haladó élek, ezek hamazát δ(S)-sel jelöljük.

Jelölés.

Egy adott v ∈ V és J ⊆ E esetén dJ (v)-vel jelöljük a v csúcshoz tartozó,

J -beli élek számát. Továbbá legyen x ∈ {0, 1}E esetén dx (v) a v csúcshoz tartozó azon élek száma, amelyek súlya x-ben nem 0. A jelölést ugyanígy értelmezzük egy v pont helyett Z halmazra is, vagyis dJ (Z) =

|{e ∈ δ(Z) : e ∈ J}| és dx (Z) = |{e ∈ δ(Z) : x(e) = 1}| értékeket értünk alatta.

2.4. Deníció.

Adott x ∈ RV esetén egy Z ⊆ V halmazt x-pontosnak nevezünk,

ha |Z| páratlan és dx (Z) = 1. Ha a Z halmaz x-pontos, akkor a komplementere is x-pontos, ha páratlan. A szakdolgozat témáját alkotó fogalmak deníciója:

2.5. Deníció.

Adott T ⊆ V páros sok csúcsot tartalmazó halmaz. Ekkor V ⊂ S

vágás T -vágás, ha |S ∩ T | páratlan. 6

2.6. Deníció.

Adott T ⊆ V páros sok csúcsot tartalmazó halmaz. J ⊆ E halmaz

T -kötés, ha dJ (v) pontosan akkor páratlan, ha v ∈ T . Mivel a vágás- és kötéskeres® algoritmusokat súlyozott gráfon vizsgáljuk, fontos lesz egy-egy vágás kapacitása. Ezt az alábbi módon deniáljuk.

2.7. Deníció. S ⊆ V tása θ(S) =

P

e∈δ(S)

és c : E → R kapacitásfüggvény esetén a δ(S) vágás kapaci-

c(e).

Halmazokon értelmezett függvények egy fontos tulajdonsága a szubmodularitás. Ezt szeretnénk a kapacitásfüggvénynél is kihasználni. A θ függvény szubmodularitása azt jelentené, hogy ∀A, B ⊆ V -re θ(A ∪ B) + θ(A ∩ B) ≤ θ(A) + θ(B). Ez könnyen látható, hiszen az A és B halmazokból kilép® éleket másképpen felírva: a két halmaz uniójából, metszetéb®l kilép® élek valamint az A\B és B \A halmazok között haladó élek  ezt jelölje β(A, B)  kétszer számolva. Mivel β(A, B) ≥ 0 a kapacitásfüggvény nemnegativitása miatt, így ezt elhagyva éppen a fenti képletet kapjuk.

2.8. Deníció. Adott c kapacitásfüggvényre és U ⊆ E -re legyen µ(U ) = min{c(e) : e ∈ U } a [6] cikkben angolul "bottleneck " kapacitásnak nevezett függvény. A T -kötések tulajdonságait sokszor használjuk a kés®bbiekben. Ezek közül a fontosabbak szerepelnek ezen fejezet további részében az [5] jegyzet szerint.

2.9. Tétel. J ⊆ T halmaz T -kötés akkor és csak akkor, ha el®áll élidegen körök és |T /2| darab T -beli végpontú élidegen és végpontjaiban különböz® út egyesítéseként.

Bizonyítás.

Ha a J élhalmaz a fenti részekb®l áll, akkor a fokszámok paritása miatt

(csak a J beli élekre nézve) épp a T -beli pontok lesznek páratlan fokszámúak, azaz

J T -kötés. Ha J T -kötés (azaz a T -beli pontok fokszáma páratlan J -ben), akkor a gráfot egészítsük ki egy új S0 ponttal és S = {st : t ∈ T } élhalmazzal. A J ∪ S Euler-gráf, tehát felbomlik élidegen körök uniójára. Ha ezekb®l elhagyom S éleit (néhány körb®l legalább egy kett® hosszú utat), akkor a körökön kívül T -végpontú utakat kapok, épp |T |/2 darabot.



A következ® tételt a [6] által leírt algoritmusban használjuk, ahol szükséges az a tulajdonság, hogy egy T -kötés és egy T -vágás élhalmazának metszete legalább egy (azaz nem üres). Ezt fogalmazzuk meg másképpen a következ® tételben. 7

2.10. Tétel. Legyen J ⊆ E T -kötés és S egy vágás. Ekkor |J ∩ δ(S)| akkor és csak akkor páratlan, ha δ(S) T -vágás.

Bizonyítás.

Ha δ(S) T -vágás, akkor a T -kötés deníciója miatt |S ∩ T | páratlan,

ezért

X

dJ (v) = 2 · |E(S) ∩ J| + |J ∩ δ(S)|

v∈S

egyenletben a bal oldal páratlan. Ebb®l következik, hogy |J ∩ δ(S)| páratlan, illetve a másik irányban fordítva is megkapjuk az állítást.



2.11. Tétel. Ha T1 , T2 ⊆ V páros elemszámú halmazok, és J1 T1 -kötés, J2 T2 -kötés, akkor J1 ⊗ J2 pedig T1 ⊗ T2 -kötés lesz.

Bizonyítás. T1 ∩ T2 -ben a pontok fokszáma J1 -re illetve J2 -re nézve páratlan volt, ezeket összeadjuk vagy kivonjuk, tehát J1 ⊗ J2 -re nézve páros lesz. A T1 \ T2 -ben és

T2 \ T1 -ben található pontok fokszáma hasonlóan páratlan lesz J1 ⊗ J2 -re nézve és éppen ezek alkotják T1 ⊗T2 -t. Az összes többi ponton pedig két páros fokszám összege vagy különbsége szerepel a szimmetrikus dierenciára, azaz a T1 ⊗T2 pontokon kívül is teljesül a T -kötés deníciója. Tehát a páratlan J1 ⊗ J2 -fokszámú pontok épp az új

T -halmaz pontjai.



Az el®z® tételhez hasonlóan láthatjuk, hogy ha J1 , J2 T -kötés és C ciklus, akkor

J1 ⊗ J2 ciklust, J1 ⊗ C pedig T -kötést alkot.

3. A feladatok poliéderes felírása

A T -vágásokhoz kapcsolódó feladatok megoldása szorosan összefügg azok duálisával. Ezért mindenképpen érdemes felírni a szóba jöhet® minimum- és maximumfeladatok poliéderes alakját is.

8

3.1. A teljes párosítás poliéder

Deniáljuk el®ször a

     

  x ∈ RE     x≥0 0 P =  dx (v) = 1 ∀v ∈ V     dx (Z) ≥ 1 ∀Z : |Z| ≥ 3

    

poliédert.

3.1. Tétel.

[3] P 0 poliéder megyegyezik a teljes párosítások vektorainak konvex bur-

kával.

3.2. Lemma.

[3] Ha Z1 és Z2 olyan x-pontos halmazok (ahol x ∈ P 0 ), amikre

|Z1 ∩ Z2 | páratlan, akkor Z1 ∩ Z2 és Z1 ∪ Z2 pontosak, valamint d(Z, Z 0 ) = 0

3.3. Tétel.

[3] P 0 -ben minden e ∈ E élhez létezik egy e-t tartalmazó feszes teljes

párosítás, azaz dpárosítás (Z) = 1 minden Z x-pontos halmazra. Ez azt jelenti, hogy biztosan van egy M teljes párosítás, ami feszes. Ennek a tulajdonságnak és a 3.3. tételnek a felhasználásával bizonyítható a 3.1. tétel. A minimális súlyú teljes párosítás megtalálásához a feladatot felírhatjuk a következ®képpen:

     

     

min cx x≥0

 dx (v) = 1 ∀v ∈ V     dx (Z) ≥ 1 ∀Z : |Z| ≥ 3

.

(1)

    

A feladat duálisa a dualitás-tétel (és az [1]-ben tanultak) miatt:   X   max y(Z)         Z : |Z| plan   y(Z) ≥ 0 ∀Z : |Z| > 1 .   X       y(Z) ≤ c(e) ∀e ∈ E    

(2)

Z : e∈δ(Z)

A 4.2. fejezetben bemutatott Edmonds algoritmus ezt a feladatot oldja meg, a súlyozott változatban a primál- és duál problémákat egyszerre kezelve. 9

3.2. A minimális

T -kötés

feladat

A feladat a G(V, E) gráfon minimális súlyú T -kötést keresni. Ha az LP feladatot szeretnénk megoldani, tehát nem egészérték¶ megoldást keresünk, a feladatot a következ®képpen írhatjuk fel. Készítsük el az A1 mátrixot, amiben az oszlopok jelölik a gráf éleit, a sorokban pedig a T -vágások incidencia-vektorai vannak. A következ® poliéder T -vágások egy optimális pakolását adja:       max y · 1  

(3)

y · A1 ≤ w

  

y≥0

  

A feladatra Edmonds és Johnson a [9] cikke szerint igaz, hogy a duálisának, azaz a (4) feladatnak a megoldása épp a minimális T -kötést adja meg. A dualitástétel miatt tudjuk, hogy az optimális megoldások egyenl®ek, azaz a minimális T -kötés értéke megyegyezik a maximális T -vágás pakolással.     min w · x    

(4)

A1 · x ≥ 1

  

x≥0

  

3.3. Blokkoló poliéderpárok és a minimális

T -vágás

feladat

A [4] állításait felhasználva szeretnénk meghatározni a minimális T -vágás keresés feladatát. Legyen A egy m × n-es nemnegatív mátrix, és jelölje β az (5) poliédert. ( ) A1 · x ≥ 1 (5) x≥0 Az A mátrix egy ai sora dominálja a többi sor valamely konvex kombinációját, ha P az ai ≥ m j=1 cj aj egyenl®tlenség teljesül, ahol a jobb oldal az aj sorok egy konvex kombinációja. Tehát vannak olyan, a fenti állítást teljesít® c1 , . . . cm ≥ 0 konstansok, Pm amikre ci = 0 és j=1 cj = 1. Nevezzük az A mátrix ai sorát szükségesnek, ha egyik konvex kombinációt sem dominálja. Az A mátrix valódi, ha minden sora szükséges, vagy A = [0 . . . 0] sormátrix, esetleg az üres mátrix.

10

Az (5) poliédert másképpen is felírhatjuk β = {b ∈ Rn+ | A · b ≥ 1} alakban, ahol legyenek β extrémpontjai b1 , . . . br . Ekkor a βˆ = {a ∈ Rn+ | a · β ≥ 1} poliéder a

β -nak blokkolója. A [4] cikk alapján az alábbiakban ismertetett 3.4. tételt felhasználva és a 3.2. fejezetben leírtak alapján adhatjuk meg a minimális T -vágás feladat poliéderes felírását. Ez a tétel deniálja a poliéder és blokkolója közti kapcsolatot.

3.4. Tétel. Legyen A m × n-es valódi mátrix, a sorait jelöljük a1 , . . . am -mel. Legyen β a fent deniált poliéder, b1 , . . . br extrémpontokkal. Jelölje B azt a mátrixot, aminek

a sorai b1 . . . br vektorok, és legyen α = {a ∈ Rn+ | B · a ≥ 1}. Ekkor a következ®k mindegyike teljesül: (1) βˆ = α (2) B valódi és az α extrémpontjai éppen az a1 , . . . am vektorok (3) αˆ = β . Alkalmazzuk a 3.4. tételben leírt tulajdonságokat a (4) feladatra. Deniáljuk úgy az A2 mátrixot, hogy az oszlopai az éleket jelölik és a sorai T -kötések incidenciavektorai. Ekkor a következ® feladatpár éppen a (4) feladat poliéderének blokkolója, és ebb®l a minimális T -vágás keresés LP feladata:        min c · x 

(6)

A2 · x ≥ 1

  

x≥0

  

Ennek duálisa a (7) poliéder, ami éppen a maximális T -kötés pakolást adja optimális megoldásnak.

    max y · 1

   

  

  

y · A2 ≤ c

4. Minimális súlyú

y≥0

T -kötések

és maximális

(7)

T -vágás

pakolás

A (4) LP feladat megoldásához az Edmondsról elnevezett algoritmus súlyozott változatát kell felhasználni. A következ® fejezetekben el®ször az algoritmus súlyozatlan változata szerepel, majd ennek segítségével lehet felírni a súlyozott esetet. 11

4.1. Teljes párosítások maximalitása és az Edmonds lemma

A [8] jegyzetben szerepelnek az alábbi deníciók, állítások, és a következ® 4.2. részben ismertetett Edmonds algorimus. A nem páros gráfokban a maximális párosítás méretét a 4.1. formula adja meg. Tehát ha létezik olyan párosítás és X halmaz, amire a formula jobb oldala minimális, akkor ez biztosan optimális megoldás, tehát tudjuk, hogy az algoritmus ekkor véget ér.

4.1. Tétel (Berge-Tutte). M pontosan akkor maximális párosítás G-ben, ha |M | = min X⊂V

|V | − (cplan (G − X) − |X|) . 2

Egy X ⊂ V halmazra a Berge-Tutte formula pontosan akkor veszi fel a minimumát, ha M maximális párosítás esetén a következ® három tulajdonság teljesül: (a) a gráfnak X elhagyásával keletkez® bármely komponensét maximum 1 pont kivételével fedi az M ebbe a komponensbe es® része, (b) X nem tartalmaz M -beli élet, (c) M fedi az X halmaz minden pontját. Az algoritmus olyan páratlan halmazok összehúzásával csökkenti a gráf méretét, amiket nagyjából lefedtünk a párosítással. Fontos, hogy ezek megtartják a párosítás maximalitására vonatkozó tulajdonságukat.

4.2. Deníció. A G gráfon M párosítást növel® útnak nevezünk egy olyan alternáló utat, amelynek mindkét végpontja szabad, azaz nem fedi M -beli párosítás-él. Tudjuk, hogy G gráfon egy párosítás pontosan akkor maximális, ha nem létezik hozzá növel® út.

4.3. Deníció. G

gráfban egy K páratlan hosszú kört kehelynek nevezünk, ha

létezik olyan M maximális párosítás, ami a k ∈ K pontot nem fedi, viszont k -ból indulva a K minden második éle párosítás-él. Ekkor a k pontot a kehely bázisának nevezzük. 12

4.4. Lemma

(Edmonds). Ha K kehely és M egy rá illeszked® maximális párosí-

tás G-ben, akkor a K összehúzásával keletkez® gráfban M 0 = M − K párosítás is maximális.

Bizonyítás.

Tegyük fel indirekten, hogy K kehely, M maximális párosítás, de M 0

párosítás nem maximális. Ekkor létezik egy P 0 út, ami mentén alternálva M 0 növelhet®. Ha P 0 nem tartalmazná a K összehúzott pontot, akkor P 0 növel® út lenne

M -ben is, ami ellentmondás. Tehát P 0 tartalmazza az összehúzott K -t, ám ekkor ez mindenképp az út egyik végpontja. Jelöljük az eredeti gráfban az út megfelel®jének végpontját z -vel, valamint tudjuk, hogy z ∈ K . Jelölje a kehely deníciójában szerepl® k és a z pont közti utak közül P 00 azt, aminek z -b®l induló éle M -beli. Ezekkel a jelölésekkel P 0 és P 00 összef¶zve növel® út lenne az eredeti gráfban. Ezzel itt is ellentmondást kapunk, tehát M 0 maximális.



A párosítást növel® út keresése csak bizonyos pontokon történik. Ehhez felépítünk egy alternáló erd®t, ez biztosítja, hogy az algoritmus végén megjelölt X halmaz megfeleljen a Berge-Tutte formula után megadott (a), (b), (c) feltételeknek. Ehhez szükséges az alternáló erd® deníciója egy adott M párosításra nézve.

4.5. Deníció.

Egy F erd® alternáló, ha a következ®k fennállnak:

• minden komponense pontosan egy szabad (M által nem fedett) pontot tartalmaz, és ez a fa gyökere,

• bármely pontjából a gyökérbe vezet® út alternáló, • ha uv ∈ M és v ∈ F ⇒ u ∈ F . A bels® pontok az egyes fák gyökerét®l páratlan, a küls® pontok a páros távolságra lév® pontok halmaza (a gyökér kivételével).

4.2. Az Edmonds algoritmus

input G(V, E) gráf, M

tetsz®leges párosítás

13

output M maximális párosítás és X ⊆ V

ponthalmaz, amire a Berge-Tutte formula

jobb oldala minimális Legyen S a szabad pontok halmaza. Legyen F a szabad pontokból álló M -altenáló erd®, azaz a szabad pontokat, mint egypontú fákat tartalmazó erd®. Jelölje µ(v) a v ∈

V \S pontnak az M párosítás által meghatározott szomszédját, a v ∈ S pontokra µ(v) = v . Az algoritmus által módosított gráfot jelöljük a kés®bbi lépésekben G0 -vel. Ekkor a következ® négy eset lehetséges, ezeket ismételjük a gráfon, amíg a 4. lépéshez nem jutunk: 1. Ha az F -nek léteznek u és v nem egy komponensben található küls® pontjai, és létezik uv él G0 -ben. ⇒ A párosítás éleinek számát alternálva növeljük a két komponens gyökerét az uv élen keresztül összeköt® út mentén. 2. Ha van olyan u küls® pont F -ben és v ∈ / F , amikre létezik uv él G0 -ben. ⇒

F -hez hozzávéve v és µ(v) pontokat egy nagyobb alternáló erd®t kapunk. 3. Ha F valamelyik komponensében léteznek u és v küls® pontok, amikre létezik

uv él G0 -ben. ⇒ Az F által meghatározott uv út és az uv él az M párosításra illeszked® kehely. Ezt az Edmonds lemma alapján egy pontra húzhatjuk össze, így ha párosítás maximális volt G-ben, G0 -ben az új párosítás is az lesz. 4. Ha az el®z®ek közül egyik sem teljesül, akkor X -et a bels® pontok halmazának választva készen vagyunk, mert ezek éppen teljesítik az (a), (b) és (c) feltételeket. A 4.4. lemma miatt a maximalitást az 1. lépés összehúzásaival nem rontjuk, így a

G0 gráfot az algoritmus végén kibontva a megkapott párosítás is maximális lesz.

4.3. Az algoritmus súlyozott esetben

A 4.4. fejezetben szükségünk lesz arra, hogy minimális súlyú teljes párosítást tudjunk keresni egy gráfban. Ehhez a 4.2. fejezetbeli Edmonds algoritmus súlyozott változata kell, ami egyszerre oldja meg a primál és a duál problémát a teljes párosítás feladatra. 14

Tegyük fel, hogy G-nek van teljes párosítása és a w : E → R súlyfüggvény nemnegatív. Ekkor a [7] jegyzet alapján a következ® algoritmus ezt megtalálja. Tudjuk, hogy x(e) = 1 esetén

P

e∈δ(Z)

y(Z) = c(e) az [1]-ben tanult optimalitási

feltételek miatt. Az algoritmus lépései a következ®k: Válasszuk az algoritmus kezd®értékeinek M = ∅, y ≡ 0 duál megengedett függvény és Ω = {{v} | v ∈ V } adatokat, X pedig jelölje a szabad éleket. Legyen X Ey = {e | y(Z) = c(e)}. e∈δ(Z)

Kezdetnek építsünk alternáló erd®t X pontokon és Ey éleken. A párosítást mindvégig csak ezeken az éleken b®vítjük, ebb®l látható, hogy az algoritmus a futás végén optimális párosítást ad az el®z® bekezdésbeli tulajdonság és a duál-megengedettség miatt. Keressünk az alternáló erd®ben M -javító utat, és ha van ilyen ezeken növeljük a párosítást amíg lehet. Ha teljes párosítást kapunk, akkor megállunk. Ha van kehely (jelöljük Z -vel) az alternáló erd®ben, akkor ezt az el®z® algoritmusban leírt módon összehúzzuk. (Ekkor az összehúzott Z pont küls® pont lesz.) A ponthalmazát ekkor hozzáadjuk az Ω halmazhoz, valamint y(Z) = 0 súllyal jelöljük. Ezek után ha lehetséges a párosítást növeljük alternáló utakkal, az újonnan keletkez® kelyheket is összehúzzuk. (Ebben a lépésben az el®z® algoritmust futtatjuk, de csak az X pontokon és Ey éleken.) Amikor a fenti módon nem lehet továbbhaladni, az y(Z) duális értékeket kell módosítani a következ®képpen: ha az összehúzott Z halmaz küls® pont, akkor növelni, ha bels® pont, akkor csökkenteni ugyanazzal az értékkel amíg lehet (azaz amíg primál- és duálmegengedett a megoldás). Ha bármekkora értékkel módosíthatunk a duálmegoldáson (azaz nem korlátos a duális poliéder), akkor a primál feladat nem megoldható a dualitástétel [1]-ben tanult következményei miatt. A fenti m¶veletekkel az

P

|Z|plan

y(Z) összeg n®, viszont a párosítás élei pontosak

maradnak. Ekkor a következ® két eset lehetséges:

• y(Z) = 0 valamely Z : |Z| ≥ 3-ra. Ekkor kibontjuk a Z összehúzott halmazt, kivesszük az Ω-ból és újra összehúzzuk a gráfban található kelyheket, valamint 15

növeljük a párosítást (azaz az algoritmus lényegi lépéseit elölr®l kezdjük). Ebben az esetben Z bels® pont kell legyen.

• ∃Z :

P

e∈δ(Z)

y(Z) ≤ c(e) pontos, azaz egyenl®séggel teljesül. Ekkor legyen

Ey = Ey ∪ {e}, majd a lényegi lépéseket elölr®l kezdjük. Az algoritmus akkor áll meg, ha a párosítás teljes, és mivel a megoldás végig duálmegengedett volt, valamint teljesül az éleire x(e) = 1, ezért ekkor maximális.

4.4. Egy algoritmus minimális

T -kötések

és a maximális

T-

vágás pakolás megkereséséhez

Az [5] alapján az algoritmus els®nek leírt verziója csak a w ≥ 0 esetben m¶ködik, kés®bb a megfelel® módosításokkal ezt általánosítva kapjuk az algoritmust tetsz®leges súlyfüggvényhez. Ha a súlyfüggvény nemnegatív, akkor a következ® eljárást alkalmazzuk. Készítsünk egy KT segédgráfot a T pontjain (ezek száma mindig páros). KT legyen teljes gráf,

λ(xy) =

min

P x→y

út

G-ben

w(P )

súlyozással, és keressük meg az M minimális súlyú teljes párosítást a gráfon a súlyozott Edmonds algoritmussal. Ekkor JM = E(P1 ) ⊗ E(P2 ) ⊗ · · · ⊗ E(P|T |/2 ) T -kötés minimális, ha a Pi a párosítás éleinek megfelel® minimális utat jelenti G-ben.

4.6. Tétel. JM minimális súlyú T -kötés Bizonyítás.

Mivel JM élidegen körök és T -végpontú utak uniója, ezért biztosan

T -kötés a 2.9. tétel alapján. Továbbá legyen J egy tetsz®leges T -kötés. Ez körök és T -végpontú utak uniója, ezek (az utak) legyenek Ri = si , . . . ti . Jelöljük

M 0 -vel a {s1 t1 , . . . sk tk } párosítást. Ekkor w(J) ≥

X

w(Ri ) ≥

i

X

λ(si ti ) = λ(M 0 ) ≥ λ(M ) =

i

X

w(Pi ) ≥ w(JM ),

i

így JM minimális.

 16

Nem feltétlenül konzervatív súlyozásra az általános algoritmus: nézzünk egy negatív súlyú e0 = uv élet. Ha a feladatot felírjuk az eredetivel ekvivalensen az e0 negatív él nélkül, akkor ezt az átfogalmazást alkalmazva minden negatív élet ki tudunk küszöbölni.

( Legyen T 0 = T ⊗ {u, v} és w0 (e) =

w(e)

ha e 6= e0

|w(e)| ha e = e0 0 0 0 Ekkor J = J ⊗ e-re w (J ) = w(J) + |w(e0 )|, mivel

.

• ha J 0 = J \ {u, v}, akkor w0 (J 0 ) = w(J) − w(e0 ) = w(J) − (−|w(e0 )|), • ha J 0 = J ∪ {u, v}, akkor w0 (J 0 ) = w(J) + w(e0 ) = w(J) + |w(e0 )|, így a 2.11. tétel miatt J 0 minimális súlyú T 0 -kötés pontosan akkor, ha J minimális súlyú T -kötés. Ha ezt minden negatív élre elvégzem, akkor az el®z® módszer szerint tudok minimális súlyú T -kötést keresni. A súlyozott Edmonds algoritmus futásideje a [7] szerint polinomiális, mivel legfeljebb

O(n2 ) itarációt hajtunk végre polinomiális lépésekkel. A KT segédgráfban az el®z® algoritmus a minimális teljes párosítás mellett adott egy duális megoldást a 2. LP feladatra. Ez a vektor a páratlan pontszámú Z ⊂ T lamináris halmazokat súlyozza. A [6] cikk hivatkozása szerint a [9] könyv taralmaz egy olyan - Edmonds és Johnson által módosított - algoritmust, amely a minimális

T -kötés (4) és maximális T -vágás pakolás (3) feladatát egyszerre oldja meg. Az algoritmus által megadott megoldást felhasználhajuk az 1. fejezetben található feladatok megoldásában. Erre jó példa a kínai postás problémája. A feladatot átfogalmazhatjuk a következ®képpen, hogy a minimális T -kötés keresés feladattal legyen egyenérték¶: válasszuk T = {páratlan fokszámú pontok V-ben} halmazt és ezen keressünk minimális súlyú T -kötést. Ekkor a megoldás éppen olyan élhalmazt ad, amely a fokszámait tekintve a gráf páratlan fokszámú pontjain páratlan, páros fokszámú pontjain páros, és ezek közül minimális. Tehát megkapjuk, hogy mely éleket kell megduplázni a gráf Eulerré tételéhez. Másik hasonló eset az s, t pontok közti útkeresés konzervatív gráfon. Ehhez egyszer¶en válasszuk T = {s, t} halmazt, az erre kapott megoldás egy s − t utat és esetleg néhány kört tartalmaz. Ekkor a konzervativitás biztosítja, hogy van olyan minimális

17

súlyú T -kötés, ami nem tartalmaz kört. Ha egy gráfban maximális súlyú Euler-részgráf ot kell keresni, akkor a fenti algoritmus szintén jól használható. Olyan részgráfot keresünk, amiben minden pont foka páros, vagyis megfeleltethet® egy T = ∅ halmazon vett T -kötésnek. A súlyozást megfordítva, vagyis c∗ ≡ −c függvényre a minimális T -kötés éppen a c súlyozású gráf maximális T -kötése a fenti tulajdonsággal.

5. Minimális súlyú

T -vágás

keresése

A feladat megoldására használt Padberg és Rao által leírt algoritmus rekurzívan keresi a gráfban a legkisebb súlyú T -vágást. Ehhez mindössze az 5.1. lemmát kell használni. Az algoritmus gyorsabb változata a minimális vágásokra épül® GomoryHu fákat használja, jelent®sen gyorsítva a futásid®t.

5.1. A Padberg-Rao algoritmus

Az algorimushoz a [10] cikkben leírt algoritmus alapján szükségünk lesz a következ® lemmára.

5.1. Lemma. Legyen [S, V \S] olyan vágás, ami legalább két pontot elválaszt T -ben és ezek közül minimális. Ekkor a következ®k igazak:

• ha |S ∩ T | páratlan, akkor S minimális T -vágás • ha |S ∩ T | páros, akkor létezik olyan S 0 ⊆ S vagy S 0 ⊆ V \ S , ami minimális T -vágás.

Bizonyítás.

Az els® eset a 2.5. deníciójából következik. Legyen A minimális T -

vágás, amely metszi S -et. Ilyen biztosan létezik, hiszen ha A nem ilyen, akkor V \ A biztosan jó lesz, és ez ugyanúgy minimális T -vágás. A második esetet két részben bizonyítjuk |A ∩ S ∩ T | paritása szerint. (Tudjuk, hogy |S ∩ T | páros.) 1. Ha |A ∩ S ∩ T | páratlan, akkor 18

(a) A ∪ S belemetsz T -be. Ekkor a θ függvény szubmodularitása miatt

θ(A ∩ S) + θ(A ∪ S) ≤ θ(A) + θ(S). Mivel A és S vágások minimálisak valamint A ∩ S is T -vágás, így θ(A ∩

S) ≥ θ(A) és θ(A ∪ S) ≥ θ(S), és itt az el®z® egyenl®tlenség miatt mindkét helyen = teljesül. Tehát (A ∩ S) ⊆ S minimális T -vágás. (b) T ⊆ A ∪ S esetén. Írjuk fel az (a)-beli egyenl®tlenségeket az A helyett

V \ A-ra. Ekkor az el®z® tulajdonságok miatt látszik, hogy (V \ A) ∩ S minimális T -vágás. 2. Ha |A ∩ S ∩ T | páros, akkor az S 0 = V \ S -re |A ∩ S 0 ∩ T | páratlan, tehát az 1. eset alapján a bizonyítás kész.

 Az 5.1. lemmát felhasználva keresünk a T -be belemetsz® vágások közül egy minimálisat, és ha ez nem T -vágás, akkor a gráf mindkét kisebb részében (S -ben, és

V \S -ben is) keresünk tovább. Ezt lehet rekurzívan ismételni a gráf kisebb részeiben, amíg T -vágást kapunk. Minimális vágás kereséséhez használhajuk a Ford-Fulkerson algoritmust a [2] alapján.

5.2. Az algoritmus futása egyszer¶bben a Gomory-Hu fa felhasználásával

5.2. Deníció (Gomory-Hu fa). G(V, E) gráfon adott c : E → R+ kapacitás mellett minden s, t ∈ V párra jelölje λ(st) a két pont között egy minimális kapacitású vágás értékét. Legyen a fa ponthalmaza VT = V , valamint jelölje egy s − t út éleit Pst a fában. A fa élhalmaza legyen olyan, hogy

λ(st) = min c(Se , Te ) ∀s, t ∈ V , e∈Pst

ahol Se és Te a T \ {e} gráf két komponense úgy, hogy [Se , Te ] egy s − t vágást alkot

G-ben.

19

A LEMON programcsomagban (b®vebben: [11]) ennek az elkészítésére van agoritmus, amelyben:

input G(V, E) gráf és c súlyfüggvény output T (VT , ET ) GomoryHu fa Ha a Padberg-Rao algoritmus iterációi helyett a gráfból építünk a programmal egy Gomory-Hu fát, akkor elég azt nézni, hogy a minimális vágás T -vágás lesz-e, és ha nem, akkor a fa két komponensében a minimálisokra ellen®rizni a feltételt (tehát nem kell a részgráfokban minimális vágásokat keresni). Ezzel a módosítással az algoritmus futásideje megegyezik n − 1 minimális s, t-vágás meghatározásával, azaz nagyságrendileg a fa felépítésének idejével.

6. Maximális súlyú

T -kötés

pakolás meghatározása

A teljes a 6. fejezetben a [6] cikk alapján a maximális T -kötés pakolás algoritmusa található. Az algoritmushoz szükéges eljárások, fogalmak és tételek: Jelölje G − α · U azt a gráfot, amiben a c kapacitás értékét az U halmaz élein αval csökkentettük. Ha valamelyik élen a kapacitás 0-ra változik, azt rögtön töröljük

G − α · U gráfból, hiszen az optimális pakolásában biztosan nem szerepel. Legyen a Padberg-Rao algoritmus által megtalált minimális T -vágás értéke λ(G) =

min{θ(S) : S ⊂ V, |S ∩ T | páratlan}. Tudjuk, hogy egy T -kötés és T -vágás metszete páratlan, tehát minden esetben legalább egy. A dualitástétel miatt a primál és duálmegoldás között "≤" helyett akkor szerepel "=", ha az optimalitási feltételek teljesülnek. Ez akkor teljesül, ha minden olyan T -kötés, ami szerepel a pakolásban (tehát a súlya nem 0), pontosan egy élen metsz minden minimális T -vágást.

6.1. Deníció.

Egy T -kötés feszes, ha minden minimális T -vágást pontosan egy

élen metsz. δ(S) T -vágás feszes egy U T -kötésre nézve, ha |δ(S) ∩ U | = 1. Jelölje minden T -kötéshez a hozzá tartozó értéket

αU = max{α : λ(G − α · U ) = λ(G) − α, 0 ≤ α ≤ µ(U )}, 20

azaz azt a maximális súlyt, amivel csökkentve az U halmazt a pakolásban a minimális

T -vágás értéke ugyanennyivel fog csökkenni az eredeti gráfhoz képest.

6.2. Lemma.

Legyen U T -kötés. Ha αU = 0, akkor van olyan minimális T -vágás,

amit az U egynél több élen metsz.

Bizonyítás.

Legyen k = |δG (S)∩U | ≥ 1. A G−α·U gráfban a δ(S) vágás kapacitása

ekkor θG (S) − k · α. Ebb®l tudjuk, hogy a λ(G − α · U ) ≤ λ(G) − α egyenl®tlenség minden 0 ≥ α ≥ µ(U ) esetén fennáll. Kellene, hogy amennyiben az U T -kötés feszes létezik olyan αU , amire igaz az egyenl®ség és nem 0. Válasszuk az α-t úgy, hogy kisebb legyen, mint az összes (nem csak minimális) vágásra a λ(G − α · U ) érték és αU ≤ µ(U ), hogy ne keletkezzenek negatív kapacitású élek. Ez az érték biztosan nagyobb, mint 0, tehát az állítás igaz.

6.1. Adott tulajdonságú



T -kötés

keresése

input Φ lamináris rendszer, amiben az S ∈ Φ egy T -vágást reprezentál output U T -kötés, amire |U ∩ δ(S)| = 1 ∀S ∈ Φ A megadott tulajdonságú T -kötés kétféleképpen is megkereshet®. Az els® lehet®ség a [6] alapján a gráf egyes lamináris halmazait összehúzva rekurzívan m¶ködik, ehhez használjuk a következ® lemmát.

6.3. Lemma.

Legyen adott δ(S) minimális T -vágás a gráfon, és legyen a G0 és

G00 a következ®: a G0 gráf G-b®l úgy keletkezik, hogy az S halmaz pontjait egy pontra húzzuk össze, és ezt a pontot adjuk a T -hez, G00 -nél ugyanígy járunk el V \ S pontjaival. Ekkor az eredeti gráf egy optimális T -kötés pakolása el®állítható a két másik gráf egy-egy optimális pakolásának kombinációjaként.

Bizonyítás.

Felírhatjuk a λ(G) = λ(G0 ) = λ(G00 ) összefüggést, hiszen a minimális

T -vágás élei az S és V \ S halmazok között vezetnek, tehát nem húztuk össze ®ket. Mivel |S ∩ T | páratlan, ezért ha egy e ∈ δ(S) élet tartalmaz a U 0 (G0 -beli) és U 00 (G00 beli) T -kötés is, akkor az eredeti G gráfban az U 0 ∪ U 00 is T -kötés lesz. Ez azért igaz, mert az összehúzott halmazokban a fokszámok mindkét részben megfelelnek 21

a T -kötés tulajdonságainak, a halmazok közti élekb®l pedig páros sok van, hiszen

U 0 -ben és U 00 -ben is páratlan darab ilyen él van, és ezekb®l egyet (e-t) vagy páratlan sok darabot csak egyszer veszem bele az unióba. Jelölje az optimális pakolás (y 0 ) nem 0 súlyú T -kötéseit a G0 gráfban {Ui0 }. Ugyanígy

{Ui00 } jelölje a G00 gráf optimális (y 00 ) pakolásában nem 0 súlyú elemeket. Ekkor X

c(e) =

y 0 (Ui0 ) =

Ui0 : e∈Ui0

X

y 00 (Ui00 )

Ui00 : e∈Ui00

következik az els® összefüggésb®l. Legyen e ∈ δ(S) olyan él, amit mindkét pakolásban tartalmaz egy Uk0 és egy Ul00 T -kötés. Ekkor válasszuk y(U ) = min{y 0 (Uk0 ), y 00 (Ul00 )}nek az él súlyát a pakolásban, valamint azt a kötést, amib®l az e élet teljesen felhasználtuk (tehát a fenti minimum értéke egyenl® az él pakolásbeli súlyával) dobjuk ki az adott részgráf-pakolásból.



A 6.3. lemma alapján azt az U T -kötést, amire |U ∩ δ(S)| = 1 minden S Φ-beli

T -vágásra a következ® algoritmussal kereshetjük rekurzívan. Legyen S = V és készítsünk egy GS segédgráfot, amiben a Φ lamináris halmaz maximális méret¶ S által tartalmazott halmazait összehúzzuk egy-egy pontra (ezek legyenek T -pontok). TS = {T -pontok GS -ben} pontjain építsünk egy teljes gráfot, ahol az élek súlya a GS -ben a két pont közti legrövidebb út (ahol összehúzott halmaz az útnak csak végpontja lehet) éleinek száma, vagy ∞ ha nincs ilyen út. Keressünk a teljes gráfon minimális súlyú teljes párosítást, majd az ezeknek megfelel® utak uniójaként megkapjuk U 0 minimális T -kötést a GS -en, ami az összehúzott halmazokat éppen egy élen metszi az utaknál leírt feltétel miatt. A teljes párosítás létezik és véges, hiszen minden optimális pakolásbeli kötésb®l egy párosítás lesz. Válasszunk egy összehúzott W halmazt, és legyen a halmazba érkez® U 0 -beli él e. Ekkor S = W ∪ {e} halmazzal folytatjuk az algoritmust, ahol az e küls® pontja T pont. Jelöljük ebben a (rekurzívan, az eddigihez hasonló módon) megtalált T -kötést

U 00 -vel. Ekkor mivel e a két kötésnek közös éle, U = U 0 + U 00 a keresett T -kötés. A megtalált T -kötésre igaz lesz, hogy minden S ∈ Φ halmazzal az élek metszete éppen egy, mert minden halmaznál az összehúzás miatt csak egy belép® élet vettünk az

U -ba. 22

Második lehet®ségként használhatjuk az el®z® rekurzió helyett az [5] jegyzetben található minimális T -kötést megtaláló algoritmust. Készítsünk egy új súlyfüggvényt a gráf élein, legyen a gráf élein értelmezett c∗ (e) = |{S ∈ Φ : e ∈ δ(S)}| adott (c∗ -ot könnyen megkaphatjuk minden élet egyesével végignézve). Tudjuk, hogy bármely U

T -kötésre és δ(S) T -vágásra |U ∩ δ(S)| ≥ 1 a 2.10. állítás miatt. Ebb®l következik, hogy az U akkor minimális, ha az el®bbi érték mindenhol pontosan egy. Tehát használjuk a 4.4. fejezet algoritmusát minimális T -kötés keresésre, és ez éppen a megadott tulajdonságú T -kötést adja.

6.2. Egy

T -kötéshez

tartozó

αU

érték kiszámítása

Adott U élhalmaz esetén szeretnénk kiszámítani a 6. fejezet elején deniált αU értéket. Ehhez válasszuk el®ször αU = µ(U )-t, majd ezt csökkentve - olyan értékre, amir®l tudjuk, hogy ennél nagyobb nem lehet αU - jutunk el egy megfelel® értékhez, ami a csökkentés feltétele miatt maximális. Megfelel® az az α, amire

λ(G − α · U ) = λ(G) − α. Keressünk az 5.1. fejezet algoritmusával a G − αU · U gráfban minimális T -vágást, és jelöljük az éleit δ(S)-sel. Ha ennek az értéke megfelel®, akkor az algorimus kilép és ez lesz a maximális αU érték. Ha nem, akkor k = |U ∩ δG (S)| ≥ 1 miatt λ(G) − α ≥

θ(S) − k · α = λ(G − α · U ). Mivel ebb®l következik, hogy α≥α ¯=

θ(S) − λ(G) , k−1

így az αU = α ¯ választással a legnagyobb lehetséges αU értéket jelöljük ki a következ® ciklus kezd®értékének. A módszert ismét a minimális T -vágás kereséssel folytatjuk tovább, amíg nem találjuk meg az αU értéket.

6.3. Lamináris halmazrendszer b®vítése a halmazok feszességének megtartásásval

Az algoritmusban felépítünk egy lamináris Φ rendszert, ahol minden halmaz egy

T -vágásnak felel meg. Az algoritmus egy lépésében a fenti módszerrel keresünk egy U T -kötést, ami minden Φ-beli vágást pontosan egy élen metsz. Ahhoz, hogy az U 23

az eredeti T -vágásokat is pontosan egy élben metssze, szükséges, hogy a következ® lemmák szerint építsük fel a Φ-t.

6.4. Lemma.

Legyenek A, B minimális súlyú T -vágások, amik keresztez®k (a 2.2.

deníció szerint). Legyen |A ∩ B ∩ T | páratlan. Ekkor ha A ∩ B és A ∪ B feszes U -ra nézve, akkor A és B is feszes U -ra.

6.5. Lemma.

Legyenek A, B minimális súlyú T -vágások, amik keresztez®k (a 2.2.

deníció szerint). Legyen |A ∩ B ∩ T | páros. Ekkor ha A \ B és A \ B feszes U -ra nézve, akkor A és B is feszes U -ra. Az els® lemmából következik a második, hiszen ha az els® lemmában B helyett V \B halmazt használjuk, akkor a paritásokat vizsgálva azt kapjuk, hogy ha |A∩V \B ∩T | páros, akkor |A ∩ V \ B ∩ T | páratlan. Továbbá A ∩ (V \ B) = A \ B , és ugyanígy az unióra, ezért éppen a 6.5. állítást kapjuk.

Bizonyítás.

[6.4. lemma] A θ függvény szubmoduláris tulajdonsága miatt θ(A ∪

B) + θ(A ∩ B) ≤ θ(A) + θ(B). Tudjuk, hogy A és B T -vágások, tehát a metszetük (mivel |A ∩ B ∩ T | páratlan), és így az uniójuk is T -vágás. A két halmaz minimalitásából következik, hogy θ(A) ≤ θ(A ∩ B) és θ(B) ≤ θ(A ∪ B). Tehát a fenti "≤" helyett biztosan "=" szerepel, vagyis a metszet és az unió is minimális T -vágás. Tudjuk, hogy egy U T -kötésnek pontosan egy éle lép ki A ∩ B -b®l és A ∪ B -b®l is. Ekkor a lehetséges eseteket megnézve (az A ∩ B, A \ B, B \ A halmazok között futó és ezekb®l kilép® élek számát vizsgálva) A-ból és B -b®l is éppen egyetlen él lép ki.

 Adott U (a Φ pontjain feszes) T -kötés mellett a lamináris Φ rendszerhez a következ® algoritmusssal adjuk hozzá S -et. Ameddig van olyan A ∈ Φ halmaz, amire A ∩ S nem üres: 1. ha A ∩ S ∩ T pontjainak száma páratlan (a) |δ(A ∪ S) ∩ U | > 1 ⇒ S = A ∪ S (b) |δ(A ∪ S) ∩ U | = 1 ⇒ S = A ∩ S 2. ha A ∩ S ∩ T pontjainak száma páros 24

(a) |δ(A \ S) ∩ U | > 1 ⇒ S = A \ S (b) |δ(A \ S) ∩ U | = 1 ⇒ S = S \ A Ez az algoritmus az 1. és a 2. lemmákat használja, ezért ha egy U T -kötés a Φ minden vágására feszes, akkor az eredeti S -sel jelölt vágásra is feszes. Továbbá a futás végére a Φ rendszer lamináris lesz, így az algoritmus futása közben helyettesíthet® vele az eredeti vágások halmaza.

6.4. Az algoritmus lépései az el®z® fejezetek felhasználásával

A [6] cikkben leírt algoritmus a 6.2. lemma alapján m¶ködik. El®ször válasszuk Φt üres halmaznak. A következ® lépéseket ciklikusan végrehajtva, ha az algoritmus megáll, akkor biztosan maximális pakolást kaptunk. Keressünk olyan U T -kötést, amire igaz, hogy minden Φ-beli halmazt pontosan egy élen metsz, azaz |U ∩ δ(S)| = 1 ∀S ∈ Φ-re. Kiszámoljuk a 6.2. fejezet alapján az

αU értékét. Ha αU = µ(U ), akkor a gráf éleinek száma legalább eggyel csökken. Ha αU < µ(U ), akkor δ(S) biztosan feszes T -vágás U -ra nézve, vagyis |U ∩ δ(S)| = 1. Ezt belevesszük Φ-be úgy, hogy lamináris rendszert készítünk a halmazokból a 6.3. fejezetben leírtak alapján, így a feszesség megmarad a lamináris rendszerben is. Végül a gráf méretét (élsúlyait) csökkentjük, vagyis G = G−αU ·U . Ha így λ(G) = 0ra jutunk, akkor a pakolás mérete elérte a minimális T -vágás értékét, vagyis az algoritmus leáll. Különben folytatjuk a ciklust az új G gráal. A λ(G) érték kiszámításához használhatjuk az 5.1. fejezetben található Padberg-Rao algoritmust. Az algoritmus végén megtalált T -kötés pakolás maximalitását biztosítja, hogy minden minimális T -vágással éppen egy élen metszik egymást. Az algoritmus végessége abból látszik, hogy minden lépésben csökkentjük az élek számát, vagy hozzáteszünk egy halmazt a lamináris rendszerhez, amir®l tudjuk, hogy n pontra legfeljebb 2n − 1 eleme lehet. Az algoritmus polinomiális lépésszámú, hiszen az összes felhasznált szubrutin is polinomiális id®ben fut és maximum m + 2n − 1-szer iteráljuk a lépéseket. A [6] cikk 25

alapján a futásid® O(n6 ).

7. A minimális

T -kötés

és a minimális

T -vágás

kere-

sés algoritmusának programozása

A Függelékben található két programkódot a minimális T -kötés és minimális T -vágás keresés algoritmusából a LEMON [11] programcsomag felhasználásával készítettem. A

LEMON egy olyan C++ programcsomag, amelyben a gráfokhoz jól használható adatszerkezetek és algoritmusok vannak implementálva. A programkódban a ListGraph irányítatlan struktúrát választottam, a gráfokat a LEMON által használt .lgf fájlokban tároltam, illetve innen olvastam be a GraphReader osztállyal. A kódolást lényegesen egyszer¶sítette az, hogy a programcsomagban többek között a Dijkstra, BFS és Gomory-Hu algoritmusok is implementálva vannak. A szdgraf.cc fájl tartalmazza a gráf beolvasását, nemnegatív élsúlyokra a minimális T -kötés megkeresését, a minimális T -vágást keres® Padberg-Rao algoritmust, valamint a kiírást egy másik .lgf fájlba. A gráfokról készült ábrákat a szdrajz.cc fájl készíti el, ami a gráfból egy LATEX formátumú, Tik Z csomagot használó kódot generál. A gráf csúcsait a program egy körön helyezi el, a T halmaz elemeit dupla karikával jelölve. Amennyiben a szdgraf.cc által megadott fájlban a minimális

T -vágás pontjai is szerepelnek, ezeket lilára színezve láthatjuk, a minimális T -kötés éleit (ha szerepelnek a fájlban) pedig kékkel jelöltem az ábrán. A továbbiakban olyan példák szerepelnek, amelyeket a program futásának eredményeként kaptam különböz® gráfokon.

26

Egy 5 pontú gráf, |T | = 4 esetben (in1.lgf):

@nodes label tnodes 0 1 1 0 2 1 3 0 4 1 5 1 @edges label 0 1 0 1 2 1 0 2 2 1 3 3 2 3 4 3 4 5 5 1 6 5 0 7

capacity 10 6 5 3 7 10 9 3

Az algoritmusok futásának eredménye a következ® fájlban látható (out1.lgf). Ugyanez az eredmény szerepel a szdrajz.cc fájl által kirajzolva az 1. ábrán.

@nodes label tnodes 0 1 1 1 0 1 2 1 1 3 0 1 4 1 0 5 1 1 @edges label 0 1 0 1 2 1 0 2 2 1 3 3 2 3 4 3 4 5 5 1 6 5 0 7

tcut

capacity 10 0 6 0 5 0 3 0 7 1 10 1 9 0 3 1

tjoin

A következ® példákon csak egy-egy él súlyát módosítottam, ebb®l könnyen láthatóak a program megoldásai a különböz® esetekre. Változtassuk az 1 − 3 él súlyát 7-re (in2.lgf). Ekkor a megoldás is változik, ez 27

1

2 2 3

1

4

1

1

2 2 0

3

3

7

4

1

1

2 2 0

3

3

1

4

7

0

3

1. ábra. Kékkel jelölve a minimális T -kötés az élsúlyok változtatása mellett.

1

2 2 3

3

1

1

1

2 4

2 0

3

7

1

4

2 0

3

1

2

3

1

7

4 0

3

2. ábra. Lilával jelölve a minimális T -vágás, az élsúlyok megváltoztatásával.

látható a 2. ábrán, módosul a minimális T -vágás. A 2 − 0 él súlyát növelve változik a minimális T -kötés. Ezeket a megoldásokat szemlélteti az 1. és a 2. ábra.

28

Egy további példa látható az algoritmus futására a a 3. ábrán, nagyobb méret¶ gráfon.

@nodes label tnodes 0 1 1 1 0 1 2 1 1 3 0 1 4 1 0 5 1 1 @edges label 0 1 0 1 2 1 0 2 2 1 3 3 2 3 4 3 4 5 5 1 6 5 0 7

2 7

tcut

capacity 10 0 6 0 5 0 3 0 7 1 10 1 9 0 3 1

2

6 7

1

3

5

3 10

tjoin

10

10

3

4

1

3

5

3 0

9

6

0

9 3

4

5

10

5

3. ábra. Az algoritmus által megtalált minimális T -kötés (kékkel), T -vágás (lilával).

29

Hivatkozások

[1] Frank Andás: Operációkutatás 1. el®adásjegyzet, 2014-2015. I. félév [2] Jüttner Alpár: Operációkutatás 2. el®adásjegyzet, 2014-2015. II. félév [3] Frank András: Poliéderes kombinatorika, 2. fejezet, 2014 http://www.cs.elte.hu/∼frank/jegyzet/polkomb/upoli.2014.pdf [4] D. R. Fulkerson: Blocking polyhedra, 1968 www.dtic.mil/cgi-bin/GetTRDoc?AD=AD0679986 [5] Frank András: Kombinatorikus optimalizálási struktúrák, 1. fejezet, 2013 http://www.cs.elte.hu/∼frank/jegyzet/kombopt/kombo.2013.pdf [6] Francisco Barahona: Fractional packing of T-joins, 2002 http://www.optimization-online.org/DB_FILE/2002/06/493.pdf [7] Jan Vondrák: Polyhedral techniques in combinatorial optimization, Lecture 6: Weighted non-bipartite matching http://theory.stanford.edu/∼jvondrak/CS369P/lec6.pdf [8] Frank András: Diszkrét optimalizálás http://www.cs.elte.hu/sinfrank/jegyzet/disopt/dopt13.pdf [9] J. Edmonds and E. L. Johnson, Matching, euler tours and the chinese postman, 1973 [10] M. W. Padberg and M. R. Rao, Odd minimum cut-sets and b-matchings, 1982 [11] LEMON programcsomag 1.3.1 verzió, ELTE https://lemon.cs.elte.hu/

30

Függelék

szdgraf.cc #include #include #include #include #include #include #include #include #include #include #include #include

// ListGraph // BFS algoritmus // Dijkstra algoritmus // gráfbeolvasó // filebaírás // SubGraph

using namespace lemon; using namespace std; void minTjoin(ListGraph &g, ListGraph::EdgeMap &capacity, ListGraph::NodeMap &tnodes, ListGraph::EdgeMap &minjoin); int padbergRao(ListGraph &g, ListGraph::EdgeMap &capacity, ListGraph::NodeMap &mincut, ListGraph::NodeMap &tnodes); int main() { // A GRÁF BEOLVASÁSA FILEBÓL: ListGraph g; ListGraph::NodeMap tnodes(g); ListGraph::EdgeMap tjoin(g); ListGraph::NodeMap proba(g); ListGraph::NodeMap proba2(g); ListGraph::NodeMap mincut(g); ListGraph::NodeMap proba3(g); ListGraph::EdgeMap capacity(g); ListGraph::EdgeMap minjoin(g); ListGraph::EdgeMap gs(g); bool beolvasaskesz; bool ujraolvas=false; do { string filename0; filename0="in.lgf"; cout << "A bemen® gráfot tartalmazó file neve (lgf): "; cin >> filename0; const char* filename1=filename0.c_str(); ifstream infile; infile.open(filename1); if(infile.is_open()) { beolvasaskesz=true; GraphReader beolvas(g, infile); beolvas .nodeMap("tnodes", tnodes) .edgeMap("capacity", capacity) .run(); } else { beolvasaskesz=false; cout << "Nem létez® fájl!" << endl; cout << "Újra (igen: 1, nem: 0)? "; cin >> ujraolvas; cout << endl;

31

}

} infile.close(); }while(!beolvasaskesz && ujraolvas == true); // GRÁF KIÍRÁSA A TERMINÁLRA: for(ListGraph::EdgeIt e(g); e != INVALID; ++e) { gs[e]=true; } string filename2; cout << "A megoldást tartalmazó file neve (lgf): "; cin >> filename2; const char* filename3=filename2.c_str(); ofstream outfile; outfile.open(filename3); GraphWriter kiiro(g, outfile); kiiro .nodeMap("tnodes", tnodes) .edgeMap("capacity", capacity) .nodeMap("tcut", mincut) .edgeMap("tjoin", minjoin); // M–VELETEK: int a=padbergRao(g, capacity, mincut, tnodes); minTjoin(g, capacity, tnodes, minjoin); // ÚJ GRÁF KIÍRÁSA A TERMINÁLRA: kiiro.run(); return 0;

//MIN T_JOIN (only >0 capacity) void minTjoin(ListGraph &g, ListGraph::EdgeMap &capacity, ListGraph::NodeMap &tnodes, ListGraph::EdgeMap &minjoin) { ListGraph k; for (ListGraph::NodeIt n(g); n != INVALID; ++n) { ListGraph::Node x = k.addNode(); } for (ListGraph::NodeIt n(k); n != INVALID; ) { ListGraph::NodeIt n2=n; ++n2; if(tnodes[g.nodeFromId(k.id(n))]==false) { k.erase(n); } n=n2; } ListGraph::EdgeMap lambda(k); for (ListGraph::NodeIt n(k); n != INVALID; ++n) { for (ListGraph::NodeIt m(k); m != INVALID; ++m) { if(n<m) { k.addEdge(n, m); } } } ListGraph::EdgeMap<Path > p(k); for (ListGraph::EdgeIt e(k); e != INVALID; ++e) { Dijkstra > djk(g, capacity); djk.run(g.nodeFromId(k.id(k.u(e)))); lambda[e]=djk.dist(g.nodeFromId(k.id(k.v(e)))); p[e]=djk.path(g.nodeFromId(k.id(k.v(e)))); } ListGraph::EdgeMap capminus(g); for(ListGraph::EdgeIt e(g); e!=INVALID; ++e) { capminus[e]=-capacity[e]; } MaxWeightedPerfectMatching mm(k, capminus); mm.run(); for(ListGraph::EdgeIt e(g); e != INVALID; ++e) { minjoin[e]=false; }

32

}

for (ListGraph::EdgeIt a(g); a != INVALID; ++a) { for (ListGraph::EdgeIt e(k); e != INVALID; ++e) { if(mm.matching(e)==true) { for(Path::ArcIt r(p[e]); r != INVALID; ++r) { if((g.source(r) == g.u(a) && g.target(r) == g.v(a)) || (g.source(r) == g.v(a) && g.target(r) == g.u(a)) ) { minjoin[a]= (!minjoin[a]); } } } } }

// PADBERG-RAO int padbergRao(ListGraph &g, ListGraph::EdgeMap &capacity, ListGraph::NodeMap &mincut, ListGraph::NodeMap &tnodes) { GomoryHu > ghtree(g, capacity); ghtree.run(); int minvalue; int minedgeid; bool firstvalue=true; ListGraph::EdgeMap tree(g); ListGraph::EdgeMap treevalide(g, false); for(ListGraph::NodeIt m(g); m!=INVALID; ++m) { for(ListGraph::NodeIt n(g); n!=INVALID; ++n) { if( n==ghtree.predNode(m) ) { ListGraph::Edge e=g.addEdge(n,m); capacity[e]=0; tree[e]=ghtree.predValue(m); treevalide[e]=true; } } } FilterEdges gsub(g, treevalide); for(ListGraph::EdgeIt e(g); e!=INVALID; ++e) { if(gsub.status(e)==true){ gsub.disable(e); int count=0; ListGraph::NodeMap comp(g); for(ListGraph::NodeIt n(g); n!=INVALID; ++n) { comp[n]=0; } Bfs > bfsalg(gsub); bfsalg.run(g.u(e)); for(ListGraph::NodeIt n(g); n!=INVALID; ++n) { if(bfsalg.reached(n)==true) { comp[n]=1; } } for(ListGraph::NodeIt n(g); n!=INVALID; ++n) { if(comp[n]==1 && tnodes[n]==true) { count++; } } if(count\%2==1) { if(firstvalue==true) { minvalue=tree[e]; for(ListGraph::NodeIt n(g); n!=INVALID; ++n) { mincut[n]=comp[n]; } firstvalue=false; } else { if(tree[e]<minvalue) {

33

}

}

minvalue=tree[e]; for(ListGraph::NodeIt n(g); n!=INVALID; ++n) { mincut[n]=comp[n]; }

} gsub.enable(e); }

}

} for(ListGraph::EdgeIt e(g); e != INVALID; ){ ListGraph::EdgeIt e2=e; ++e2; if(capacity[e]==0){ g.erase(e); } e=e2; } return minvalue;

szdrajz.cc #include #include #include #include #include

<sstream> <string>

using namespace std; int main() { bool beolvasaskesz; bool ujraolvas=false; vector > pontadatok; vector > eladatok; char t1, t2; do { string filename0; cout << "A gráfot tartalmazó file neve (lgf): "; cin >> filename0; const char* filename1=filename0.c_str(); ifstream infile; infile.open(filename1); cout << "Minimális T-kötés megjelenítése kék élekkel (i/ ): "; cin >> t1; cout << "Minimális T-vágás megjelenítése lila pontokkal (i/ ): "; cin >> t2; if(infile.is_open()) { beolvasaskesz=true; string a; getline(infile, a); while(getline(infile, a) && a != "@edges") { istringstream s(a); vector<string> belsotomb; string b; while(getline(s, b, '\t')) {

34

belsotomb.push_back(b); } pontadatok.push_back(belsotomb);

} bool first=true; while(getline(infile, a)) { istringstream s(a); vector<string> belsotomb; if(first==true) { belsotomb.push_back("upont"); belsotomb.push_back("vpont"); first=false; } string b; while(getline(s, b, '\t')) { if(b!="") {belsotomb.push_back(b);} } eladatok.push_back(belsotomb); }

} else { beolvasaskesz=false; cout << "Nem létez® fájl!" << endl; cout << "Újra (igen: 1, nem: 0)? "; cin >> ujraolvas; cout << endl; } infile.close(); }while(!beolvasaskesz && ujraolvas == true); int pontnev, tpont, tcut=-1; for(int j=0; j<pontadatok[0].size(); j++) { if(pontadatok[0][j]=="label"){ pontnev=j; } else if(pontadatok[0][j]=="tnodes"){ tpont=j; } else if(pontadatok[0][j]=="tcut"){ tcut=j; } } int kap, tjoin=-1, upont, vpont; for(int j=0; j<eladatok[0].size(); j++) { if(eladatok[0][j]=="capacity"){ kap=j; } else if(eladatok[0][j]=="tjoin"){ tjoin=j; } else if(eladatok[0][j]=="upont"){ upont=j; } else if(eladatok[0][j]=="vpont"){ vpont=j; } } ofstream outfile; string filename2; cout << "A rajzot tartalmazó file neve (tex): "; cin >> filename2; const char* filename3=filename2.c_str(); outfile.open(filename3); outfile<<"\\documentclass[12pt]{article}"<<endl; outfile<<"\\usepackage{tikz}"<<endl; outfile<<"\\begin{document}"<<endl; outfile<<"\\begin{tikzpicture}[scale=5]"<<endl; for(int i=1; i<pontadatok.size(); i++) {

35

double coord=((i-1)*360/pontadatok.size()); if(tcut != -1 && t2=='i') { if(pontadatok[i][tpont]=="1" && pontadatok[i][tcut]=="1") { outfile<<"\\path ("<
}

} for(int i=1; i<eladatok.size(); i++) { if( tjoin!=-1 && t1=='i' && eladatok[i][tjoin]=="1" ) { outfile<<"\\draw[blue] ("<<eladatok[i][upont]<<") -- node [above] {$"<<eladatok[i][kap]<<"$} ("<<eladatok[i] [vpont]<<");"<<endl; } else { outfile<<"\\draw ("<<eladatok[i][upont]<<") -- node [above] {$"<<eladatok[i][kap]<<"$} ("<<eladatok[i][vpont]<<");"<<endl; } } outfile<<"\\end{tikzpicture}"<<endl; outfile<<"\\end{document}"<<endl; outfile.close();

36