KOMBINATORIKUS ALGORITMUSOK II.

Frank András

1. Fejezet

ÁRAMOK ÉS FOLYAMOK

Jelöljön D = (V, E) egy irányított gráfot. Tetszőleges x : E → R_{+} vektorra és S ⊆ V halmazra legyen ϱ_{x}(S) := ∑(x(uv) : uv ∈ E, uv belép S-be) és legyen δ_{x}(S) := ϱ_{x}(V − S).

D-ben adott egy s forráspont és egy t nyelőpont úgy, hogy s-be nem lép be él és t-ből nem lép ki él. Folyamon egy olyan nemnegatív x : E → R_{+} vektort értünk, amely minden, s-től és t-től különböző pontra teljesíti a megmaradási szabályt (conservation rule), azaz ϱ_{x}(v) = δ_{x}(v) fennáll minden v ∈ V − {s, t} csúcsra, ahol Amennyiben még az x ≤ g feltétel is teljesül, megengedett folyamról beszélünk. Egy s-t tartalmazó, de t-t nem tartalmazó X halmazt nevezzünk st̄-halmaznak.

Tetszőleges S st̄-halmaz és x folyam esetén δ_{x}(S) − ϱ_{x}(S) = ∑(δ_{x}(v) − ϱ_{x}(v) : v ∈ S) = δ_{x}(s) − ϱ_{x}(s) = δ_{x}(s). Vagyis minden S st̄-halmazra a δ_{x}(S) − ϱ_{x}(S) értékkel definiált tiszta kiáramlás független S választásától. Ezt a közös, δ_{x}(s)-sel (és ϱ_{x}(t)-vel) egyenlő értéket nevezzük az x folyam nagyságának. Az x(uv) szám a folyam értéke az uv ∈ A élen. Az x folyamot út-folyamnak (kör-folyamnak) nevezzük, ha x csak egy s-ből t-be vezető út (irányított kör) mentén pozitív.

Gyakorlat 1.1 Igazoljuk, hogy minden nem-negatív folyam kör- és út-folyamok nem-negatív kombinációja.

Alapvető a következő Fordtól és Fulkersontól származó tétel.

TÉTEL 1.1 Akkor és csak akkor létezik k nagyságú megengedett folyam, ha minden S st̄-halmazra δ_{g}(S) ≥ k. Ha e feltétel teljesül, g egészértékű, k pedig egész, úgy a folyam is választható egészértékűnek.

A tételt néha az alábbi ekvivalens alakban említik. (Az MFMC elnevezés az angol Max-flow Min-cut rövidítése.)

TÉTEL 1.2 (MFMC) A megengedett st-folyamok maximális nagysága egyenlő a δ_{g}(S) értékek minimumával, ahol a minimum az összes st̄-halmazra megy. Ha g egészértékű, úgy a maximum egészértékű folyamon is felvétetik.

Az MFMC tételt először racionális g kapacitás függvényre igazoljuk a Ford-Fulkerson növelő utas algoritmus segítségével.

1.1 A NÖVELŐ UTAK MÓDSZERE

Legyen x megengedett folyam. Ekkor tetszőleges S st̄-halmaz esetén ax x folyam nagyságára érvényes az alábbi becslés. δ_{x}(s) = δ_{x}(s) − ϱ_{x}(s) = ∑[δ_{x}(v) − ϱ_{x}(v) : v ∈ S] = δ_{x}(S) − ϱ_{x}(S) ≤ δ_{g}(S). Ebből adódik, hogy az 1.1 tételben a feltétel szükségessége illetve az 1.2 tételben max ≤ min egyenlőtlenség.

Az is megállapíthaó, hogy egy x folyam bizonyosan maximális nagyságú, amennyiben létezik egy olyan S st̄-halmaz, amelyre teljesülnek az alábbi optimalitási feltételek.

(a) x(a) = g(a) minden a élre, amely kilép S-ből, és

(b) x(a) = 0 minden a élre, amely belép S-be.

Jelen célunk egy ilyen x folyam és S halmaz algoritmikus megkeresése. Ezt először csak egészértékű (illetve racionális) g kapacitás függvény esetén tesszük meg, majd tetszőleges g-re.

A Fordtól és Fulkersontól származó algoritmus tetszőleges x megengedett st-folyamból indul ki (például x ≡ 0), és azt iteratívan javítja. Készítsünk el egy D_{x} = (V, A_{x}) digráfot a következőképp. Egy uv él A_{x}-hez tartozik, ha vagy (i) uv ∈ A és x(uv) < g(uv), és ekkor ezen élét D_{x}-nek előre élnek hívjuk, vagy (ii) vu ∈ A és x(vu) > 0, és ekkor uv neve hátra él. Jelölje S az s-ből D_{x}-ben irányított úton elérhető pontok halmazát.

1. eset t ∉ S, azaz t nem érhető el s-ből. Mivel D_{x} semelyik éle sem lép ki S-ből, ezért D-ben minden S-ből kilépő él telített (azaz x(uv) = g(uv)) és minden S-be belépő uv élen x(uv) = 0. Vagyis az (a) és (b) optimalitási feltételek teljesülnek és az algoritmus végetér: az adott x folyam nagysága egyenlő δ_{g}(S)-sel.

2. eset t ∈ S, azaz t elérhető s-ből. Legyen P tetszőleges s-ből t-be vezető irányított út D_{x}-ben.

Legyen Δ_{1} := min{g(uv) − x(uv) : uv előre éle P -nek} és Δ_{2} = min{x(v, u) : uv hátra éle P -nek}. Legyen Δ = min{Δ_{1}, Δ_{2}}. Ekkor Δ pozitív. Nevezzük P egy élét kritikusnak, ha Δ ezen az élen éretik el.

Módosítsuk x-t a következőképp. Ha uv előre éle P -nek, úgy a D uv élén növeljük x(uv)-t Δval. Ha uv hátra éle P -nek, úgy a D vu élén csökkentsük x(vu)-t Δ-val. Könnyen látható, hogy a módosított x′ megengedett folyam lesz, amelynek nagysága Δ-val nagyobb, mint x-é. Következésképp, ha g egészértékű, akkor a 2. eset csak véges sokszor fordulhat elő, vagyis véges sok növelés után az 1. eset következik be, amikor is az algoritmus véget ér. Tehát egész kapacitások esetén az MFMC tétel bizonyítást nyert.

Amennyiben g racionális, a nevezők legkisebb közös többszörösével a kapacitásokat végigszorozva visszajutunk az egész kapacitású esethez. •

Megjegyzendő, hogy ha g irracionális, akkor a fenti eljárás nem biztosan ér véget véges sok lépésben (amint az példával demonstrálható). Másik hátrány, hogy még egész kapacitások esetén is az iterációk száma arányos lehet az előforduló legnagyobb kapacitás nagyságával. Így az algoritmus bonyolultsága az input méretének exponenciális függvényével arányos, azaz nem polinomiális. (Egy szám nagysága a jegyei számának exponenciális függvénye.)

1.1.1 Skálázási technika

Az alábbiakban bemutatunk egy ügyes fogást, amelynek segítségével bizonyos eljárásokat polinomiális futásidejűvé lehet tenni. Használatát a maximális folyam problémán szemléltetjük, mert ott igen egyszerű, de számos alkalommal bonyolultabb körülmények között is használható.

Tételezzük fel, hogy a kapacitások egész számok és kettes számrendszerben vannak megadva. A legnagyobb kapacitás álljon M jegyből. Összesen M darab folyam problémát fogunk megoldani, mindegyikben a megelőzően megkapott maximális folyamot használjuk kiindulási folyamként. Jelölje g_{i} azt a kapcitás függvényt, amely úgy áll elő, hogy minden élen az eredeti kapacitásnak (balról) az első i jegyét tekintjük, míg a többit eltöröljük. Tegyük fel, hogy a g_{i} kapacitás függvényre nézve már meghatároztuk az x_{i} maximális folyamot. Ekkor 2x_{i} megengedett folyam a g_{i+1}-re nézve. A 2x_{i}-ből kiindulva alkalmazzuk a fent leírt növelő út módszert a g_{i+1} kapacitás függvényre vonatkozólag.

Miután minden e élre g_{i+1}(e) értéke vagy 2g_{i}(e) vagy 2g_{i}(e) + 1, legfeljebb élszámnyi növelés után megkapjuk az x_{i+1} maximális folyamot (a g_{i+1}-re nézve). Összesen tehát legfeljebb M|A| növelés segítségével megkonstruáltunk egy eredeti kapacitásokra vonatkozó maximális folyamot.

1.1.2 Legrövidebb növelő utak

A fenti eljárás hátránya, hogy csak egész (és így racionális) kapacitásokra működik. Ezen nehézség leküzdésére J. Edmonds and R. Karp [1972] és E.A. Dinitz [1970] javasolták, hogy minden iterációban a legkisebb élszámú növelő utat válasszuk. Ez az egyszerű megszorítás lehetővé teszi, hogy a Ford-Fulkerson algoritmus bonyolultságát |V | és |A| polinomjával korlátozzuk, függetlenül a kapacitások nagyságától. (Ezt persze úgy értve, hogy a számokkal végzett alapműveleteket egyetlen lépésnek tekintjük.)

TÉTEL 1.3 Ha a Ford-Fulkerson féle növelő utas algoritmusban mindig a legrövidebb növelő utat használjuk, úgy az eljárás tetszőleges g kapacitás függvény esetén legfeljebb O(|V ||A|) növelés után véget ér.

Biz. Jelölje σ_{x}(v) a v távolságát D_{x}-ben s-től. (Ha nincs egyáltalán s-ből v-be út, akkor σ_{x}(v) = ∞). Legyen P egy legrövidebb út D_{x}-ben s-ből t-be. Ekkor P mindegyik uv élére, σ_{x}(v) = σ_{x}(u) + 1.

Lemma 1.4 Amikor P mentén végrehajtunk egy növelést, a σ_{x}(v) érték semmilyen v-re sem csökken.

Biz. Nézzük meg milyen hatással van a növelés a D_{x} segédgráfra. Mivel a folyamot D-nek csak olyan élein változtattuk, melyek P éleinek felelnek meg, D_{x} csupán P éleinél változhat. Éspedig, D′_{x} lehetséges új élei P élei megfordítva, ugyanakkor P kritikus élei (ahol Δ felvétetik) eltűnnek D_{x}-ből. A v pont s-től való távolsága csak akkor csökkenhetne, ha olyan uw éleket adnánk a segédgráfhoz, melyekre σ_{x}(w) > σ_{x}(u) + 1, amiből a lemma következik. •

A növelések sorozatát fázisokra bontjuk. Egy fázis során σ_{x}(t) ugyanaz marad. A lemma szerint legfeljebb |V | − 1 fázis lehetséges.

Lemma 1.5 Egy fázison belül legfeljebb |A| növelésre kerülhet sor.

Biz. Jelölje σ_{i}(v) a v pont távolságát s-től az i fázis kezdetén az aktuális segédgráfban. Nevezzünk egy uv élt i-szorosnak, ha σ_{i}(v) = σ_{i}(u) + 1. Az i-dik fázis során csupán i-szoros éleket használunk. Tudjuk, hogy egy növelés legalább egy i-szoros élt eltüntet az aktuális segédgráfból és nem hoz be új i-szoros élt. Mivel a segédgráfnak legfeljebb |A| darab i-szoros éle van, a lemma következik. •

Mindezeket összetéve kapjuk, hogy legfeljebb |V ||A| növelésre van szükségünk. • •

Ennek alapján megállapíthatjuk, hogy az Edmonds-Karp és Dinitz féle algoritmus össz-bonyolultsága O(|V ||A|^{2}), hiszen egyetlen növelés O(|A|) lépést igényel.

Miután a fenti algoritmus futása során a rendelkezésre álló legrövidebb növelő utak közül bármelyiket választhatjuk, a végül kapott maximális folyam függ ezen választásoktól. Nem így a végső S!

Feladat 1.2 (a) A végül kapott minimális δ^{+}(S) vágás független az algoritmus futásától. (b) Ha X és Y minimalizálja az δ_{g}(Z) értéket az összes st̄-halmazra, akkor X ∩ Y és X ∪ Y is minimalizáló st̄-halmazok. (c) A minimalizáló halmazok metszete S.

Feladat 1.3 Adott e élre hogyan lehet eldönteni, hogy (a) létezik-e olyan maximális folyam, amely telíti e-t, (b) minden maximális folyam telíti e-t.

Feladat 1.4 Algoritmikusan határozzuk meg az összes {x, y} rendezett csúcspárt, amelyre létezik olyan X halmaz, hogy s, x ∈ X, y ∈ V − X és X minimális vágást határoz meg.

Feladat 1.5 Adott két kapacitás függvény esetén algoritmikusan döntsük el, hogy létezik-e olyan S st̄-halmaz, amely miondkét kapacitás-függvényre nézve minimális vágást határoz meg.

Feladat 1.6 Adott c_{1} és c_{2} kapacitás függvények esetén keressünk olyan c_{1}-re nézve minimális st̄- vágást, amely a c_{2}-re nézve a lehető legkisebb.

Feladat 1.7 Készítsünk algoritmust, amely adott költségfüggvényre eldönti, hogy létezik-e k élidegen út s-ből t-be, melyek mindegyike minimális költségű.

Feladat 1.8 Digráfban keressünk két diszjunkt halmazt, melyek egyeki st̄-halmaz, másika ts̄-halmaz, úgy hogy befok összegük minimális.

1.1.3 Kombinatorikus alkalmazások

Ismert, hogy az MFMC tételből könnyen levezethető a Menger tételnek az irányított él- és pontváltozata is. Hasznos megfogalmazni ezeknek az alábbi közös általánosítását.

TÉTEL 1.6 (Menger: pont-él változat) Legyen D = (V, E) digráf és legyenek k, l pozitív egészek. Akkor és csak akkor létezik D-ben kl élidegen út s-ből t-be úgy, hogy minden csúcson legfeljebb l darab út halad keresztül, ha bárhogy kihagyva egy X ⊆ V − {s, t} halmazt (0 ≤ |X| ≤ k − 1), a maradékban minden st̄-halmazból legalább (k − |X|)l él kilép.

Biz. Ha létezik a kívánt útrendszer, akkor ennek legfeljebb |X|l tagja használhat X-beli pontot, tehát a maradék (k − |X|)l darab út D − X-ben halad, és ezért D − X minden st̄-halmazból halmazából legalább (k − |X|)l él kilép, vagyis a feltétel szükséges..

Az elegendőség igazolásához feltehetjük, hogy s-be nem lép be él és tből nem lép ki. Használjuk a szokásos pont széthúzós technikát, azaz minden v ∈ V csúcsot helyettesítsünk két új csúccsal, melyeket jelöljön v′ és v′′. Vezessünk l párhuzamos élt v′-ből v′′-be, törljük s′-t és t′′-t, végül minden uv ∈ E élre vezessünk egy élt u′′-ből v′-be. Az így keletkező D′ = (V′, E′) digráfban legyen a g kapacitás függvény azonosan 1. A tétel feltételéből adódik, hogy minden S′ ⊆ V′ s′′t̄′-halmazra δ′_{g}(S) ≥ kl. Ezért az MFMC tétel miatt létezik kl nagyságú folyam, amely egészértékű. Ez a folyam felbomlik körfolyamokra és kl útfolyamra, amely az eredeti D digráfban a konstrukció miatt kl élidegen útnak felel meg úgy, hogy minden csúcson legfeljebb l halad keresztül. •

Figyeljük meg, hogy az l = 1 speciális esetben az irányított Menger tétel pontidegen változatát kapjuk k darab belsőleg pontidegen st út létezéséről, míg a k = 1 esetben az élidegen változatot l darab élidegen st út létezéséről. (Mivel ilyenkor összesen l élidegen utat keresünk, az a kívánság, hogy minden csúcson legfeljebb csak l haladhat keresztül automatikusan teljesül, így kihagyható.)

TÉTEL 1.7 (Egawa, Kaneko, Matsumoto) Egy D = (V, E) digráf élei akkor és csak akkor színezhetők ki l színnel, hogy mindegyik színben létezzék k belsőleg pontidegen út s-ből t-be, ha bárhogyan kihagyva egy X ⊆ V − {s, t} halmazt (0 ≤ |X| ≤ k − 1), a maradékban minden st̄-halmazból legalább (k − |X|)l él kilép.

Biz. Tekintsük az 1.6 tétel által biztosított kl élidegen utat. Feltehető, hogy a digráfban nincs is más él, mert azokat kitörölhetjük a feltétel megsértése nélkül. Ekkor minden v ∈ V − {s, t} pont befoka megegyezik a kifokával (és legfeljebb l), továbbá s-ből kl él lép ki és t-be kl él lép be.

Készítsük el a következő páros gráfot. Minden v ∈ V −{s, t} csúcsot helyettesítsünk két új csúccsal, melyeket jelöljön v′ és v′′. között. Az s pontot helyettesítsük az s′_{1}, …, s′_{k} új pontokkal, míg t-t a t′′_{1}, …, t′′_{k} pontokkal. Vezessünk l − ϱ(v) = l − δ(v) párhuzamos élt v′ és v′′. Minden uv élre vezessünk uv egy élt u′ és v′′ között. Végül az s-ből kifutó kl darab élt osszuk k darab l-es csoportba tetszőlegesen és az i-dik csoportban lévő l darab sv él mindegyikére kössük össze s_{i}-t v′-vel. Analóg módon a t-be befutó kl élt osszuk k darab l-es csoportba tetszőlegesen és az i-dik csoportban lévő l darab ut él mindegyikére kössük össze u′′-t és t_{i}-t. A keletkező páros gráf minden csúcsa l-ed fokú lesz. Így Kőnig élszínezési tétele miatt ennek éle felbonthatók l darab teljes párosításra. Könnyen ellenőrizhető, hogy egy teljes párosítás éleinek megfelelő élhalmaz az eredeti digráfban k belsőleg pontidegen utat definiál s-ből t-be. •

TÉTEL 1.8 (Folkman - Fulkerson) Egy G = (V, E) páros gráfban akkor és csak akkor létezik l darab élidegen k-élű párosítás, ha V mindegyik X részhalmaza legalább l(k + |X| − |V |) élt feszít.

1.2 AZ ELŐFOLYAM ALGORITMUS

A Ford és Fulkerson által bevezetett növelő utas módszer, illetve annak finomított változata, az Edmonds-Karp-Dinitz algoritmus segítségével erősen polinomiális időben, nevezetesen O(nm^{2}) lépésben meg tudtunk határozni egy s-ből t-be menő maximális nagyságú folyamot és egy minimális vágást, ahol n a csúcsok számát jelöli, m pedig az élekét.

Az alábbiakban bemutatunk egy ettől gyökeresen különböző eljárást, az úgynevezett előfolyam algoritmust, amely minden szempontból felülmúlja a növelő utas módszert. Az eljárás, amely A.

Goldbergtől és R.E. Tarjantól származik, elvileg is és gyakorlailag is hatékonyabb a növelő utas algoritmusnál. Nem használ növelő utakat, nem használ segédgráfot, sőt még folyamokat sem! Mindegyik lépése kicsiny, lokális változtatásból áll (szemben a növelő utas eljárásnak egy egész út mentén történő változtatásával), és helyességének illetve a lépésszámára adott korlátnak bizonyítása egyszerű.

Az eljárás egyik kulcsa az, hogy folyam helyett annak egy relaxációjával dolgozik. A D = (V, E) digráf élhalmazán értelmezett x : E → R_{+} függvényt előfolyamnak nevezzük, ha az s pont kivételével minden v csúcsra γ_{x}(v) ≥ 0, ahol γ_{x}(v) := ϱ_{x}(v) − δ_{x}(v). Egy t-től különböző v csúcsot aktívnak mondunk, ha γ_{x}(v) > 0, míg ha γ_{x}(v) = 0 teljesül, akkor passzívnak. Az x előfolyam akkor folyam, ha minden v ∈ V − {s, t} csúcs passzív. Egy e élt csökkenthetőnek (vagy pozitívnak) mondunk, ha x(e) > 0, és növelhetőnek (vagy telítetlennek), ha x(e) < g(e). (Egy másik lehetséges interpretáció szerint minden v ∈ V − s pontból végtelen kapacitású élt vezetünk t-be. Az így keletkező D′ gráf egy folyama és egy D-beli előfolyam között egy-egy értelműen megfelel egymásnak.)

Az eljárás másik lényegi része, hogy a csúcsokat egy h szintfüggvény segítségével szintekbe soroljuk; az algoritmus során a csúcsok időnként felsőbb szintre lépnek (lejjebb soha). Egy v csúcs aktuális szintjét a h(v) ≥ 0 szám jelzi. Az eljárás során végig h(t) = 0 és h(s) = n, ahol n a csúcsok száma. Emiatt mindig van olyan 0 < i < n érték, amelyre a {v : h(v) = i} szint üres, azaz Egy uv élt nevezzünk felmenőnek illetve lemenőnek annak megfelelően, hogy h(v) > h(u) vagy h(v) < h(u).

Az algoritmus bármely közbenső állapotában adott egy x előfolyam és egy h szint-függvény, melyek a következő illeszkedési feltételeket teljesítik.

1. x(uv) > 0 esetén h(v) ≤ h(u) + 1, azaz csökkenthető él legfeljebb egy szintet lép fel.

2. x(uv) < g(uv) esetén h(v) ≥ h(u) − 1, azaz növelhető él legfeljebb egy szintet lép le.

Másként fogalmazva, felmenő csökkenthető élre h(v) = h(u) + 1, és lemenő növelhető élre h(v) = h(u) − 1. Az ilyen éleket nevezzük feszesnek. Az algoritmus csak feszes éleken fog előfolyamot változtatni. Mielőtt az algoritmust ismertetnénk, megemlítjük az illeszkedési feltételeknek néhány egyszerű következményét.

Lemma 1.9 Ha az x előfolyam kielégíti az illeszkedési feltételeket, úgy egy olyan 0 < i < n indexre, amelyre a {v : h(v) = i} szint üres, az S := {v : h(v) > i} halmazba nem lép be csökkenthető él és S-ből nem lép ki növelhető él. •

Következésképp, ha x történetesen folyam, akkor s ∈ S ⊆ V − t miatt x szükségképpen maximális nagyságú folyam és a lemmabeli S halmaz minimális vágást határoz meg.

Lemma 1.10 Tetszőleges v ≠ t aktív pont szintje legfeljebb 2n − 2.

Biz. Indukcióval könnyen látszik, hogy minden előfolyam előállítható irányított körök és s-ből induló irányított utak (karakterisztikus vektorainak) nemnegatív lineáris kombinációjaként. Ebből adódik, hogy minden aktív pontba vezet s-ből pozitív (azaz csökkenthető) élekből álló irányított út. Mivel az 1. illeskedési feltétel miatt csökkenthető él legfeljebb egy szintet lép fel és minden t-t nem használó egyszerű út legfeljebb n − 2 élből áll, ezért aktív pont szintje legfeljebb n + n − 2. •

1.2.1 Az algoritmus lépései

Kiinduláskor minden v ≠ s csúcsra h(v) = 0, h(s) = n, továbbá x(sv) = g(sv) minden s-ből induló élre, míg az összes többi élre x(e) = 0. Ezen h és x nyilván teljesítik az illeszkedési feltételeket. Az algoritmus minden lépése vagy egyetlen pont szintjének eggyel történő megemelése vagy egyetlen él x-értékének módosítása.

Ha nem létezik aktív csúcs, magyarán az aktuális x előfolyam folyam, akkor az 1.9 lemmában látottak szerint x maximális folyam, és az algoritmus végetér.

Ha létezik aktív csúcs, úgy válasszunk ki egy maximális szintűt és jelöljük z-vel.

A. (Szintemelés) Ha nem létezik sem z-be felmenő csökkenthető él, sem z-ből lemenő növelhető él, akkor helyezzük z-t eggyel magasabb szintre (azaz növeljük meg a h(z) értéket eggyel.)

B. (Előfolyam módosítás)

B1. Ha létezik z-be belépő e = uz feszes él (azaz felmenő csökkenthető él), úgy csökkentsük x(e)-t a min{x(e), γ_{x}(z)} értékkel. B2. Ha létezik z-ből kilépő e = zu feszes él (azaz lemenő növelhető él), úgy növeljük x(e)-t a min{g(e) − x(e), γ_{x}(z)} értékkel.

Két egymást követő szintemelés között végzett tevékenységet nevezzük az algoritmus egy fázisának. Miután csak aktív pontnak emelkedik a szintje és minden aktív pont szintje az 1.10 lemma szerint legfeljebb 2n − 2, szintemelés összesen legfeljebb 2n^{2}-szer fordulhat elő, vagyis legfeljebb 2n^{2} fázis van.

Csak előfolyam módosításkor keletkezhet új aktív pont éspedig a(z aktív) z alatti u pont. Miután mindig maximális szintű aktív pontot választunk, ha ez egyszer passzívá válik, akkor ugyanazon fázis során már az is marad. Így egy fázis alatt minden élen az x-értéket legfeljebb egyszer módosítjuk. Következésképp az algoritmus legfeljebb O(n^{2}m) lépés után végetér.

Jobb lépésszám becslés

Kicsit körültekintőbb becsléssel javíthatunk a korláton. Egy előfolyam módosítást nevezzünk kiegyenlítőnek, ha a minimum γ_{x}(z)-n vétetik fel, azaz a módosítás végrehajtása z-t passzívvá teszi. Ha a módosítás az e = uv élen nem kiegyenlítő, akkor e megszűnik feszesnek lenni. Nevezetesen, ha e felmenő (lemenő) él volt, akkor őrajta az x-érték nullára csökken (g(e)-re nő). Legközelebb csak akkor lehet az e élen módosítás, ha lemenővé (felmenővé) változott, tehát ha a h(u) (illetve h(v)) szint legalább kettővel megemelkedett.

Mivel a legmagasabb szint kisebb, mint 2n, tetszőleges élen az egész algoritmus során legfeljebb 2n nem-kiegyenlítő módosítás fordulhat elő. Így a nem-kiegyenlítő módosítások teljes száma legfeljebb 2nm. Miután egy fázis során kiegyenlítő módosítás legfeljebb n lehet, és a fázisok száma legfeljebb 2n^{2}, kapjuk, hogy a kiegyenlítő módosítások teljes száma legfeljebb 2n^{3}. Ezeket összevetve az algoritmus teljes lépésszámára az O(n^{3}) becslés adódik.

1.3 ÁRAMOK

Legyen f : E → R ∪ {−∞} alsó kapacitás, g : E → R ∪ {+∞} felső kapacitás úgy, hogy f ≤ g. Valamely x : E → R vektorra és S ⊆ V részhalmazra legyen ϱ_{x}(S) := ∑(x(uv) : uv ∈ E, uv belép S-be) és legyen δ_{x}(S) := ϱ_{x}(V − S). Az x vektort áramnak (circulation) nevezzük, ha teljesül a rá megmaradási szabály (conservation rule), azaz ϱ_{x}(v) = δ_{x}(v) fennáll minden v csúcsra. (Figyelem: az f-ben megengedünk −∞ komponenst, ami persze csak annyit jelent, hogy az illető élen az áram értéke nincs alulról korlátozva. Ez azt is jelenti, hogy csak az olyan e élen rendelünk majd az f(e) ≤ x(e) egyenlőtlenséghez duál változót, amelyen az f(e) korlát véges. Analóg módon a g-nek lehetnek +∞ komponensei, de az x áram komponensei mindig valósak. Az f alsó korlátban +∞-t, a g felső korlátban pedig −∞-t nem engedünk meg. Néha előírjuk, hogy az f vagy a g komponensei egészértékűek legyenek; ebbe beleértjük a ±∞-t is.) Az x áramot megengedettnek (feasible) mondjuk, ha

f ≤ x ≤ g.  (1.1)

Gyakorlat 1.9 (a) Igazoljuk, hogy x akkor és csak akkor áram, ha ϱ_{x}(v) ≤ δ_{x}(v) fennáll minden v csúcsra. (b) Ha x áram, akkor ϱ_{x}(Z) = δ_{x}(Z) minden Z ⊆ V részhalmazra is fennáll.

Alapvető az alábbi, Alan Hoffmantól származó tétel.

TÉTEL 1.11 (Alan Hoffman, 1960) Akkor és csak akkor létezik megengedett áram, ha

ϱ_{f}(X) ≤ δ_{g}(X) minden X ⊆ V halmazra.  (1.2)

Továbbá, ha f és g egészértékűek és (1.2) fennáll, akkor létezik egészértékű megengedett áram is.

Biz. (MFMC → Hoffman) Minden v ∈ V csúcsra legyen λ(v) := ϱ_{f}(v) − δ_{f}(v). (Az itt következő levezetésben feltesszük, hogy f, g véges értékű: kis gyakorló feladat az általános eset kezelése.) Ha λ mindenhol nulla, akkor f megengedett áram, és készen vagyunk.

Ha λ nem azonosan nulla, akkor az S = (v : λ(v) > 0) és T = (v : λ(v) < 0) halmazok nem-üresek. Készítsük el a D′ = (V′, A′) digráfot úgy, hogy V′ = V ∪{s, t} és A′ = A∪(s, v) : v ∈ S∪((v, t) : v ∈ T). Definiáljuk a g′ kapacitás függvényt a következőképpen. g′(sv) := λ(v) ha v ∈ S, g′(vt) := −λ(v) ha v ∈ T, és g′(a) := g(a) − f(a) ha a ∈ A. Legyen M = ∑(λ(v) : v ∈ S). A következő lemma a kapcsolatot írja le egyrészt D megengedett áramai és D′ megengedett st folyamai között, másrészt D′ M-nél kisebb vágásai és D (5.1)-et megsértő halmazai között.

Lemma 1.12 (a) Ha x M-nagyságú megengedett st-folyam D′-ben (a g′ kapacitásra vonatkozóan), akkor f + x (az eredeti A-ra megszorítva) megengedett áram.

(b) Ha δ_{g′}(X + s) < M valamely X ⊆ V halmazra, akkor X megsérti a Hoffman féle (1.2) feltételt.

Biz. (a) A megengedettség, azaz f ≤ f +x ≤ g, következik a konstrukcióból. A megmaradási szabály nyilván fennáll V −(S ∪T) pontjaiban. Mivel x nagysága M, minden s-ből kilépő él telített. Így S-nek bármely v pontjára az eredeti gráfban érvényes, hogy x(sv)+ϱ_{x}(v) = δ_{x}(v), azaz ϱ_{f}(v)−δ_{f}(v)+ϱ_{x}(v) = δ_{x}(v), és így ϱ_{f+x}(v) = δ_{f+x}(v), vagyis a megmaradási szabály érvényes S pontjaiban is. A bizonyítás T pontjaira analóg módon végezhető el.

(b) λ(S) = M > δ_{g′}(X +s) = δ_{g−f}(X)+λ(S −X)−λ(T ∩X), amibe λ(S −X) = λ(S)−λ(S ∩X)-t helyettesítve kapjuk, hogy 0 > δ_{g−f}(X) − λ(S ∩ X) − λ(T ∩ X) = δ_{g−f}(X) − λ(X) = δ_{g−f}(X) + δ_{f}(X) − ϱ_{f}(X), vagyis δ_{g}(X) < ϱ_{f}(X). •

Feladat 1.10 Vezessük le Hoffman tételét az MFMC tételből, ha f-nek lehetnek {−∞}, g-nek pedig {+∞} komponensei.

A fenti redukció azt is mutatja, hogy egy maximális folyam illetve minimális vágás meghatározására szolgáló algoritmus segítségével el lehet dönteni, hogy teljesül-e (1.2), és ha igen, akkor tudunk találni megengedett áramot.

Megmutatjuk, hogy Hoffman tételéből könnyen következik az MFMC tétel (nemtriviális iránya). Biz. (Hoffman → MFMC). Jelölje m_{g} a szóbanforgó minimum értékét. (Ez a minimum nyilvánvalóan létezik, merthogy véges sok szám minimumáról van szó. Az viszont még ezen a ponton nem világos, hogy létezik maximális nagyságú folyam.) Adjunk D-hez egy új e = ts élt és definiáljuk f(e) = m_{g}, g(e) := {∞}. Az eredeti éleken legyen f mindenhol nulla.

Könnyen látszik, hogy most (1.2) fennáll, és így az 1.11 tétel szerint létezik megengedett áram (amely ráadásul egészértékű, ha g az). Kihagyva a hozzávett e élt, m_{g} nagyságú folyamot kapunk. •

1.3.1 Hálózati mátrixok

Fontos megjegyezni, hogy a hálózati mátrixokkal megadott poliéderek nemürességének feladata megoldhatók áram problémaként. Legyen D = (V, E) irányított gráf, F feszítő fa és legyen N := E − F a nem-fa élek halmaza. Legyen adott f = (f_{F} , f_{N}) és g = (g_{F} , g_{N}) korlát, melyekre f ≤ g. Jelölje az F -hez tartozó (0, ±1)-es hálózati mátrixot A, míg a D digráf (0, ±1)-es pont-él incidencia mátrixát B. Legyen továbbá x = (x_{F} , x_{N}).

TÉTEL 1.13 A {x : f_{F} ≤ Ax_{N} ≤ g_{F} , f_{N} ≤ x_{N} ≤ g_{N}} poliéder akkor és csak akkor nemüres, ha a {x : Bx = 0, f ≤ x ≤ g) megengedett áram poliéder nemüres.

Biz. Amennyiben x = (x_{F} , x_{N}) áram (azaz Bx = 0), úgy könnyen látszik, hogy x_{F} = Ax_{N}, és persze cx = c_{N}x_{N}. Emiatt f ≤ x ≤ g ekvivalens a f_{F} ≤ Ax_{N} ≤ g_{F} , f_{N} ≤ x_{N} ≤ g_{N} feltételekkel. Fordítva, tegyük fel, hogy x_{N} kielégíti ezen utóbbi egyenlőtlenségeket. Minden e ∈ N nem-fa élhez legyen χ_{e} az (1, a_{e}) vektor, ahol a_{e} az A mátrix e-hez tartozó oszlopa. (Másszóval, χ_{e} az e élhez tartozó C_{e} alapkör 0, ±1-es incidencia vektora.) Ekkor persze χ_{e} áram, és így az x := ∑(x_{N}(e)χ_{e} : e ∈ N) is áram, méghozzá olyan, hogy x(e) = x_{N}(e), ha e ∈ N. Látható, hogy f_{F} ≤ Ax_{N} ≤ g_{F} azzal ekvivalens, hogy f_{F} (e) ≤ x(e) ≤ g_{F} (e) minden e ∈ F élre fennáll. •

Gyakran az áramnál általánosabb fogalmat tekintenek. Például az x vektorra azt írjuk elő, hogy minden v pontra ϱ_{x}(v) − δ_{x}(v) = b(v), ahol b : V → R előre adott vektor. Vagy még általánosabban, adott p : V → R ∪ {−∞}, b : V → R ∪ {∞} esetén (p ≤ b) minden v csúcsra legyen

p(v) ≤ ϱ_{x}(v) − δ_{x}(v) ≤ b(v).  (1.3)

Egy egyszerű fogással azonban ez a feladat áram problémává alakítható. Nevezetesen, vegyünk fel egy új s csúcsot, és D valamennyi pontjából vezessünk egy-egy élt s-be. Egy új vs élen legyen f(vs) := p(v), g(vs) := b(v). Jelölje a kibővített élek halmazát E′. Tetszőleges x : E → R vektorhoz legyen x′ : E′ → R a következőképpen definiálva: x′(e) := x(e) ha e ∈ E, és x′(e) := ϱ_{x}(v) − δ_{x}(v) ha e′ = vs (v ∈ V). Hasonlóképp terjesszük ki f-t és g-t az új élekre: f(us) := p(u), g(us) := b(u). Könnyen látszik, hogy x akkor és csak akkor teljesíti (1.1)-t és (1.2)-t, ha x′ megengedett áram.

Feladat 1.11 Hoffman tételének általánosításaként igazoljuk, hogy akkor és csak akkor létezik az (1.1)-t és (1.3)-t kielégítő x vektor, ha ϱ_{f}(X)−δ_{g}(X) ≤ min(p(X), b(V −X)) fennáll minden X ⊆ V - re.

2003. május 22.umaxfo

KÖLTSÉGES FOLYAMOK ÉS ALKALMAZÁSAIK

Legyen adva D = (V, A) irányított gráf az s forrás- és a t nyelőponttal. Adott még az éleken a g nemnegatív kapacitás függvény és a c nemnegatív költségfüggvény. Feltesszük, hogy g egészértékű. Korábban már láttuk, hogy miként lehet egy maximális M nagyságú s-ből t-be vezető folyamot polinom időben kiszámítani. Most minden 0 és M közé eső k egészre szeretnénk találni egy olyan k nagyságú folyamot, melynek költsége minimális. Egy z folyam költségét a cz = ∑(c(e)z(e) : e ∈ A) skaláris szorzattal definiáljuk. Azt mondjuk, hogy a z st-folyam minimális költségű folyam, ha z a legkisebb költségű a megengedett, z-vel azonos nagyságú st-folyamok közül.

2.1 Minimális költségű folyam algoritmus

Az alábbiakban ismertetjük Ford és Fulkerson [1962] algoritmusát. Legyen π : V → Z_{+} olyan függvény a V -n, amelyre π(s) = 0 ≤ π(v) ≤ π(t) minden v ∈ V -re. Ilyen függvényt potenciálnak hívunk. Használni fogjuk a következő jelölést. c̄(uv) = c(uv) − π(v) + π(u), ahol uv ∈ A. Potenciálok segítségével egy z folyam cz költségére az alábbi alsó korlátot nyerhetjük.

∑ c(uv)z(uv) = ∑(π(v) − π(u))z(uv) + ∑ c̄(uv)z(uv) = π(t)k + ∑(c̄(uv)z(uv) : c̄(uv) < 0) + ∑(c̄(uv)z(uv) : c̄(uv) > 0) ≥ π(t)k + ∑ c̄(uv)g(uv) + 0.

Ebből következik, hogy egy z folyam bizonyosan minimális költségű, amennyiben létezik olyan π potenciál, amelyre az egyenlőtlenség egyenlőséggel teljesül. Ez pontosan akkor van így, ha fennáll a következő két optimalitási feltétel.

π(v) − π(u) < c(uv) ⇒ z(uv) = 0,  (i)
π(v) − π(u) > c(uv) ⇒ z(uv) = g(uv).  (ii)

[Tetszőleges π potenciálra a π(v) − π(u) potenciál különbség egy semleges költségfüggvényt definiál az élhalmazon abban az értelemben, hogy minden k nagyságú folyamnak ugyanaz a költsége, éspedig k(π(t) − π(s)). Így, ha a c költségfüggvényt egy potenciál különbséggel eltoljuk, akkor a kapott c̄(uv) := c(uv)−(π(v)−π(u)) költségfüggvény ekvivalens az eredetivel. Ennek alapján az optimalitási feltételeket úgy is lehet interpretálni, hogy egy z folyam akkor és csak akkor minimális költségű, ha létezik egy olyan c̄ ekvivalens költségfüggvény, amely ha egy uv élen pozitív, úgy a folyam a minimumon van, azaz z(uv) = 0, míg ha c̄(uv) negatív, úgy a folyam a maximumon van, azaz z(uv) = g(uv).]

Ford és Fulkerson módszere a maximális folyam kiszámítására vonatkozó Ford-Fulkerson algoritmus finomításának tekinthető. Minden lehetséges egész k értékre megkonstruálunk egy minimális költségű k nagyságú folyamot. Az eljárás az azonosan nulla folyammal és az azonosan nulla potenciállal indul. Ezután a folyam nagyságát növeljük egyenként, illetve menetközben néha a potenciált növeljük úgy, hogy az optimalitási feltételek végig fennállnak. Az algoritmus akkor ér véget, amikor maximális nagyságú folyamot illetve egy minimális vágást kaptunk.

ITERATÍV LÉPÉS Az általános helyzetben adott a z folyam és a π potenciál, és ezek kielégítik az (i) és (ii) feltételeket. Megkonstruálunk egy D′ = (V, A′) segédgráfot a következőképpen. D′-nek kétféle éle van: előre és hátra. Egy uv él előre él, ha uv ∈ A, c̄(uv) = 0 és z(uv) < g(uv). Egy uv él hátra él, ha vu ∈ A, c̄(vu) = 0 és z(vu) > 0.

Legyen S az s-ből D′-ben irányított úton elérhető pontok halmaza. Két eset lehetséges.

1. Eset t ∉ S, azaz t nem elérhető s-ből.

Legyen ε_{1} = min(c̄(uv) : uv ∈ δ^{+}(S), z(uv) < g(uv)) és ε_{2} = min(−c̄(uv) : uv ∈ δ^{+}(V −S), z(uv) > 0), ahol az üres halmazon vett minimumot ∞-nek definiáljuk. Legyen ε = min(ε_{1}, ε_{2}). Az optimalitási feltételek és az S definíciója miatt ε pozitív.

Amennyiben ε = ∞, akkor az algoritmus végetér. Ebben az esetben az S-ből kilépő eredeti élek mind telítettek, míg az S-be belépő eredeti élek mindegyikén a folyam nulla. Így tehát δ_{g}^{+}(S) = val(z), az aktuális z folyam maximális nagyságú és az S-ből kilépő élek halmaza minimális vágást határoz meg.

Legyen most ε < ∞, és módosítsuk π-t úgy, hogy minden v ∈ V − S-re növeljük π(v)-t ε-nal. Az S és az ε definíciójából rögtön kapjuk:

Állítás 2.1 A módosított potenciál és a változatlanul hagyott z folyam kielégíti az optimalitási feltételeket.

Készítsük el az új segédgráfot és ismételjük meg az eljárást. Figyeljük meg, hogy a segédgráfban a régi S által feszített élek változatlanok maradnak és ezért az s-ből elért pontok halmaza szigorúan bővebb lesz, mint S. Ezért az 1. eset legfeljebb |V |−1-szeri előfordulása után biztosan vagy az ε = ∞ következik be, vagypedig az alábbi 2. eset.

2. Eset t ∈ S, vagyis t elérhető s-ből. Legyen P a D′-ben egy s-ből t-be vezető irányított út. Módosítsuk z-t a következőképpen. Legyen z′(uv) = z(uv) + 1, ha uv a P -nek előre éle és legyen z′(uv) = z(uv) − 1, vu a P -nek hátra éle.

A módosításból adódik:

Állítás 2.2 A módosított folyam és változatlanul hagyott potenciál kielégíti az optimalitási feltételeket.

Ezzel az algoritmus leírását be is fejeztük. Mi mondható az eljárás futásidejéről? Lényegében M darab növelésre van szükségünk (2. eset), így az eljárás polinomimális, amennyiben mind az M minimális költségű folyamot meg kell határoznunk.

Elképzelhető persze olyan helyzet is, amikor például csak egy maximális nagyságú minimális költségű folyamot kell kiszámítanunk. Ebben az esetben az algoritmus természetesen nem biztosan polinomiális, hiszen lépésszáma az M nagyságával arányos. De még ebben az esetben is két fontos speciális eset kezelhető.

Ha a legnagyobb kapacitás nem túlságosan nagy (nevezetesen, ha |V | polinomjával korlátozható), akkor a fenti eljárás nyilván polinomiális, függetlenül attól, hogy a c költség-függvény egészértékű-e vagy sem.

Tegyük most fel, hogy a kapacitások tetszőlegesek, a költség-függvény egészértékű és ”kicsi”. Ekkor az algoritmus következő módosítása erősen polinomiális algoritmust eredményez. Tekintsük az algoritmus egy közbenső helyzetét, amikor egy π potenciál rendelkezésre áll. A szoros élek digráfjában (egy uv él szoros, ha c̄(uv) = 0) számítsunk ki (a Max-flow Min-cut algoritmusssal) egy maximális nagyságú z folyamot és egy S minimális ki-kapacitású st̄-halmazt. Ha D-ben minden S-be belépő és S-ből kilépő él szoros, akkor S minimális vágást határoz meg és az aktuális z folyam maximális nagyságú, amely kielégíti az optimalitási feltételeket. Ebben az esetben az algoritmus véget ér.

Amennyiben D-nek létezik nem-szoros éle, amely S-be be- vagy kilép, akkor ε, ahogy azt fentebb az 1. esetnél kiszámítottuk, véges lesz. Módosítsuk π-t úgy, mint az előbb, azaz minden v ∈ V − S-re növeljük π(v)-t ε-nal.

Azt állítjuk, hogy a π(t) érték a D digráf valamely (irányítatlan értelemben vett) s-ből t-be vezető útjának a költsége. Valóban, minden folyam-növeléskor a segédgráfban van olyan st út, amely szoros élekből áll.

Következik, hogy a különböző π(t) értékek száma (vagyis az 1. eset előfordulásainak száma) felülről korlátozható az élek össz-költségével. Tehát az eljárás polinomiális, ha a c egészértékű és legnagyobb értéke |V | polinomjával korlátozható.

2003. május 22.uminfo

2.2 Részbenrendezett halmazok láncai és antiláncai

Legyen P = {p_{1}, …, p_{n}} részbenrendezett halmaz. Egy lánc elemszámát néha a lánc hosszának nevezik. A leghosszabb lánc hossza a részbenrendezett halmaz magassága. A legnagyobb antilánc elemszáma részbenrendezett halmaz szélessége.

2.2.1 A Dilworth tétel és polárisa

Először a magasságra és a szélességre vonatkozóan két fontos tételt bizonyítunk. Az első meglehetősen egyszerű (néha a Dilworth tétel polárisának hívják):

TÉTEL 2.3 (poláris Dilworth) A P -t fedő antiláncok minimális c száma egyenlő a leghosszabb lánc hosszával, vagyis P magasságával.

Biz. Világos, hogy max ≤ min. Az egyenlőség igazolásához jelölje A_{1} a minimális elemek halmazát. Ez nyilván antilánc. Jelölje c′ a P′ := P − A_{1} magasságát. Indukcióval P′ felbontható c′ darab antiláncra, így P felbontható c′ + 1 darab antiláncra. Másrészt P′ bármely eleme nagyobb, mint A_{1} valamelyik eleme, és ezért P′ bármely lánca megnövelhető egy A_{1}-beli elemmel, vagyis P -ben van c′ + 1 elemű lánc. •

A fenti induktív bizonyítás könnyen algoritmussá alakítható, amely megtalál egy antilánc felbontást és egy láncot, melyekre egyenlőség áll.

Legyen A_{1} a P minimális elemeinek halmaza. Legyen A_{2} az A_{1} elhagyása után a minimális elemek halmaza. Ezt folytatva megkonstruáljuk az A_{1}, …, A_{c} antiláncokból álló felbontását P -nek. Most visszafelé haladva előállítunk egy c elemből álló láncot. Legyen a_{c} az A_{c} antilánc tetszőleges eleme. Az a_{c} elem nem került bele A_{c−1}-be, ezért van A_{c−1}-nek egy a_{c}-nél kisebb a_{c−1} eleme. Ez az elem nem került A_{c−2}-be, tehát van A_{c−2}-ben egy a_{c−2} elem, amely kisebb, mint a_{c−1}. Ezt az eljárást folytatva, megkapunk egy c elemű láncot.

Feladat 2.1 Igazoljuk, hogy egy legalább kl + 1 tagú számsorozatban vagy van k + 1 tagú monoton növő rész-sorozat, vagy van l + 1 tagú szigorúan monoton csökkenő rész-sorozat. Előfordulhat-e, hogy mind a két rész-sorozat létezik?

Érvényes tételt kapunk, ha a 2.3 tételben a lánc és antilánc szavakat felcseréljük:

TÉTEL 2.4 (Dilworth) A P -t fedő láncok minimális a száma egyenlő a legnagyobb antilánc elemszámával, vagyis P szélességével.

Biz. A max ≤ min egyenlőtlenség ismét nyilvánvaló. A fordított irány igazolásához készítsünk el egy G = (X, Y; E) páros gráfot, melynek mindkét osztálya a P halmaznak felel meg és valamely x_{i} elem y_{j}-vel akkor van összekötve, ha p_{i} > p_{j}. (x_{i} NINCS összekötve y_{i}-vel.)

Lemma 2.5 G tetszőleges M párosításának megfelel P -nek egy n − |M| láncból álló felbontása.

Biz. Tekintsük a B halmaz M által fedetlen pontjait. Ezek száma n − |M|. Legyen x_{i} olyan pont, amelyet M nem fed. Mindegyik ilyen x_{i} elemhez megkonstruálunk egy C_{i} láncot, a következőképpen. Ha y_{i} fedetlen, akkor C_{i} álljon az egyetlen p_{i} elemből. Ha y_{i}-t fedi valamely M-beli x_{j}y_{i} él, akkor p_{j} > p_{i}, és legyen p_{j} a lánc következő eleme. Ha y_{j}-t fedi valamely M-beli x_{k}y_{j} él, akkor legyen p_{k} a lánc következő eleme. Így folytatva, a láncot addig növeljük, amig a lánchoz utolsónak vett p_{m} elemhez tartozó y_{m} csúcsot már nem fedi M-beli él.

Íly módon az M által nem fedett n−|M| darab X-beli csúcs mindegyikéhez definiáltunk egy láncot P -ben. A lemma következik abból, hogy az így kapott láncok páronként diszjunktak és lefedik P -t. •

Lemma 2.6 Legyen S ⊆ X ∪ Y a páros gráf éleinek minimális lefogása. Ekkor P -ben van olyan A antilánc, ameyre |S| + |T | = n.

Biz. Először belátjuk, hogy ha x_{i} ∈ S, akkor y_{i} ∉ S. Ha indirekt mindkét csúcs S-ben volna, akkor S minimalitása miatt a gráfnak létezne olyan x_{i}y_{j} illetve x_{k}y_{i} éle, melyekre y_{j}, x_{k} ∉ S. Ekkor tehát p_{k} > p_{i} > p_{j}, amiből p_{k} > p_{j}, és így x_{k}y_{j} éle a gráfnak. Ezt az élt viszont nem fogja le S, amely ellentmondás azt bizonyítja, hogy valóban nem lehet x_{i} és y_{i} mindegyike S-ben.

Legyen most A := {p_{i} : x_{i} ∉ S, y_{i} ∉ S}. Rögtön látszik, hogy az A halmaz kielégíti a lemma követelményeit. •

A két lemmát felhasználva Dilworth tétele rögtön következik a Kőnig tételből, ami szerint egy páros gráfban a független élek maximális száma egyenlő az éleket lefogó pontok minimális számával. • •

2.2.2 Közös általánosítás

A fenti két tételnek megadjuk egy közös általánosítását. Valamely B= {B_{1}, B_{2}, …, B_{k}} családra használjuk az ∪B = ∪(B_{i} : i = 1, …, k) jelölést. A C_{γ} = {C_{1}, C_{2}, …, C_{γ}} lánc-családon γ darab diszjunkt nemüres láncból álló családot értünk. Jelölje C_{γ} a γ láncból álló lánc-családok halmazát, míg C az összes lánc-családot magába foglaló halmazt. Legyen c_{γ} = max | ∪ C_{γ}| : C ∈ C_{γ}, vagyis c_{γ} a legnagyobb halmaz elemszáma, amely előáll γ lánc egyesítéseként (azaz a Dilworth tétel alapján nem tartalmaz γ-nál nagyobb elemszámú antiláncot).

Az A_{α} = {A_{1}, A_{2}, …, A_{α}} antilánc-családon α darab diszjunkt nemüres antiláncból álló családot értünk. Jelölje A_{α} az α antiláncból álló antilánc-családok halmazát, míg A az összes antilánc-családot magában foglaló halmazt. Legyen a_{α} = max | ∪ A_{α}| : A_{α} ∈ A_{α}, vagyis a_{α} a legnagyobb halmaz elemszáma, amely előáll α antilánc egyesíteseként (azaz a poláris Dilworth tétel alapján nem tartalmaz α-nál nagyobb elemszámú láncot).

Dilworth tétele szerint c_{a} = n, a poláris tétel szerint a_{c} = n. Mi mondható c_{γ}-ról (1 ≤ γ ≤ a) és a_{α}-ról (1 ≤ α ≤ c)?

TÉTEL 2.7 (Greene és Kleitman, 1976) a_{α} = min{qα + |P − ∪C_{q}| : C_{q} ∈ C}.

TÉTEL 2.8 (Greene, 1976) c_{γ} = min{qγ + |P − ∪A_{q}| : A_{q} ∈ A}.

Miután egy láncnak és egy antiláncnak legfeljebb egy közös eleme lehet, a_{α} és c_{γ} legfeljebb akkora, mint a szóbanforgó minimum.

DEFINÍCIÓ Az A_{α} = {A_{1}, A_{2}, …, A_{α}) antilánc-család és a C_{γ} = {C_{1}, C_{2}, …, C_{γ}} lánc-család ortogonális, ha

P = (∪A_{α}) ∪ (∪C_{γ})  (2.1)

és

A_{i} ∩ C_{j} ≠ ∅ hacsak 1 ≤ i ≤ α, 1 ≤ j ≤ γ,  (2.2)

azaz a lánc-család és az antilánc-család együttesen lefedi P -t és mindegyik A_{i} antilánc metszi az összes C_{j} láncot.

A 2.7 és 2.8 tételek nemtriviális részeit átfogalmazhatjuk az alábbiak szerint.

TÉTEL 2.9 Minden α-ra, 1 ≤ α ≤ c, létezik A_{α} ∈ A_{α} és C_{γ} ∈ C, valamely γ-ra, amelyek ortognálisak.

TÉTEL 2.10 Minden γ-ra, 1 ≤ γ ≤ a, létezik C_{γ} ∈ C_{γ} és A_{α} ∈ A, valamely α-ra, melyek ortogonálisak.

A két tétel közös általánosítása így hangzik.

TÉTEL 2.11 A P = {p_{1}, …, p_{n}} részbenrendezett halmaz szélessége legyen a, magassága c. Létezik egy olyan C_{a}| A_{1}, A_{2}, …, A_{i_{1}}| C_{a−1}, C_{a−2}, …, C_{a−j_{1}}| A_{i_{1}+1}, …, A_{i_{2}}| C_{a−j_{1}−1}, …, C_{a−j_{2}}| … sorozat, amely a C_{a}, C_{a−1}, …, C_{1} és az A_{1}, A_{2}, …, A_{c} sorozatok összefésülésével keletkezik, ahol C_{j} ∈ C_{j} és A_{i} ∈ A_{i}, és a sorozat bármely tagjára (akár C_{j}, akár A_{i}) fennáll, hogy ortogonális az utolsó őt megelőző ellentétes típusú tagra. (Vagyis, A_{1}, A_{2}, …, A_{i_{1}} ortogonális C_{a}-ra, C_{a−1}, C_{a−2}, …, C_{a−j_{1}} mindegyike ortogonális A_{i_{1}}-re, stb.)

Biz. Feleltessünk meg P -nek egy D = (V, A) irányított gráfot, ahol V := {s, t, x_{1}, x_{2}, …, x_{n}, y_{1}, y_{2}, …, y_{n}}, és A := {(s, x_{i}) : i = 1, 2, …, n} ∪ {(y_{i}, t) : i = 1, 2, …, n} ∪ {x_{i}y_{j} : ha p_{i} ≥ p_{j}}. Legyen minden e él kapacitása g(e) ≡ 1, míg a költsége c(e) = 1, ha e = x_{i}y_{i} és 0 különben.

Alkalmazzuk a Ford és Fulkerson féle minimális költségű folyam algoritmust. Legyen z és π az algoritmus egy közbenső állapotához tartozó folyam illetve potenciál. Ekkor z 0−1-értékű, π nemnegatív, π(s) = 0 és kielégítik a következő optimalitási feltételeket.

π(v) − π(u) < c(uv) ⇒ z(uv) = 0,  (i)
π(v) − π(u) > c(uv) ⇒ z(uv) = g(uv).  (ii)

Írjuk fel, hogy a különféle élekre mit jelentenek az optimalitási feltételek. x_{i}y_{i} típusú élre:

π(y_{i}) − π(x_{i}) < 1 ⇒ z(x_{i}y_{i}) = 0,  (i)
π(y_{i}) − π(x_{i}) > 1 ⇒ z(x_{i}y_{i}) = 1.  (ii)

x_{i}y_{j} típusú élre (tehát amikor p_{i} > p_{j}):

π(y_{j}) − π(x_{i}) < 0 ⇒ z(x_{i}y_{j}) = 0,  (i)
π(y_{j}) − π(x_{i}) > 0 ⇒ z(x_{i}y_{j}) = 1.  (ii)

sx_{i} típusú élre:

π(x_{i}) < 0 ⇒ z(sx_{i}) = 0,  (i)
π(x_{i}) > 0 ⇒ z(sx_{i}) = 1.  (ii)

y_{i}t típusú élre:

π(y_{i}) > π(t) ⇒ z(y_{i}t) = 0,  (i)
π(y_{i}) < π(t) ⇒ z(y_{i}t) = 1.  (ii)

Lemma 2.12 Minden i = 1, …, n-re

π(y_{i}) ≤ π(x_{i}) + 1.  (2.3)

Biz. Az (2.3) fennáll az algoritmus kezdetén. A folyamnövelési lépés nem befolyásolja (2.3)-t, egy potenciálcsere pedig csak akkor ronthatja el, ha a csere előtt π(y_{i}) = π(x_{i}) + 1 állt és x_{i} elérhető volt a D′ segédgráfban, miközben y_{i} nem. Ebben az esetben π′(y_{i}) = π′(x_{i}) + 2 érvényes a módosított π′ potenciálra. Az (ii) feltétel (ha π′-re alkalmazzuk) maga után vonja, hogy z(x_{i}y_{i}) = 1. Ezért z(sx_{i}) = 1 és a D′ segédgráfnak az egyetlen x_{i}-be lépő éle y_{i}x_{i}. De ez ellentmond az indirekt feltevésnek, hogy x_{i} elérhető, míg y_{i} nem. •

Lemma 2.13 Ha p_{i} > p_{j} és z(x_{i}y_{j}) = 1, akkor π(x_{i}) = π(y_{j}).

Biz. Az (i) feltétel alapján a π(y_{j}) ≥ π(x_{i}) egyenlőtlenség végig érvényben van, és az algoritmus indításakor egyenlőség áll. Ha egy potenciálcsere elrontaná ezt, akkor π′(y_{j}) = π′(x_{i}) + 1 állna a módosított π′ potenciálra, és x_{i} elérhető volna D′-ben az s-ből, miközben y_{j} nem. De ez nem lehetséges, mivel y_{j}x_{i} az egyedüli él D′-ben, amely belép x_{i}-be.

Egy folyamcsere csak akkor ronthatja el π(x_{i}) = π(y_{j})-t, ha az aktuális (:= 0) folyamértéket az x_{i}y_{j} élen 1-gyel megnöveli. De ekkor x_{i}y_{j} éle D′-nek és emiatt π(y_{i}) − π(x_{j}) = c(x_{i}y_{j}) = 0. •

Jelölje P′ azon p_{h} elemek halmazát, melyekre z(x_{h}y_{h}) = 0. Ekkor a Dilworth tétel bizonyításában látottakhoz hasonlóan azon x_{i}y_{j} (i < j) élek halmaza, melyekre z(x_{i}y_{j}) = 1, megfelel egy C_{γ} lánccsaládnak, ahol γ = n − val(z), és ez a lánc-család a P′ partícióját adja. α := π(t)-re definiáljunk egy A_{α} = {A_{1}, A_{2}, …, A_{α}} családot, ahol A_{i} = {p_{j} : π(x_{j}) + 1 = π(y_{j}) = i}.

Lemma 2.14 A_{α} antilánc-családot alkot, amely ortogonális C_{γ}-ra.

Biz. Először mutassuk meg, hogy mindegyik A_{i} antilánc. Valóban, ha indirekt p_{m}, p_{j} ∈ A_{i} valamely p_{m} > p_{j} elemekre, akkor π(y_{j}) − π(x_{m}) = 1, és ezért (ii) alapján, z(x_{m}, y_{j}) = 1, ellentétben a 2.13 lemmával.

(2.1) igazolása érdekében legyen p_{m} olyan elem, amely nincs P′ = ∪C_{γ}-ban, ami azzal ekvivalens, hogy z(x_{m}, y_{m}) = 1. Ekkor (i) miatt π(y_{m}) − π(x_{m}) ≥ 1, így a 2.12 lemma miatt π(y_{m}) − π(x_{m}) = 1. Vagyis π(y_{m})-t i-vel jelölve p_{m} ∈ A_{i}, tehát (2.1) fennáll.

Igazoljuk végül, hogy A_{i} ∩C_{j} ≠ ∅ (1 ≤ i ≤ α, 1 ≤ j ≤ γ). Álljon a C_{j} lánc mondjuk a p_{1} > … > p_{k} elemekből (k ≥ 1). Ekkor z(y_{1}t) = 0, így (ii) miatt π(y_{1}) ≥ π(t), amiből persze π(y_{1}) = π(t) = α. Hasonlóan z(sx_{k}) = 0, így (i) miatt π(x_{k}) ≤ 0, amiből π(x_{k}) = 0. A 2.13 lemmából kapjuk, hogy π(x_{1}) = π(y_{2}), π(x_{2}) = π(y_{3}), …, π(x_{k−1}) = π(y_{k}). Ezt a 2.12 lemmával összevetve kapjuk, hogy a 0 = π(x_{k}), π(y_{k}), π(y_{k−1}), π(y_{k−2}), …, π(y_{1}) = α egész számokból álló sorozat olyan, hogy minden tagja legfeljebb eggyel nagyobb a megelőzőnél. Íly módon minden i-re (1 ≤ i ≤ α) kell olyan m indexnek lennie, amelyre π(x_{m}) = π(y_{m}) + 1 = i. Vagyis p_{m} ∈ C_{j} ∩ A_{i}.

Tegyük most fel, hogy a minimális költségű folyamot kiszámító algoritmus a következőképpen futott le. Kiindulva a π azonosan nulla potenciálból és a z azonosan nulla folyamból, a folyam nagysága egyenként k_{0}-ig nő, a potenciál nagysága (ami definíció szerint a π(t) érték) egyenként i_{1}-ig, azután ismét a folyam nagysága k_{1}-ig, …, stb. Végül a folyam nagysága k_{s}-re, a potenciál nagysága i_{s}-re nő. Az algoritmus a maximális nagyságú folyam elérésekor ér véget, amely nagyság esetünkben n, azaz k_{s} = n.

Legyen a := n − k_{0} és j_{i} := k_{i} − k_{0} (i = 1, 2, …, s). Az utolsó lemma alapján az algoritmus (k_{0}, 1) paraméterekkel jellemzett fázisához a C_{a} a tagú lánc-család és az A_{1} egytagú antilánc-család tartozik, melyek ortogonálisak egymásra. Ezután a potenciál nagysága, mint már említettük, egyenként i_{1}-re nő. A közbenső helyzetekhez tartozó A_{2}, A_{3}, …, A_{i_{1}} antilánc-családok ortogonálisak a változatlan C_{a}- ra. Ezután a folyam értéke egyenként k_{1}-re nő. A közbenső helyzetekhez tartozó C_{a−1}, C_{a−2}, …, C_{a−j_{1}} lánc-családok ortogonálisak a változatlan A_{i_{1}}-re, és így tovább. Ezzel a tétel bizonyítását és az algoritmus ismertetését befejeztük. • •

Feladat Dilworth után nevezzünk egy maximális (azaz a elemszámú) antiláncot D-antiláncnak. Igazoljuk, hogy a diszjunkt D-antiláncok maximális száma egyenlő a D-antiláncokat lefogó elemek minimális számával. (Segítség: Tekintsük a 2.11 tételben leírt sorozat A_{i_{1}}| C_{a−1} tagjait.)

file: lgreen 2003. május 22.

PÁROSÍTÁSOK

3.1 PÁROS GRÁFOK

3.1.1 Maximális elemszámú párosítások

Az egész elmélet kiindulópontja Kőnig klasszikus tétele.

TÉTEL 3.1 (Kőnig Dénes) Egy G = (S, T; E) páros gráfban a diszjunkt élek maximális ν = ν(G) száma egyenlő az éleket lefogó pontok minimális τ = τ(G) elemszámával.

Biz. Egy ν elemű párosítás lefogásához kell legalább ν csúcs, így az összes élhez is kell, ezért ν ≤ τ. Ebből az is következik, hogy (∗) egy ν elemű L lefogás egy ν elemű párosítás minden élét pontosan egyszer fogja le.

A fordított irányhoz lássuk be, hogy G élei lefoghatók ν(G) ponttal. Indirekt, legyen G minimális ellenpélda abban az értelemben, hogy ν(G) < τ(G), de minden G-nél kisebb G′ gráfra ν(G′) = τ(G′).

Minden u csúcsot elkerül maximális párosítás, mert ha valamelyiket nem, úgy ν(G − u) < ν(G), és miután G − u élei már lefoghatók ν(G − u) ≤ ν(G) − 1 ponttal, ezen lefogáshoz u-t hozzávéve G éleinek egy legfeljebb ν(G) elemű lefogását kapnánk.

Legyen e = st a gráf egy éle, melyre s ∈ S, t ∈ T. A G − e éleinek létezik ν(G) elemű L := A ∪ B lefogása, ahol A ⊆ S, B ⊆ T. Az L nem fogja le e-t, mert különben G éleinek is ν(G) elemű lefogása volna. G − s-nek van ν(G) elemű párosítása, amelynek B-t fedő M_{B} része (∗) miatt nem fedi A egyetlen pontját sem. G − t-nek van ν(G) elemű párosítása, amelynek A-t fedő M_{A} része (∗) miatt nem fedi B egyetlen pontját sem. De most M_{A} ∪ M_{B} ∪ {e} párosítása G-nek, melynek elemszáma |A| + |B| + 1 = ν(G) + 1, ellentmondás. •

A most következő algoritmikus bizonyítás lényegében Kőnig eredeti bizonyítása kicsit algoritmikusabb nyelven elmondva. (Kőnig nem tekintette explicit azt a kérdést, hogy miként lehet megtalálni a szóbanforgó alternáló utakat, de a bizonyításából ez közvetlenül kiolvasható.)

Algoritmikus bizonyítás.

A nemtriviális ν ≥ τ irány igazolásához konstruálunk egy M párosítást és egy L lefogást, melyek elemszáma ugyanaz. Az eljárás tetszőleges M párosításból indul ki, ami kezdetben az üres halmaz is lehet. Az általános lépésben vagy találunk egy nagyobb párosítást, és ekkor a nagyobb párosításra vonatkozóan iteráljuk az eljárást, vagy pedig egy |M|-mel megegyező elemszámú lefogást, amikoris az algoritmus véget ér.

Irányítsuk meg M éleit T -től S felé, míg az összes többi élt fordítva. Jelölje R_{S} illetve R_{T} az S-ben illetve a T -ben az M által fedetlen pontok halmazát. Jelölje Z az R_{S} pontjaiból az így kapott irányított gráfban irányított úton elérhető pontok halmazát (amit például szélességi kereséssel találhatunk meg).

Két eset lehetséges. Amennyiben R_{T} -nek esik pontja Z-be, akkor megkaptunk egy olyan R_{S}-t és R_{T} -t összekötő P utat, amely M-ben alternál. Most M és P szimmetrikus differenciája egy Mnél eggyel több élből álló M′ párosítás. (Technikailag az eljárást nagyon egyszerű végrehajtani: a megtalált út éleinek irányítását egyszerűen megfordítjuk.)

A másik esetben R_{T} diszjunkt Z-től. Z definíciója folytán Z-ből nem lép ki irányított él. Érvényes továbbá, hogy Z-be nem lép be megirányított uv ∈ M párosítás él, hiszen v csak u-n keresztül érhető el, így v csak akkor lehetett irányított úton elérhető R_{S}-ből, ha u is az volt.

Következik, hogy az L := (T ∩ Z) ∪ (S − Z) halmaz egyrészt lefogja az összes élt, másrészt minden M-beli élnek pontosan az egyik végpontját tartalmazza, tehát |M| = |L|. •

A fenti bizonyítás egyúttal hatékony algoritmust is jelent a szóbanforgó optimumok meghatározására. A lépésszám megbecsléséhez figyeljük meg, hogy legfeljebb n/2 alkalommal kell utat keresnünk. Miután egyetlen út megkeresése az élszámmal arányos időben történhet, az összlépésszám nem nagyobb, mint O(nm) (ahol n a gráf pontszáma, míg m az élszáma).

A Kőnig tételhez szorosan kapcsolódik Hall tétele.

TÉTEL 3.2 Egy G = (S, T; E) páros gráfban akkor és csak akkor létezik S-t fedő párosítás, ha teljesül a Hall-féle feltétel:

|Γ(X)| ≥ |X| minden X ⊆ S részhalmazra,  (3.1)

ahol Γ(X) jelöli azon T -beli pontok halmazát, melyeknek van szomszédja X-ben.

A tételt rögtön kicsit általánosabb alakban igazoljuk. Definiáljuk egy X ⊆ S halmaz hiányát a h(X) := (|X| − |Γ(X)|) értékkel és legyen μ = μ(G, S) a maximális hiány, azaz

μ := max_{X⊆S} h(X)  (3.2)

TÉTEL 3.3 Egy G = (S, T; E) páros gráfban egy párosítás által nem fedett S-beli pontok minimális száma egyenlő μ-vel.

Biz. A max ≤ min egyenlőtlenség nyilván fennáll. A fordított irány igazolásához legyen M egy maximális (azaz ν elemű) párosítás és L egy minimális (azaz τ = ν elemű) lefogás. Legyen X := S−L. Ekkor M pontosan |S| − ν elemét nem fedi S-nek. Másrészt Γ(X) ⊆ L − S és így |X| − |Γ(X)| ≥ |S − L| − |L − S| = |S| − |L| = |S| − τ = |S| − ν. •

Legyen F az S maximális (azaz μ) hiányú részhalmazainak rendszere, vagyis F := {X ⊆ S : |X| − |Γ(X)| = μ}. Az F tagjait röviden max-hiányú halmazoknak fogjuk hívni. Az előbbi bizonyítás mutatja, hogy egy-egy értelmű kapcsolat áll fenn a minimális lefogások és a max-hiányú S-beli halmazok között: Ha L minimális lefogás, akkor S − L max-hiányú halmaz, míg ha H ⊆ S max-hiányú halmaz, akkor Γ(H) ∪ (S − H) minimális lefogás lesz.

Lemma 3.4 F zárt a metszet és unió képzésre.

Biz. Könnyű ellenőrizni, hogy a h függvény szupermoduláris, azaz h(X)+h(Y) ≤ h(X∩Y)+h(X∪Y). Tegyük most fel, hogy X és Y két maximális hiányú halmaz (azaz F elemei). Ekkor μ + μ = h(X) + h(Y) ≤ h(X ∩ Y) + h(X ∪ Y) ≤ μ + μ, és emiatt valóban h(X ∩ Y) = μ, h(X ∪ Y) = μ. •

A lemmából következik, hogy az összes max-hiányú halmaz metszete is és uniója is max-hiányú, azaz létezik egy egyértelmű legszűkebb és egy legbővebb max-hiányú halmaz. Megjegyzendő, hogy Kőnig fenti alternáló utas algoritmusa segítségével e két halmaz könnyen megkonstruálható. Például, a legszűkebb K max-hiányú halmaz, amint azt könnyű kimutatni, éppen Z ∩ S lesz, ahol Z jelölte az irányított segédgráfban az R_{S}-ből elérhető pontok halmazát. Ez egyúttal azt is mutatja, hogy az algoritmus által produkált (S − K ∪ Γ(K)) lefogás nem függ az algoritmus futásától (szemben az algoritmus által szolgáltatott párosítással). A súlyozott párosítási algoritmus bizonyításához szükségünk lesz még az alábbi hasznos megfigyelésre.

Lemma 3.5 Legyen K ⊆ S a legszűkebb max-hiányú halmaz G-ben. Ha a gráfból kitöröljük az összes olyan élt, amely Γ(K) és S − K között vezet, akkor a létrejövő G′ gráfban a maximális hiány ugyanaz, mint G-ben. Továbbá G és G′ max-hiányú halmazainak rendszere ugyanaz.

Biz. Miután G egy M maximális párosításának a Γ(K)-t fedő élei mind K-ban végződnek, az M benne van G′-ben is, vagyis G′ max hiánya legfeljebb akkora, mint G-é, de persze kisebb nem lehet, mert G′ részgráfja G-nek. Ebből az is következik, hogy a G egy max-hiányú halmaza G′-ben is maxhiányú. Legyen most X tetszőleges max-hiányú halmaz G′-ben. Mivel K max-hiányú G′-ben is, a 3.4 lemma szerint K ∩ X is max-hiányú G′-ben. De akkor K ∩ X max-hiányú G-ben, hiszen K ∩ Xből indulo’élt nem töröltünk, és így a K minimalitása folytán K ⊆ X. Ekkor viszont Γ(X) = Γ′(X), azaz X max-hiányú G-ben is. •

3.1.2 Súlyozott párosítások

TÉTEL 3.6 (Egerváry) Legyen G = (V, E) teljes páros gráf, melynek pontjai két n elemű osztályba vannak sorolva. Legyen továbbá c : E → R_{+} az éleknek egy nemnegatív számokkal történő súlyozása. Ekkor G teljes párosításainak maximális súlya egyenlő a nemnegatív súlyozott lefogások minimális súlyával, ahol nemnegatív súlyozott lefogáson egy olyan π : V → R_{+} függvényt értünk, amelyre π(u) + π(v) ≥ c(uv) a gráf minden uv élére fennáll. Amennyiben c egészértékű, úgy az optimális π is választható egészértékűnek.

Egervárynak a 3.6 tételre adott eredeti bizonyításának a váza a következő. Legyen π egy minimális súlyú nemnegatív, egészértékű súlyozott lefogás. (A π súlyán a ∑[π(v) : v ∈ S ∪ T] összeg értendő.) Feltehetjük, hogy π az S elemein mindenütt pozitív, mert ha nem, akkor az S-beli pontokon eggyel növelve, a T -beli pontokon eggyel csökkentve már ilyen lesz. Amennyiben azon élek G_{π} részgráfjában, melyekre π(u) + π(v) = c(uv) létezik teljes M párosítás, úgy M maximális súlyú párosítás, melynek súlya egyenlő a π(v) értékek összegével. Ha viszont G_{π}-ben nincs teljes párosítás, úgy Kőnig vagy Hall tétele alapján létezik hiányos X halmaz, azaz olyan, amelynek |X|-nél kevesebb szomszédja van. A π értékeit az X pontjain eggyel csökkentve, a Γ_{G_{π}}(X) pontjain pedig eggyel növelve, egy másik nemnegatív, súlyozott lefogást kapunk, amelynek súlya kisebb, mint π-é, ellentmondásban π minimális választásával.

Ez a bizonyítás könnyen algoritmizálható, hiszen tetszőleges π súlyozott lefogásból kiindulva vagy talál egy maximális súlyú teljes párosítást, és ekkor az aktuális π is optimális, vagypedig talál egy jobb súlyozott lefogást, amivel az eljárást iterálva véges sok lépés után az első eset következik be. Egy kézenfekvő gyorsítási lehetőség azonnal kínálkozik: a π súlyozott lefogás módosításakor ne eggyel növeljünk vagy csökkentsünk, hanem a legnagyobb olyan δ értékkel, amelyre a módosított π′ még súlyozott lefogás. Az így nyert eljárást nevezzük Egerváry algoritmusának. (Hangsúlyozzuk, hogy ez nem ugyanaz, mint a H. W. Kuhn által kifejlesztett primál-duál eljárás, amit ma valójában a világban Kuhn javaslata nyomán Magyar Módszernek hívnak.)

Az Egerváry algoritmusnak az az előnye is megvan, hogy nem egészértékű c súlyfüggvényre is működik, bár ekkor még az is kérdés, hogy az eljárás véges-e egyáltalán, és Egerváry valójában a nemegész c esetét nem algoritmikusan, hanem folytonossági megfontolásokkal intézte el.

Nem kevésbé fontos a másik kérdés, hogy Egerváry algoritmusa milyen hatékony, akár egész a c, akár nem. Példával megmutatható, hogy ha tetszőleges olyan X halmazt használunk a π módosítására, amely megsérti a Hall-féle feltételt, akkor az algoritmus nem polinomiális futásidejű (és ez a kellemetlenség még akkor is előfordulhat, ha X maximális hiányú halmaz.) Ráadásul irracionális költségek esetén még azt sem tudjuk, hogy az algoritmus véges sok lépés után megáll-e.

Egerváry azonban bizonyításában azt javasolja, hogy a π változtatását annak a maximális hiányú X halmaznak a segítségével végezzük, amelyet Kőnig alternáló utas algoritmusa szolgáltat, amely tehát a(z egyértelmű) legszűkebb max-hiányú halmaz. Az alábbiakban kimutatjuk, hogy Egerváry algoritmusa ilyenkor polinomiális, sőt erősen polinomiális futásidejű. Mivel nem jelent semmilyen többlet nehézséget, a bizonyítást rögtön a tétel azon csöppnyit általánosabb alakjára mondjuk el, amikor a páros gráf nem feltétlenül teljes, csupán azt írjuk elő, hogy tartalmazzon teljes párosítást.

TÉTEL 3.7 Tegyük fel, hogy a G = (S, T; E) páros gráfnak van teljes párosítása. Legyen továbbá c : E → R_{+} az éleknek egy nemnegatív számokkal történő súlyozása. Ekkor G teljes párosításainak maximális súlya egyenlő a súlyozott lefogások minimális súlyával, ahol súlyozott lefogáson egy olyan π : V → R függvényt értünk, amelyre π(u)+π(v) ≥ c(uv) a gráf minden uv élére fennáll. Amennyiben c egészértékű, úgy az optimális π is választható egészértékűnek. Amennyiben G teljes páros gráf, az optimális π választható nemnegatívnak.

Biz. Tetszőleges M teljes párosításra és π súlyozott lefogásra fennáll, hogy ∑(π(z) : z ∈ S ∪ T) = ∑([π(u) + π(v)] : uv ∈ M) ≥ ∑(c(uv) : uv ∈ M), vagyis a minimum valóban lagalább a maximum. Az is kiolvasható, hogy itt egyenlőség pontosan akkor áll, ha az M párosítás minden uv éle pontos abban az értelemben, hogy π(u) + π(v) = c(uv). Célunk tehát azt kimutatni, hogy létezik egy olyan π, amelyre nézve a pontos élek gráfjában létezik teljes párosítás.

Legyen π egy olyan súlyozott lefogás (egészértékű, ha c az), amelyre a pontos élek G_{π} = (S, T; E_{π}) részgráfjában a μ_{π}(= |S| − ν(G_{π})) érték minimális, és ezen belül, az (egyértelmű) legszűkebb maxhiányú K ⊆ S halmaz a lehető legnagyobb. Készen vagyunk, ha a μ_{π} maximális hiány nulla, mert ez épp azt jelenti, hogy G_{π}-nek van teljes párosítása. Tegyük fel tehát, hogy μ_{π} > 0. Mivel G-nek van teljes párosítása, biztosan van olyan e éle G-nek, amely K és T − Γ_{π}(K) között vezet, ahol Γ_{π}(K) jelöli a K szomszédainak halmazát a G_{π}-ben. Ilyen él nem pontos, így a

δ := min(π(u) + π(v) − c(uv) : uv ∈ E, u ∈ K, v ∈ T − Γ_{π}(K))  (3.3)

érték pozitív. Módosítsuk π-t úgy, hogy a K-minden elemén δ-val csökkentjük, míg Γ_{π}(K) minden elemén δ-val növeljük, azaz

v ∈ K -ra π′(v) := π(v) − δ, v ∈ Γ_{π}(K) -ra π′(v) := π(v) + δ, egyébként π′(v) := π(v).  (3.4)

A δ választása miatt az így módosított π′ továbbra is súlyozott lefogás, amely egészértékű, ha c az volt. A π′-ra vonatkozó pontos élek G_{π′} gráfja abban különbözik G_{π}-től, hogy van legalább egy éle (ahol a δ-t definiáló minimum felvétetett) K és T − Γ_{π}(K) között, de biztosan nincsen éle T ∩ Γ_{π}(K) és S − K között (miközben G_{π}-nek lehetett). A 3.5 lemma szerint μ_{π′} = μ_{π}, és G_{π′}-ben a legszűkebb max-hiányú halmaz szigorúan bővebb, mint K, és ez ellentmond π választásának.

Beláttuk tehát, hogy van olyan π súlyozott lefogás, amelyre a pontos élek részgráfjában van teljes párosítás. Végül tegyük fel, hogy G teljes páros gráf, és igazoljuk, hogy π választható nemnegatívnak. Legyen a π legnegatívabb értéke −α ahol α > 0 és legyen π(v) = −α, ahol v mondjuk S-ben van. ekkor minden u ∈ T csúcsra π(u) + π(v) ≥ c(uv) ≥ 0 miatt π(u) ≥ α. Így ha π-t úgy módosítjuk, hogy S elemein növeljük α-val, míg T elemein csökkentjük α-val, akkor egy másik minimális súlyozott lefogás keletkezik, amelyik már nemnegatív. •

Az is belátható, hogy az optimális súlyozott lefogás pontosan akkor választható nemnegatívnak, ha a maximális súlyú párosítás teljes párosításon vétetik fel (amely feltétel persze teljes páros gráf esetén fennáll.)

A bizonyítás alapján Egerváry algoritmusa a következő. Az algoritmus bemenete egy teljes párosítással rendelkező páros gráf, míg a kimenete egy maximális súlyú párosítás és egy minimális súlyú súlyozott lefogás. Szubrutinként szükségünk van a súlyozatlan esetre vonatkozó fentebb ismertetett alternáló utas algoritmusra, amely egy tetszőleges G′ = (S, T; E′) páros gráfban megkonstruál egy maximális M′ párosítást és a(z egyértelmű) legszűkebb K′ ⊆ S max-hiányú halmazt (melyekre tehát |M′| = |Γ′(K′)| + |S − K′|.) Hivatkozás kedvéért ezt Kőnig szubrutinnak nevezzük.

Az algoritmus egy általános lépésében rendelkezésre áll egy π súlyozott lefogás (amely egészértékű, ha c az, és amely kezdetben lehet például az azonosan α lefogás, ahol α a c(e) költségek maximuma. Alkalmazzuk a Kőnig szubrutint a π-re nézve pontos élek G_{π} részgráfjára. Amennyiben G_{π}-ben van M teljes párosítás, úgy az algoritmus az aktuális π súlyozott lefogás és M teljes párosítás kiadásával véget ér. Ha viszont G_{π}-nek nincs teljes párosítása, úgy a szubrutin által szolgáltatott (G_{π}-re nézve) legszűkebb K_{π} max-hiányú halmaz segítségével 3.4 szerint módosítjuk π-t, és az eljárást iteráljuk.

Mi mondható az algoritmus lépésszámáról? Tekintsük egy fázisnak az algoritmus azon szakaszát, amíg a pontos élek (egyre változó) részgráfjában a maximális hiány változatlan. Nyilván legfeljebb |S| fázis létezik. Egy fázis során a szubrutint legfeljebb |S|-szer hívjuk meg, hiszen beláttuk, hogy a π cseréjekor a legszűkebb max-hiányú halmaz szigorúan bővül. Vagyis a súlyozatlan esetre vonatkozó alternáló utas algoritmusnak legfeljebb |S|^{2}-szeri meghívásával az algoritmus futása befejeződik. Miután Kőnig algoritmusának lépésszámára O(|S||E|) korlát volt mondható, a leírt súlyozott eljárás teljes futásideje O(|S|^{3}|E|).

Bár ez a lépészám nem különösebben látványos (és valójában hatékonyabb eljárások is léteznek), mindenesetre azt megkaptuk, hogy az algoritmus polinomiális futásidejű, sőt erősen polinomiális is abban az értelemben, hogy a futásidő egyáltalán nem függ a szereplő c költségfüggvénytől, amennyiben feltesszük, hogy a számokkal végzett összadást, kivonást és összehasonlítást egyetlen lépésben tudjuk elvégezni.

A jelen megközelítés előnye, hogy tisztán mutatja a súlyozatlan és a súlyozott párosítási algoritmusok viszonyát. A súlyozatlan Kőnig-féle algoritmus teljesen szeparáltan, szubrutinként kerül felhasználásra. Amint azt H. W. Kuhn megmutatta, a két eljárás összevonható, aminek talán hátránya, hogy az algoritmus összetettebbé válik, de előnye, hogy jobb lépésszám becslés adódik. Most ismertetjük a Kuhn által javasolt Magyar Módszert.

Kuhn algoritmusa súlyozott teljes párosítás meghatározására

Az általános lépésben tekintjük a pontos élek által (az S ∪T ponthalmazon) alkotott G_{π} részgráfot. Legyen M egy már rendelkezésre álló párosítás G_{π}-ben. Irányítsuk meg M éleit T -től S felé, míg az összes többi G_{π}-beli élt fordítva. Jelölje R_{S} illetve R_{T} az S-ben illetve a T -ben az M által fedetlen pontok halmazát. Jelölje Z az R_{S} pontjaiból az így kapott irányított gráfban irányított úton elérhető pontok halmazát (amit például szélességi kereséssel találhatunk meg). Amennyiben R_{T} -nek esik pontja Z-be, akkor megkaptunk egy olyan R_{S}-t és R_{T} -t összekötő P utat, amely M-ben alternál. Most M és P szimmetrikus differenciája egy M-nél eggyel több élből álló M′ párosítás. Ekkor az eljárás egy fázisa véget ér, és az új M′ párosítással folytatva iteráljuk az eljárást.

Nézzük most azt az esetet, amikor R_{T} diszjunkt Z-től. Legyen K_{π} := Z ∩ S és módosítsuk π-t a 3.4-ben leírtak szerint. Ekkor az R_{S}-ből elérhető pontok halmaza szigorúan bővül. Így egy fázis (ami alatt tehát a pontos élek gráfjában a maximális párosítás elemszáma nem nő) |S| útkereső eljárás alkalmazása után véget ér. Mivel egy útkeresés O(|E|) lépésben végrehajtható és legfeljebb |S| fázis van, az algoritmus teljes futásideje O(|E||S|^{2}).

A fejezet lezárásaképp megmutatjuk, hogy a maximális súlyú (nem feltétlenül teljes) párosítás meghatározásának problémája egyszerű fogással visszavezethető a maximális súlyú teljes párosításéra.

TÉTEL 3.8 Egy G′ = (S′, T′; E′) páros gráfban nemnegatív c súlyfüggvény esetén a párosítások maximális ν′_{c} súlya egyenlő a nemnegatív (!) súlyozott lefogások minimális τ′_{c} súlyával. Amennyiben c egészértékű, az optimális π′ is választható egészértékűnek.

Biz. A ν′_{c} ≤ τ′_{c} egyenlőtlenség nyilvánvaló, így csak a fordított iránnyal foglalkozunk. Új pontok esetleges hozzávételével elérhetjük, hogy a páros gráf két osztálya egyforma méretű legyen. Egészítsük ki a gráfot 0 súlyú élek bevételével egy G teljes páros gráffá. A súlyfügvény ezen kiterjesztését továbbra is jelölhetjük c-vel. A 3.7 tétel (második része) szerint G-nek létezik egy M teljes párosítása és c-nek egy π nemnegatív súlyozott lefogása, melyekre c(M) = ∑ π(v). Mivel az új élek súlya 0, így az új élek kihagyásával M-ből keletkező G′-beli M′ párosítás súlya változatlanul c(M). Miután új pontból (ha van) csak 0 súlyú él megy ki, így π értéke az új pontokon 0, vagyis, ha π-t megszorítjuk az eredeti pontokra, akkor a kelektező π′-re ∑ π′(v) = ∑ π(v), és így ∑ π′(v) = c(M′). •

Végül megjegyezzük, hogy tetszőleges rögzített k pozitív egészre Ford és Fulkerson minimális költségű folyam algoritmusának segítségével ki lehet számolni a maximális (vagy minimális) súlyú k élű párosítást, ha ilyen párosítás egyáltalán létezik.

file: umagyar,

3.2 Minimális költségű fenyők

Legyen D = (V, A) irányított gráf, amelynek egy adott s pontjából minden más pontja elérhető irányított úton, ami azzal ekvivalens, hogy D tartalmaz feszítő s-fenyőt. Adott az éleken egy nemnegatív c : A → R_{+} költség- (vagy másnéven súly-) függvény. Keressünk minimális összköltségű feszítő s-fenyőt.

Egy z : 2^{V −s} → R_{+} halmazfüggvényt c-megengedettnek nevezünk, ha

c(e) ≥ ∑(z(X) : e belép X-be) minden e ∈ E élre.  (3.5)

TÉTEL 3.9 [Fulkerson, 1974] Az s-fenyők minimális költsége egyenlő max{∑[z(X) : X ⊆ V −s] : z c-megengedett}. Továbbá, ha c egészértékű, akkor az optimális z választható egészértékűnek.

Biz. Legyen F feszítő s-fenyő és z egy c-megengedett vektor. Ekkor

c(F) = ∑(c(a) : e ∈ F) ≥ ∑(∑(z(X) : e belép X − be): e ∈ F) ≥ ∑(z(X) : X ⊆ V − s) (3.6)

amiből max ≤ min következik. (3.6)-ben akkor van végig egyenlőség, ha a következő optimalitási feltételek teljesülnek.

c(e) = ∑(z(X) : e belép X-be) minden e ∈ F élre,  (3.7)
z(X) > 0 esetén ϱ_{F} (X) = 1.  (3.8)

Az alábbi algoritmus egy olyan F feszítő s-fenyőt és megengedett z-t konstruál, amelyre (3.7) és (3.8) teljesül. Két fázisból áll. Az elsőben z-t konstruáljuk meg, míg a másodikban F -t. Mindkét rész egyfajta értelemben mohó lesz. Az első fázis minden lépésében módoítjuk a költségfüggvényt, és az aktuális költségfüggvényt c′-vel fogjuk jelölni. Egy e élt a c′ aktuális költségfüggvényre nézve 0-élnek nevezzük, ha c′(e) = 0.

1. fázis Amíg van V − s-nek olyan nemüres részhalmaza, amelybe nem lép be 0-él, ismételjük a következő lépést. Válasszunk egy olyan minimális nemüres X ⊆ V − s részhalmazt, amelybe nem lép 0-él. Legyen z(X) := min(c′(e) : e belép X-be) és csökkentsük c′(e)-t a z(X) értékkel az összes X-be lépő e élen.

A módosított c′ továbbra is nemnegatív, és mindazokon az X-be belépő éleken 0-vá vált, amelyeken az előbbi minimum eléretik. Az 1. fázis tehát akkor fejeződik be, amikor már minden X ⊆ V − s részhalmazba lép be 0-él, vagyis amikor már létezik 0-élekből álló feszítő s-fenyő.

2. fázis Az s pontból kiindulva, 0-élek egymás utáni hozzávételével felépítünk egy F s-fenyőt. Ha az építési eljárás egy lépésében több, mint egy olyan 0-él van, amely a már megkonstruált részfenyő ponthalmazából kilép, akkor azt az élt adjuk a részfenyőhöz, amely az 1 fázis során a leghamarabb vált 0-éllé.

Az előállítás szabályai miatt világos, hogy a megkonstruált z vektor c-megengedett, továbbá, hogy (3.7) fennáll.

Lemma 3.10 z és F kielégítik (3.8)-t.

Biz. Legyen X olyan halmaz, amelyre z(X) > 0 és tegyük fel indirekt, hogy ϱ_{F} (X) > 1. Ekkor a 2. fázisnak van egy olyan pillanata, amikor az aktuális F′ részfenyő olyan, hogy ϱ_{F′}(X) = 1 és az F′-höz éppen hozzáadásra kerülő e él belép X-be.

Tekintsük most az 1. fázisnak azt a pillanatát, amikor z(X) pozitív lett. Ekkor az X-be még nem lépett 0-él, ugyanakkor az X-nek már minden valódi nemüres részhalmazába lépett. Speciálisan, az X − V (F′) halmazba is lépett egy f 0-él, és mivel ez X-be nem léphetett, így f töve X ∩ V (F′)-ben van. Az f tehát már z(X) pozitívvá válásának pillanatában 0-él volt, amikor még e nem volt az. Miután az f éllel is lehetne növelni az F′ részfenyőt, ellentmondásra jutottunk a 2. fázis választási szabályával, amely szerint a legkorábban 0-éllé vált éllel kell növelni az aktuális részfenyőt. •

A lemmából következik, hogy az algoritmus által megtalált F feszítő s-fenyő és z megengedett duális megoldás kielégítik az optimalitási feltételeket, amiből az algoritmus helyessége, valamint Fulkerson tétel is következik. • •

Az előbbihez kapcsolódik a következő probléma. Legyen D = (V, E) ismét egy irányított gráf éleinek halmazán egy w súlyfüggvénnyel. Keressünk maximális súlyú fenyvest!

Egy (p, y) párt fedésnek nevezünk, ha p : V → R_{+} és y : 2^{V} → R_{+} nemnegatív függvények melyekre w(u, v) ≤ p(v) + ∑(y(B) : u, v ∈ B ⊆ V) teljesül minden uv ∈ E élre. A fedés értéke ∑(p(v) : v ∈ V) + ∑(y(B)(|B| − 1) : B ⊆ V).

TÉTEL 3.11 [Edmonds, 1967], [Chu and Liu, 1965] Egy fenyves súlyának maximuma a fedések minimális értékével egyenlő. Ha w egészértékű, akkor az optimális fedés is választható annak.

Biz. Könnyen látszik, hogy max ≤ min. A fordított irány belátásához egészítsük ki D-t egy új s ponttal és vezessünk s-ből minden v ∈ V pontba egy új sv élt. A megnövelt D′ digráfon definiáljunk egy c költségfüggvényt a következőképpen. Az új élek költsége legyen M := max(w(e) : e ∈ E), míg minden eredeti e ∈ E élre legyen c(e) = M − w(e).

Az 3.9 tétel szerint létezik z : 2^{V} → R_{+} c-megengedett vektor és egy D′-nek egy F feszítő s-fenyője amelyek kielégítik (3.7)-t és (3.8)-t. Legyen p(v) := M − ∑(z(B) : v ∈ B), és |B| > 1 esetén legyen y(B) := z(B) (B ⊆ V). Könnyen látható, hogy az így kapott (p, y) fedést alkot, továbbá, hogy az értéke egyenlő a D digráf F ∩ A fenyvesének súlyával. •

Feladat 3.1 Legyen T ⊆ V −s adott halmaz olyan, hogy a digráf minden pozitív költségű élének a feje T -ben van (a költségfüggvény nemnegatív). Olyan minimális költségű s gyökerű fenyő keresése, amely T minden pontját tartalmazza (de nem feltétlenül feszítő) speciális esete a T -metsző halmazrendszerek korábban tárgyalt lefogási problémájának. Mutassuk meg, hogy a feladat visszavezethető a minimális költségű fesztő fenyő problémájára.

Feladat 3.2 Igazoljuk hogy egy D = (V, E) digráfban éleknek egy adott F ⊆ E részhalmaza akkor és csak akkor egészíthető ki s gyökerű feszítő fenyővé, ha nem lehet úgy megadni a V − s halmaznak |V | − |F | darab nemüres részhalmazát, hogy ezek egyikébe sem lép F -beli él és E − F minden eleme legfeljebb egybe lép.

(Útmutatás. Alkalmazzuk az 3.9 tételt alkalmas költségfüggvényre.)

Feladat 3.3 Tegyük fel, hogy adott V −s részhalmazainak egy {A_{1}, …, A_{t}} rendszere. Hogyan lehetne algoritmikusan eldönteni, hogy a digráf tartalmaz-e olyan feszítő fenyőt, amely mindegyik A_{i} halmazba pontosan egyszer lép bele?

(Útmutatás. Keressünk minimális költségű fenyőt okosan választott költségfüggvényre.)

Feladat 3.4 Tegyük most fel, hogy létezik olyan s-gyökerű feszítő fenyő, amely az {A_{1}, …, A_{t}} halmazok mindegyikébe egyetlen éllel lép bele. Készítsünk algoritmust, amely az ilyen fenyők közül egy megadott költségfüggvényre vonatkozó minimális költségűt talál.

3.3 Maximális párosítások általános gráfokban

Valamely G irányítatlan gráfra jelölje ν = ν(G) a független élek maximális számát vagyis a legnagyobb párosítás elemszámát. Láttuk, hogy az alternáló utak módszerével miként lehet páros gráfban maximális elemszámú párosítást megkonstruálni. Az eljárás egyúttal bizonyította a Kőnig tételt is, amely szerint a szóbanforgó maximum egyenlő a pontokat lefogó élek minimális τ számával. Nem páros gráfokban a ν = τ min-max reláció már nem feltétlenül igaz, amint ezt a háromszög példája mutatja. Itt ν = 1, τ = 2. Az általános gráfokra vonatkozó jellemzés W.T. Tutte-tól származik.

TÉTEL 3.12 (Tutte) A G = (V, E) irányítatlan gráfban akkor és csak akkor létezik teljes párosítás, ha a pontok tetszőleges X részhalmazára az X elhagyásával keletkező páratlan (pontszámú) komponensek száma legfeljebb |X|.

Az X elhagyásával keletkező páratlan komponensek számát jelölje q(X). Tetszőleges M teljes párosítás egy páratlan pontszámú halmazból páratlan sok éllel lép ki, így speciálisan legalább eggyel. Ebből látszik, hogy ha létezik teljes párosítás, akkor q(X) legfeljebb |X|, azaz a Tutte-féle feltétel szükséges.

Az elegendőséget kicsit általánosabb alakban igazoljuk. Amennyiben teljes párosítás nem létezik, megkérdezhetjük, hogy milyen nagy létezik, azaz mekkora ν. Jelöljük a q(X) − |X| különbséget γ(X)-szel. (A Tutte féle feltétel azt jelenti, hogy γ(X) ≤ 0.) Tegyük most fel, hogy valamely X ponthalmazra γ(X) > 0. Ekkor tetszőleges M párosítás legalább γ(X) pontot nem fed le, vagy másszóval M legfeljebb |V | − γ(X) pontot fedhet le, azaz

|M| ≤ (|V | − γ(X))/2.  (3.9)

Itt egyenlőség akkor és csak akkor áll, ha

(a) Az X elhagyásával keletkező bármely C komponensre az M-nek a C-be eső része legfeljebb egy pont híján fedi C-t. (b) X nem feszít M-beli élt.

(c) M fedi X minden pontját.

Egy ilyen X halmazt gátnak nevezünk. A Tutte tétel általánosítása mármost a következő.

TÉTEL 3.13 (Berge-Tutte formula) G-ben a független élek maximális ν száma egyenlő max(|V |− γ(X))/2-vel, ahol a maximum V összes X részhalmazára megy.

A fenti meggondolás alapján a max ≤ min egyenlőtlenség következik. A fordított egyenlőtlenség ekvivalens a következővel:

Létezik olyan M párosítás és pontoknak olyan X részhalmaza, melyekre (a), (b) és (c) fennáll.

Az alábbi J. Edmondstól származó algoritmus ilyen M-et és X-et konstruál meg. Az eljárás fázisokból áll. Egy fázisban valamely korábban megtalált M párosításból indulunk ki és keresünk egy olyan P M-alternáló utat, amely két szabad (azaz, M által nem fedett) pontot köt össze. Nevezzük az ilyen utat növelő útnak.

Amennyiben találunk egy P növelő utat, úgy az M′ := M ⊗ P szimmetrikus differencia olyan párosítás lesz, amelynek eggyel több éle van, mint M-nek, és ekkor a következő fázisra térünk. Amikor az algoritmus már nem talál M-alternáló utat, akkor megad majd egy X részhalmazt, amely az aktuális M párosítással együtt kielégíti a három optimalitási feltételt.

Legyen tehát M valamilyen párosítás, S a szabad pontok halmaza és v ∈ V −S-re jelöljük μ(v)-vel a v párosításbeli szomszédját. Az S pontjaira pedig definiáljuk μ(v) = v. Az eljárás egy F M-alternáló erdőt épít fel, amely a következő tulajdonságú erdő.

(i) F -nek |S| darab komponense van, mindegyike egyetlen szabad pontot tartalmaz, amely a komponens gyökere.

(ii) F bármely pontjából a gyökérhez vezető út M-alternáló.

(iii) Ha valamely fedett v pont F -ben van, akkor a vμ(v) él is F -hez tartozik.

Az F erdőben nem lévő pontok halmazát tisztásnak hívjuk és C := C(F)-fel jelöljük. Nyilván az M-nek C-ben levő élei C-t párosítják. Külső pontnak hívjuk az F azon pontjait, melyek a gyökértől páros távolságban vannak. F többi pontja belső pont. (Az elnevezés arra utal, hogy a végül kapott külső pontok, amint majd az Edmonds-Gallai tétel nyomán kiderül, olyanok, hogy mindegyikhez van egy őt nem lefedő maximális párosítás, míg a belső pontok mindegyikét valamennyi maximális párosítás fedi.)

Kiinduláskor F a szabad pontokból áll és élt nem tartalmaz. Az általános lépés leírásához legyen F M-alternáló erdő. Három esetet különböztetünk meg.

1. eset. Az F -nek létezik olyan u és v külső pontja, melyek az F különböző komponenséhez tartoznak és amelyek között vezet él a gráfban. Ekkor az u és v komponensében a gyökerekhez vezető két alternáló utat az uv él mentén összekapcsolva egy P növelő utat kapunk, és ekkor az adott fázis végetér.

2. eset. F -nek létezik olyan u külső pontja, amely szomszédos egy v tisztáson lévő v ponttal. Ekkor az uv élt és a vμ(v) párosító élt F -hez véve nagyobb M-alternáló erdőt kapunk.

3. eset. F -nek egy komponensében létezik u és v külső pont, melyek szomszédosak. Ekkor az F -ben az u-t és v-t összekötő egyértelmű út az uv éllel együtt egy páratlan kört alkot. Húzzuk össze ezt a kört egy ponttá. Ekkor F -ből egy másik alternáló erdő keletkezik, melynek az összehúzott pont külső pontja.

Nevezzünk valamely K páratlan kört M-alternálónak, ha valamely r pontjából a körön akármelyik irányba elindulva minden második él M-beli. Az r pontot a kör bázisának hívjuk. Az M-alternáló kör legfontosabb tulajdonsága, hogy

(∗) K bármely pontjából vezet a bázisba párosítás éllel kezdődő alternáló út.

A fenti 3. esetben egy M-alternáló páratlan kört húztunk össze. A (∗) tulajdonságból látjuk, hogy ha az összehúzott gráfban létezik növelő út, akkor ebből előállíthatjuk az eredeti gráf egy növelő útját. Ebből az is következik, hogy ha az 1. eset olyankor fordul elő, amikor már bizonyos összehúzásokat végrehajtottunk, akkor az eredeti gráfnak is elő tudunk állítani egy növelő útját. Azt is megfigyelhetjük, hogy (esetleg többszöri) összehúzással keletkezett pont ősképe olyan halmaz, amelyet a beleeső M-beli élek egy pont híján kipárosítanak.

TEHÁT: Ameddig a 2. vagy 3. eset fordul elő, járjunk el az ott leírtak szerint. Amennyiben az 1. eset következik be, azaz az összehúzott gráfban van növelő út, akkor keressünk az eredeti gráfban növelő utat és egy nagyobb párosítást, majd térjünk a következő fázisra.

Vizsgáljuk most meg azt az esetet, amikor a fenti három eset egyike sem áll fenn. Jelölje X a belső pontok halmazát, C a tisztást és D a külső pontok ősképeinek halmazát. Emlékezzünk rá, hogy belső pont sohasem összehúzott pont. Külső pontból csak belső pontba vezet él, ezért G-ben az X elhagyásakor a külső pontok ősképei páratlan komponensek lesznek. Így M és X kielégítik az optimalitási feltételeket. Evvel az algoritmus leírását és egyúttal a Berge-Tutte formula igazolását befejeztük. •

Feladat 3.5 Vezessük le Tutte tételéből: (a) Petersen tételét (amely szerint 2-élösszefüggő 3-reguláris gráfban létezik teljes párosítás), (b) a Berge-Tutte formulát, (c) Hall tételét.

3.3.1 Kritikus gráfok

A párosítások elméletében a következő fogalom alapvető fontosságú. Egy gráfot faktor-kritikusnak vagy röviden kritikusnak nevezünk, ha bármely pontját elhagyva létezik teljes párosítása.

(A matroidelmélet előadásban bebizonyítottuk Gallai Lemmáját, amely szerint, ha G olyan összefüggő gráf, amelynek bármely pontját elhagyva ν(G) csökken, akkor G faktor-kritikus. A bizonyítás azon múlt, hogy a feltevés szerint G párosítás matroidjának M^{∗} duálisában nincsen hurok és bármely két szomszédos pont kételemű matroidbeli kört alkot. Ebből a G összefüggőségét felhasználva következik, hogy a V alaphalmaz M^{∗}-beli rangja egy ,ami viszont azt jelenti, hogy G faktor-kritikus.)

Egy Q ⊆ V páratlan pontszámú részhalmaz által feszített gráfot valamely M párosításra nézve Mkritikusnak mondunk, ha az M Q-ba eső élei egyetlen r pont, az ún bázispont kivételével lefedik Q-t és Q minden pontjából vezet r-be páros élszámú alternáló út (azaz olyan, amelynek első éle párosítás él.)

TÉTEL 3.14 Legyen adott a G gráf egy M párosítása, amely az r pontot nem fedi le, a többit lefedi. A következők ekvivalensek:

(a) G M-kritikus,

(b) G felépíthető a bázispontjából kiindulva M-alternáló utak illetve körök egymás utáni hozzávételével,

(c) G felépíthető bármely pontjából kiindulva páratlan élszámú utak és körök hozzávételével,

(d) G faktor-kritikus.

Biz. (a → b) Tegyük fel, hogy r-ből kiindulva már felépítettünk G-nek egy részgráfját a megadott módon. Jelölje a részgráf ponthalmazát T. (A kezdetben T az egyetlen r pontból áll.) Akkor vagyunk készen, ha T = V, ekkor ugyanis a még G-ből esetleg hiányzó éleket egyélű M-alternáló utakként bevéve, megkapjuk G-t. Ha még T ≠ V, akkor létezik olyan uv él, amelyre u ∈ T, v ∉ T. (Miután a definícióból adódóan M-kritikus gráf összefüggő, ilyen él létezik.) A gráf M-kritikus, így v-ből létezik r-be vezető páros M-alternáló út. Legyen ennek p az első T -be eső pontja és jelölje P′ az útnak v-ből p-be vezető szegmensét. Most az uv él a P′-vel együtt egy M-alternáló utat vagy kört alkot, amellyel T tovább építhető.

(b → c) Triviális, mert egy M-alternáló út páratlan élszámú.

(c → d) Fülek száma szerinti indukció. Két esetet kell különválasztani, annak megfelelően, hogy a kihagyandó pont az utolsó fülön van vagy sem.

(d → a) Legyen v a gráf tetszőleges pontja. Mivel G faktor-kritikus, G−v-nek létezik egy M_{v} teljes párosítása. Két párosítás szimmetrikus differenciája mindig diszjunkt alternáló körökből és utakból áll. Mivel mind M mind M_{v} a G-nek egyetlen pontját nem fedi le, így szimmetrikus differenciájuk egyetlen alternáló utat tartalmaz, és az a v és r pontokat köti össze. Így tehát létezik v-ből r-be páros élszámú M-alternáló út. •

Az alábbiakban megadunk egy kicsit bonyolultabb konstrukciót, amely M-kritikus gráfot eredményez. A tétel szemléletesen azt mondja, hogy ha egy páratlan kör pontjaiba M-kritikus gráfokat ”fújunk be”, akkor M-kritikus gráfot kapunk.

TÉTEL 3.15 Tegyük fel, hogy a G gráfban az M párosítás egy r pont kivételével mindent lefed, továbbá, hogy a ponthalmaz fel van osztva páratlan sok diszjunkt M-kritikus részgráfra, melyek mindegyikét egyetlen pontra húzva M-kritikus (azaz M-alternáló) C páratlan kört kapunk. Ekkor G maga is M-kritikus.

Biz. Vegyünk a gráfnak egy tetszőleges v_{1} = v pontját és mutassuk meg, hogy létezik v-ből r-be páros élszámú M-alternáló út. Amennyiben v és r ugyanabban a P_{r} partíció részben van, akkor P_{r} M-kritikussága miatt a kívánt út létezik.

Tegyük most fel, hogy a P_{v} és P_{r} partíció részek különbözők. Jelölje P_{1} := P_{v}, P_{2}, …, P_{t} := P_{r} azokat a partíció részeket, amelyeket a C körben a P_{v}-ből a P_{r}-be menve kapunk, ha a P_{1}-ből kilépő r_{1}r_{2} párosítás él felé indulunk el. (Tehát t páratlan!)

Először P_{1}-ben a v-ből indulva elmegyünk egy páros élszámú M-alternáló úton a P_{1} gyökeréig, az ebbe jövő M-élen átmegyünk P_{2}-be. Legyen a P_{2}-ből kilépő nem-párosítás él u_{2}v_{2} ahol u_{2} ∈ P_{2}, v_{2} ∈ P_{3}. Használjuk fordítva az u_{2}-ből r_{2}-be vezető páros élszámú M-alternáló utat, így már eljutottunk u_{2}-be. Most tovább lépünk az u_{2}v_{2} élen a P_{3}-részbe, ahonnan a v_{2} ponttal kezdve iteráljuk az eljárást. •

Amint láttuk, Edmonds algoritmusa megkonstruál egy gátat és egy párosítást, melyekre fennállnak az optimalitási kritériumok. A kapott gát és párosítás elvileg függhet az algoritmus futásától és a párosítás vonatkozásában ténylegesen ez is a helyzet; egy háromszög esetén páldául akármelyik maximális (:egy-élű) párosítást megadhatja. Annál meglepőbb, hogy az algoritmus által megtalált gát kizárólag a gráftól függ és független azoktól a választásoktól, amelyeket az algoritmus futása során tettünk. (Tehát például, ha az aktuális alternáló erdőt többféleképpen lehetett növelni, akkor a végül kapott gát nem függ attól, hogy melyik növelést választottuk.) Az algoritmus által talált gát éppen a Gallai-Edmonds tételben definiált kanonikus gáttal egyezik meg.

TÉTEL 3.16 (Gallai és Edmonds) Jelölje D(G) azon pontok halmazát, amelyeket G-nek valamely maximális párosítása nem fed le. Álljon A(G) a V − D(G) azon pontjaiból, melyeknek van D(G)-beli szomszédja, és legyen C(G) a maradék pontok halmaza. Ekkor A(G) gátja G-nek, éspedig éppen az, amelyet az algoritmus megtalál, D(G) a V − A(G) páratlan komponenseinek egyesítése, C(G) pedig a V − A(G) páros komponenseinek egyesítése. D(G) komponensei faktor-kritikus gráfok. Végül, ha eltöröljük a páros komponenseket és az A-ban lévő éleket, és a páratlan komponensek mindegyikét összehúzzuk egy-egy pontra, akkor olyan páros gráfot kapunk, amelyben az A minden X nemüres részhalmazának legalább |X| + 1 szomszédja van.

Biz. Tetszőleges A′ gáthoz jelölje D′ a G−A′ páratlan komponenseinek únióját, C′ pedig a párosakét. Tetszőleges maximális M′ párosítás esetén az M′ lefedi a X′-t és C′-t. Ezért D(G) biztosan része D′-nek.

Legyen most A′ az algoritmus által talált gát. Csak azt kell kimutatnunk, hogy a külső pontok ősképének (ami D′) minden v elemét fedetlenül hagyja valamely maximális elemszámú párosítás. Az 3.15 tétel szerint tudjuk, hogy egy külső pont ősképe M-kritikus, ezért létezik v-ből az alternáló fa gyökerébe egy P páros élszámú M-alternáló út. Ekkor P és M szimmetrikus differenciája egy maximális párosítás, amely elkerüli v-t.

A tétel utolsó részéhez azt figyeljük meg, hogy az algoritmus által talált alternáló erdőben a belső pontok akármely X részhalmazának legalább |X + 1| külső pont szomszédja van. Ez pedig azért van így, mert a belső pontok másodfokúak, és ha mindegyik z belső pontra a belőle kiinduló uz, vz élt az uv éllel helyettesítjük, akkor egy erdőt kapunk, amelyre az állítás azt jelenti, hogy egy erdő tetszőleges X élhalmaza legalább |X| ponttal érintkezik. Ez pedig közismert és egyszerű. •

Feladat 3.6 Tekintsünk egy olyan gátat, amelyre az elhagyásával keletkező páratlan komponensek úniója minimális. Igazoljuk, hogy ez éppen a Gallai-Edmonds tételében lévő gát.

3.4 Minimális súlyú teljes párosítás keresése

Legyen adva a G = (V, E) gráf élein c nemnegatív költség-függvény, és tegyük fel G-nek létezik teljes párosítása. Az alábbiakban páratlan vágáson olyan vágást értünk, melynek két partja páratlan sok pontot tartalmaz.

A duális probléma: rendeljünk páratlan vágásokhoz változókat, melyek nemtriviális vágáson nemnegatívak és minden e élre az élt tartalmazó páratlan vágások változóinak összege legfeljebb c(e), az él költsége. Az így hozzárendelt változókat megengedettnek hívjuk. (Egy páratlan vágás triviális, ha egyik oldala egypontú.)

Azaz,

∑(y_{B} : e ∈ B) ≤ c(e) minden e élre,  (∗)

ahol az összegzés a B páratlan vágásokra megy.

Az élhalmazon egy súlyozást páros körösszegűnek nevezünk, ha egészértékű és minden kör súlya páros szám. Ha y egészértékű, akkor a (∗) baloldalán szereplő érték az élhalmazon páros körösszegű súlyozást definiál.

Legyen c_{y}(e) := c(e) − ∑(y_{B} : e ∈ B). y megengedettsége azt jelenti, hogy c_{y} nemnegatív. Egy e élt, amelyre c_{y}(e) = 0 telítettnek vagy pontosnak fogunk hívni.

TÉTEL 3.17 Teljes párosítás minimális költsége egyenlő max{∑[y_{B} : y megengedett duális megoldás]}. Amennyiben c páros körösszegű, úgy az optimális y választható egészértékűnek.

Biz. Egyszerű becslés mutatja, hogy tetszőleges teljes párosítás költsége legalább akkora, mint a duális változók összege. Az egyenlőség kimutatásához megkonstruálunk egy M teljes párosítást és egy y megengedett duális megoldást, melyekre egyenlőség áll. Ez pedig pontosan akkor áll fenn, ha teljesül a következő két optimalitási kritérium.

1. M minden éle telített.

2. Minden B páratlan vágásra, amelyre y_{B} > 0, fennáll, hogy |B ∩ M| = 1.

Az azonosan 0 duális megoldásból indulunk ki, ami nyilván megengedett. Az általános lépésben adott a következő alakú megoldás. Legyen F a csúcsok részhalmazainak olyan lamináris rendszer, melynek minden tagja páratlan elemszámú, és bármely tagjára az abban lévő maximális tagokat összehúzva a telített élek faktor-kritikus gráfot alkotnak. Egy B nemtriviális páratlan vágásra y_{B} akkor és csak akkor pozitív, ha B-t az F nem egyelemű tagja definiálja.

Jelölje G′_{0} az F maximális tagjai összehúzásával keletkező és csak telített éleket tartalmazó gráfot. Legyen adva G′_{0}-nek egy M′ párosítása.

1. eset Amennyiben M′ a G′_{0}-nek teljes párosítása, akkor az F tagjain kintről befelé haladva egyenként végigmegyünk, és M′-t kiegészítjük a G telített élekből álló teljes párosításává, amely F minden tagjába pontosan egy éllel lép be.

2. eset Ha M′ nem teljes, akkor G′_{0}-ban valamely szabad pontból építünk egy F alternáló fát. (Ez egy apró különbség a ”nem-súlyozott” algoritmushoz képest, ahol alternáló erdőt építettünk.) A következő esetek lehetnek.

1. M′ növelése. F külső pontjából vezet G′_{0}-beli él szabad pontba. Ez meghatároz egy növelő utat. E mentén cserélve egy M′-nél eggyel nagyobb párosítást kapunk és erre nézve iteráljuk az eljárást.

A maximális elemszámú párosítást kereső algoritmushoz képest van egy fontos különbség. Ott, amikor alternáló utat találtunk, végrehajtjuk a növelést és az új, megnövelt párosítással mindent előlről kezdünk. Tehát eldobjuk a régi M-re felépített alternáló erdőt, az összehúzásokat, stb. Most, ha egy növelést végrehajtunk, akkor az eddigi alternáló fát ugyan eldobjuk, de a korábbi összehúzásokat megtartjuk. Ez azt jelenti, hogy az M′ vizsgálatakor már vannak G′_{0}-ban olyan pontok, melyek az M′ előtt lettek összehúzva. Így most előfordulhat, hogy az F alternáló fának belső pontja is (korábban) összehúzott pont.

2. Fa növelés. F egy külső u pontjából egy tisztáson lévő v pontba vezet G′_{0}-nek éle. Ekkor az uv élt és a vμ(v) élt a fához vesszük.

3. F két külső pontja között vezet él G′_{0}-ben. A keletkező páratlan kört összehúzzuk. Az új pont F külső pontja lesz.

4. Amennyiben az 1-2-3 lépések egyike sem hajtható végre, akkor megváltoztatjuk az y-t a következőképpen. A külső pontok ősképének duál-változóját növeljük, a belső pontok ősképének duál-változóját csökkentjük ugyanazzal az alább meghatározandó Δ értékkel. Minden külső pont ősképét F-hez vesszük.

Legyen z belső pont korábban összehúzott pont, legyen zv a z-vel szomszédos M-beli él, és zu a z-vel szomszédos másik fabeli él. Amennyiben z ősképének a duál-változója nullává válik, akkor a z pont Z-vel jelölt ősképét kihagyjuk F-ből. Ezenkívül z-t visszafújjuk abban az értelemben, hogy helyettesítjük azzal a C gráffal, amely a Z-ben lévő 0 módosított költségű élek gráfjából keletkezik az F maximális Z-ben fekvő tagjainak összehúzásával. F definíciója miatt a C gráf faktor-kritikus. Legyen v′ a C-nek olyan pontja, melyre vv′ telített él (vagyis az az él, mely a zv élt definiálta) és legyen M_{C} a C − v′ egy teljes párosítása. Vegyük M-hez az M_{C} elemeit. Ezenkívül a C-ben vegyünk egy M_{C}-ben alternáló P utat a v′ pont és az u pont között (ilyen van, mert C faktor-kritikus). Most a G′_{0}-ben lévő alternáló fa a P úttal együtt a z felfújásával keletkezett gráfban alternáló fát alkot.

Mekkora legyen Δ? Az alábbi m_{1}, m_{2}, m_{3} mennyiségek minimuma. Legyen m_{1} a külső pontokból a fán kívüli pontokba (azaz tisztás plusz többi szabad pont) menő G-beli (!) élek módosított költségeinek minimuma. Mivel a 2. lépés nem volt alkalmazható, m_{1} pozitív. Legyen m_{2} a fában szereplő összehúzott belső pontok duálváltozóinak minimuma. Végül legyen m_{3} az F fa külső pontjait összekötő G-beli élek módosított költségének minimumának a fele. Mivel a 3. lépés nem volt alkalmazható, az m_{3} pozitív.

Alapvető megfigyelés, hogy bármely uv élnek, amelyik a fában két külső pontot köt össze, a módosított költsége páros. Ez azért van így, mert uv a fában egy olyan G′_{0}-beli C kört definiál, melynek minden más éle telített, azaz 0 módosított költségű. Mármost bármely összehúzott pont ősképe a telített éleken összefüggő, így a C körből előállítható az eredeti G gráf egy köre, melynek minden éle, az uv él (ősképének) kivételével, telített. De a páros körösszeg tulajdonság miatt ebből következik, hogy c_{y}(uv) páros.

Ezen megfontolásból alapján m_{3} is egész szám. Könnyen látszik, hogy az új duális megoldás is megengedett. Az algoritmust az új párosításra, az új alternáló fára és az új duál-változókra iteráljuk.

Milyen lépés-szám becslés adható a fenti algoritmusra? A szabad pontok száma sohasem növekszik és párosítás növeléskor csökken. Nevezzük az algoritmus két párosítás növelés közötti részét fázisnak. Nyilván legfeljebb n/2 fázis lehetséges.

Egy fázison belül minden összehúzás külső pontot eredményez. Mivel mindig csak belső pontot fújunk fel, csak olyan pont felfújására kerülhet sor, amelyet korábbi fázisban húztunk össze. Ezért egy fázis O(m) lépést igényel.

Feladat 3.7 Igazoljuk, hogy az algoritmus során a páratlan kör összehúzása a páros körösszeg tulajdonságot nem rontja el.

file: lmatch

3.5 Minimális költségű áramok

Legyen D = (V, A) egy n csúcsú és m élű irányított gráf, az élein f : A → R alsó és g : A → R felső korlátokkal, melyekre f ≤ g. A korlátokon kívül adott még egy c : A → R költség-függvény is. Egy x áram költségén a cx skaláris szorzatot értjük. Az x megengedett, ha f ≤ x ≤ g. Határozzuk meg a legkisebb költségű megengedett áramot!

Adott x áramhoz definiáljuk a D_{x} = (V, A_{x}) segédgráfot és a c_{x} módosított költség-függvényt a következőképpen. Egy uv él akkor tartozzék A_{x}-hez, ha vagy (i) uv ∈ A, x(uv) < g(uv) és ekkor legyen c_{x}(uv) := c(uv) (A_{x} előre éle), vagy ha (ii) vu ∈ A, x(vu) > f(vu) és akkor legyen c_{x}(uv) := −c(vu) (A_{x} hátra éle).

TÉTEL 3.18 Az x megengedett áramra a következők ekvivalensek. (a) x minimális költségű, (b) D_{x}-ben nincs negatív kör, (c) létezik egy π : V → R potenciál, melyre

π(v) − π(u) ≤ c(uv), ha x(uv) < g(uv) (uv ∈ A),  (i)

és

π(v) − π(u) ≥ c(uv), ha x(uv) > f(uv) (uv ∈ A).  (ii)

Biz. (a)=>(b). Ha D_{x}-ben létezik C negatív kör, akkor annak előre éleinek megfelelő D-beli éleken növeljük, hátra éleinek megfelelőkön pedig csökkentsük x-t ε-nal. Amennyiben ε kicsiny pozitív szám, a keletkező x′ megengedett áram lesz, amelynek költsége (C negativitása miatt) kisebb, mint x költsége.

(b)=>(c). Használjuk azt a korábban megismert tételt, hogy ha egy irányított gráfban nincsen negatív kör, akkor létezik megengedett potenciál. A D_{x} gráfban egy π potenciálnak a c_{x}-re vonatkozó megengedettsége pontosan az (i) és (ii) feltételekkel ekvivalens! (Ez tehát valójában a (b) és (c) ekvivalenciáját bizonyítja.)

(c)=>(a). Tegyük fel π teljesíti az (i) és (ii) feltételeket. Legyen c̄(uv) := c(uv)−π(v)+π(u). Ekkor tetszőleges z megengedett áramra cz = c̄z = ∑[c̄(uv)z(uv) : c̄(uv) > 0] + ∑[c̄(uv)z(uv) : c̄(uv) < 0] ≥ ∑[c̄(uv)f(uv) : c̄(uv) > 0] + ∑[c̄(uv)g(uv) : c̄(uv) < 0] = ∑[c̄(uv)x(uv) : c̄(uv) > 0] + ∑[c̄(uv)x(uv) : c̄(uv) < 0] = c̄x = cx. •

Az (i) és (ii) feltételeket hívják optimalitási kritériumoknak. A tétel a következő algoritmust sugallja.

Körjavító algoritmus minimális költségű áram kiszámítására

Induljunk ki egy tetszőleges x megengedett áramból. Ha D_{x}-ben nincs negatív kör, akkor készen vagyunk: a 3.18 tétel szerint az adott x áram minimális költségű. Ha van negatív kör, akkor ezen C kör mentén cseréljük ki x-et úgy, hogy D azon élein, melyek a C előre éleinek felelnek meg, Δ-val növeljük, míg a C hátra éleinek megfelelő D-beli éleken az x értékét Δ-val csökkentjük, ahol

Δ = min{Δ_{1}, Δ_{2}}

és Δ_{1} a C előre éleinek megfelelő D-beli éleken a g(uv)−x(uv) minimuma, Δ_{2} pedig a C hátra éleinek megfelelő D-beli éleken az x(uv)−f(uv) minimuma. Nevezzünk egy ilyen változtatást a C kör mentén való javításnak. Iteráljuk az eljárást a létrejött új áramra vonatkozólag.

Hasznos megfigyelni, hogy ha D_{x} egy C köre mentén javítva az y áramot kapjuk, akkor D_{y} úgy kapható meg D_{x}-ből, hogy a C kör minden élét fordítva betesszük, ha még nem volt benn, továbbá a C kör bizonyos éleit kitöröljük, éspedig azokat, amelyeken a Δ felvétetik.

Miután Ford és Fulkersonnak a maximális folyam megkeresésére vonatkozó közismert alternáló utas algoritmusa a körjavító eljárás speciális esetének tekinthető, amelyben az út mentén történő folyamnövelés éppen egy kör mentén történő javításnak felel meg, és a Ford-Fulkerson féle eljárás köztudottan nem polinomiális futásidejű (sőt valós kapacitások esetén még csak nem is feltétlenül véges), a körjavító áram algoritmus sem polinomiális.

Tudjuk azonban, hogy a Ford-Fulkerson algoritmusnak az Edmondstól és Karptól illetve Dinitstől származó változata, amelyben mindig az aktuális segédgráf legrövidebb javító útját használjuk, már erősen polinomiális. Ennek egyfajta általánosításaként A. Goldberg és R.E. Tarjan azt javasolta, hogy a körjavító algoritmusban mindig az aktuális c_{x} költségre vonatkozó minimális átlagú kör mentén javítsunk. Megjegyzendő, hogy például Karp módszerével tetszőleges költségfüggvény esetén a minimális átlagú kört erősen polinom időben ki lehet számítani, és ezt az eljárást a továbbiakban szubrutinként használjuk.

TÉTEL 3.19 (Goldberg és Tarjan) Amennyiben mindig a minimális átlagú kör mentén történik a javítás, úgy bármely megengedett áramból indulva a körjavító algoritmus O(nm^{2} log n) javítás után minimális költségű áramot szolgáltat.

Biz. Bár a bizonyítás több ponton is analógiát mutat az Edmonds-Karp-Dinits algoritmus helyességének bizonyításával, újfajta megfigyelésekre is szükségünk lesz. Egy egyszerű észrevétellel kezdjük.

Lemma 3.20 Legyenek z és y megengedett áramok, melyekre valamely uv élen z(uv) < y(uv). Ekkor létezik D_{z}-ben olyan uv-n átmenő C irányított kör, amelynek megfordítása benne van D_{y}-ban.

Biz. Ekkor s := y − z áram, és így s a D azon éleire megszorítva is áram, melyeken s(e) ≠ 0. Fordítsuk meg D azon éleinek irányítását, melyeken s negatív és ezen éleken negáljuk s-t. A keletkező s′ függvény a keletkező D′ digráf élein áramot alkot, amely mindenütt pozitív. Mivel egy pozitív áram előáll irányított körök (karakterisztikus vektorainak) pozitív lineáris kombinációjaként, van olyan C irányított kör a D′-ben, amely átmegy az uv élen.

Ha C egy h = ab élére s(h) > 0, akkor g(h) ≥ y(h) > z(h) ≥ f(h), és ezért ab benne van D_{z}-ben és ba benne van D_{y}-ban. Hasonlóképp, ha C egy h = ab élére s(h) < 0, akkor f(h) ≤ y(h) < z(h) ≤ g(h), és ezért ba benne van D_{z}-ben és ab benne van D_{y}-ban.

Emiatt C benne van D_{z}-ben és C megfordítása benne van D_{y}-ban, azaz C eleget tesz a lemma követelményének. •

Készítsük el D segítségével a következő H = (V, A^{∗}) digráfot. A D minden uv éléhez, amelyre f(uv) < g(uv), tegyük A^{∗}-ba az uv élt d(uv) := c(uv) költséggel és a vu élt d(vu) := −c(uv) költséggel. A D_{x} segédgráf tehát mindig a H részgráfja, és c_{x} a d megszorítása A_{x}-re. Jegyezzük meg, hogy H szimmetrikus abban az értelemben, hogy minden uv éllel együtt vu is benne van, továbbá a d költségfüggvény antiszimmetrikus, azaz H minden uv élére d(uv) = −d(vu).

Legyen π : V → R tetszőleges potenciál. Definiáljuk H-nak mindegyik uv élére a d_{π}(uv) := d(uv)−π(v)+π(u) eltolt költséget. Nyilván d_{π} is antiszimmetrikus. Tetszőleges áramnak, speciálisan minden körnek, az eltolt költsége ugyanannyi, mint az eredeti. A fenti optimalitási kritérium azzal ekvivalens, hogy a D_{x} minden e élére d_{π}(e) ≥ 0. Amennyiben tehát x nem optimális, úgy bármely π potenciálra lesz olyan e él D_{x}-ben, amelyre d_{π}(e) negatív. Azt a szemléletes érzetet fogjuk kiaknázni, hogy minél közelebb vannak ezek a negatív számok a 0-hoz, annál közelebb vagyunk az optimalitási kritériumok teljesüléséhez. A továbbiakban, hacsak az ellenkezőjét nem mondjuk, mindig feltesszük, hogy a szóbanforgó áram nem optimális, azaz a hozzátartozó segédgráfban van negatív kör.

Definíció. Az x áram és π potenciálból álló (x, π) pár hibája az ε(x, π) = − min{d_{π}(e) : e ∈ A_{x}} szám. Egy x áram ε(x) hibája ε(x) := min{ε(x, π) : π potenciál}. A minimalizáló potenciált π_{x}-szel jelöljük.

Lemma 3.21 Az x áram hibája egyenlő a c_{x}-re vonatkozó D_{x}-beli minimális körátlag −1-szeresével.

Biz. A definíció miatt D_{x} minden e élére d_{π_{x}}(e) ≥ −ε(x), és így D_{x}-ben a minimális körátlag legalább −ε(x). Megfordítva, ha D_{x}-ben a minimális körátlag −ε′, akkor a d′(e) := d(e)+ε′ (e ∈ A_{x}) költségre nézve D_{x}-ben nincs negatív kör. Így létezik π potenciál, melyre π(v)−π(u) ≤ d′(uv), minden uv ∈ A_{x} élre. Ez épp azt jelenti, hogy az (x, π) pár hibája legfeljebb ε′, és így ε(x) ≤ ε′. •

Hangsúlyozzuk tehát, hogy a D_{x} digráfban minden él d_{π_{x}}-költsége legalább −ε(x), és a minimális átlagú kör minden élének a d_{π_{x}}-költsége −ε(x).

Lemma 3.22 Minimális d-átlagú kör mentén javítva az áram hibája nem nő.

Biz. A 3.21 lemma szerint D_{x}-ben a minimális körátlag −ε(x). Ekkor d_{π_{x}}(uv) ≥ −ε(x) minden uv ∈ A_{x} élre és a minimális átlagú C_{x} kör minden e élére d_{π_{x}}(e) = −ε(x). C_{x} mentén javítva a keletkező D_{y} segédgráfban csak a C_{x} néhány élének megfordítottja lehet új él. Ezek d_{π_{x}}-költsége +ε(x), vagyis D_{y}-ban minden él d_{π_{x}}-költsége legalább −ε(x), és így y hibája legfeljebb ε(x). •

Belátjuk, hogy a javítások során az áram hibája nemcsak, hogy nőni nem tud, de m javítás során már bizonyosan csökkenni fog. Legyen x egy megengedett áram. A H egy irányított körét nevezzük teljesen negatívnak, ha a kör minden élének d_{π_{x}}-költsége negatív. (Ez a fogalom tehát a megadott x áramra vonatkozik.)

Lemma 3.23 Tetszőleges x megengedett áramból kiindulva nem több, mint m javítás után olyan x′ áram keletkezik, amelyre

ε(x′) ≤ ε(x)(1 − 1/n).  (3.10)

Biz. Legyen ε := ε(x). Amint már említettük, D_{x}-ben egy C_{x} minimális átlagú javító kör valamennyi élének d_{π_{x}}-költsége −ε, tehát C_{x} teljesen negatív. Tekintsük x-től kezdődően az egymást követő javításokat egészen addig, amíg a használt javító körök teljesen negatívak. A keletkező áramot jelölje x′. Mivel teljesen negatív kör mentén történő javításkor a segédgráfból legalább egy negatív él kiesik és negatív él nem jön be, az ilyen javítások száma legfeljebb a D_{x}-beli negatív élek száma, vagyis legfeljebb m.

Készen vagyunk, ha x′ már optimális, azaz hibája 0. Tegyük fel, nem ez a helyzet, és legyen C_{x′} a D_{x′}-ben az algoritmus által használt minimális átlagú kör. Mivel ez már nem teljesen negatív, C_{x′} valamely e élére d_{π_{x}}(e) ≥ 0. A megelőző, teljesen negatív körök mentén történt javítások során a segédgráfhoz csak olyan f élek jöttek, melyekre d_{π_{x}}(f) > 0, ezért a C_{x′} minden olyan h éle, melyre d_{π_{x}}(h) < 0, benne van a kiindulási D_{x}-ben. Így d_{π_{x}}(C_{x′}) ≥ 0+(|C_{x′}|−1)(−ε), tehát d_{π_{x}}(C_{x′})/|C_{x′}| ≥ (1 − 1/|C_{x′}|)(−ε) ≥ (1 − 1/n)(−ε). Azt kaptuk, hogy legfeljebb m javítás után az előálló D_{x′}-ben a minimális körátlag legalább (1 − 1/n)(−ε), azaz x′ hibája az x hibájának legfeljebb (1 − 1/n)-szerese. •

Legyen K := mn⌈log(2n)⌉. Egy x megengedett áramból kiindulva jelölje z a K javítás után keletkező áramot. π_{z} jelölte azt a potenciált, amelyre ε(z) = ε(z, π_{z}).

Lemma 3.24 ε(z) ≤ ε(x)/2n.

Biz. A 3.23 lemma szerint a hiba m javítás után az (1 − 1/n)-szeresére csökken, így mn javítás után az (1 − 1/n)^{n}-szeresére. Mivel (1 − 1/n)^{n} = 1/[1 + 1/(n − 1)]^{n} ≤ 1/2, így a hiba mn javítás után legfeljebb a felére csökken. Amiből adódik, hogy minden r > 0 egészre mnr javítás után a hiba az 1/2^{r}-szeresére csökken, speciálisan r = ⌈log(2n)⌉-re, K javítás után a (2n)-ed részére. •

Lemma 3.25 A D_{x}-ben használt C_{x} javító körnek a minimális c_{π_{z}}-költségű vu éle olyan, hogy a neki megfelelő D-beli élen az áram értéke a z áramot követő javítások során már nem változik.

Biz. Mivel C_{x}-nek a d_{π_{x}}-átlaga −ε(x), így a d_{π_{z}}-átlaga is −ε(x). Ebből és a 3.24 lemmából d_{π_{z}}(vu) ≤ −ε(x) ≤ −2nε(z) < −ε(z). Tegyük fel, hogy vu mondjuk hátra éle D_{x}-nek. (Analóg módon kezelhető az az eset, ha előre éle). Ekkor uv ∈ A és d_{π_{z}}(vu) < −ε(z) miatt vu nem lehet D_{z}-ben, és ezért z(uv) = f(uv). Indirekt, tegyük fel, hogy az algoritmus később egy olyan y áramot talál, amelyre y(uv) > z(uv). A 3.22 lemma miatt y hibája legfeljebb ε(z).

Tekintsük a 3.20 lemma által biztosított, uv-n áthaladó C kört, melynek megfordítottját jelölje C′. A lemma szerint C benne van D_{z}-ben, C′ pedig D_{y}-ban. Mivel d_{π_{z}}(uv) = −d_{π_{z}}(vu) ≥ 2nε(z), kapjuk, hogy −d(C′) = d_{π_{z}}(C) ≥ 2nε(z)+(n−1)(−ε(z)) = (n+1)ε(z), azaz d(C′) ≤ −(n+1)ε(z) < −|C′|ε(z), vagyis C′ átlaga kisebb, mint −ε(z), ellentmondásban azzal, hogy y hibája legfeljebb ε(z). •

Megállapítottuk tehát, hogy egy x áramból kiindulva K javítást követően egy élen az áram értéke rögzül. Ezért legfeljebb mK javítás után már nem létezhet javítás, azaz minimális költségű áramot kaptunk. • •

Feladat 3.8 Mutassuk meg, hogy a maximális folyam meghatározására szolgáló Edmonds-Karp-Dinits algoritmus a körjavító algoritmus speciális esetének tekinthető.

2003. május 22.file: lminaram

3.6 A Lucchesi-Younger tétel algoritmikusan

Korábban már találkoztunk a Lucchesi-Younger tételnek a kikeresztezési technikán alapuló nemalgoritmikus bizonyításával. Jelen célunk egy algoritmikus bizonyítás leírása, amelynek segítségével polinom időben kiszámítható a szóbanforgó minimum illetve maximum. Az alábbiakban irányított vágások egy lefogását irányított kötésnek vagy röviden kötésnek fogjuk hívni.

TÉTEL 3.26 (Lucchesi és Younger) Legyen D = (V, A) irányított gráf. Az élidegen irányított vágások maximális ν száma egyenlő a minimális kötés τ elemszámával.

Biz. Feltehetjük, hogy D irányítatlan értelemben összefüggő. Ekkor egy F élhalmaz pontosan akkor kötés, ha elemeinek összehúzása erősen összefüggő digráfot eredményez, tehát τ azon élek minimális száma, amelyeket összehúzva, vagy ekvivalensen fordítva is behúzva, eöf. digráfot kapunk. Nyilván ν ≤ τ. Az egyenlőség igazolásához leírunk egy algoritmust, amely megkonstruál egy F kötést és |F | darab élidegen irányított vágást.

Nevezzük pontok egy X részhalmazát magnak, ha nem lép bele él. Az X-ből kilépő élek Δ(X) halmazát (ha nemüres) neveztük irányított vágásnak. Egyszerűen látszik, hogy a magok metszetre-unióra zárt rendszert alkotnak. Valamely X magra jelölje c(X) az X elhagyásával keletkező komponensek számát. Nyilván c(V) = 0 és c(∅) = 1.

Lemma 3.27 A magokon értelmezett c függvény szupermoduláris.

Biz. Legyen ĉ(X) := c(V − X). Elegendő azt belátni, hogy d(X, Y) = 0 esetén a szupermodularitási egyenlőtlenség fennáll ĉ-re. Tekintsük az X és Y halmazok által feszített élek I(X) és I(Y) halmazát. Miután d(X, Y) = 0,

I(X ∪ Y) = I(X) ∪ I(Y) és I(X ∩ Y) = I(X) ∩ I(Y).  (3.11)

Jelölje r a irányítatlan értelemben vett gráf körmatroidjának rangfüggvényét. Mivel r szubmoduláris és r(I(X)) = |X| − ĉ(X), a ĉ és így a c szupermodularitása is következik. •

Legyen c′(X) ugyanaz, mint c(X), azzal az eltéréssel, hogy c′(∅) = 0. Ekkor c′ metsző szupermoduláris. Rögtön látszik, hogy egy F ⊆ A kötésre és X magra δ_{F} (X) ≥ c′(X), ahol δ_{F} (X) az X-ből kilépő F -beli élek számát jelöli. (Ez az egyenlőtlenség az üres X halmaz kivételével a c függvényre is igaz. Azért kell a c helyett a c′-vel dolgoznunk, hogy az egyenlőtlenség mindenhol érvényes legyen).

Egy X magot illetve a hozzá tartozó Δ(X) irányított vágást pontosnak hívunk (F -re nézve), ha c′(X) = δ_{F} (X). Amennyiben δ_{F} (X) = 1, 1-pontos magról ill. vágásról beszélünk. Látható, hogy minden pontos vágás, melynek X magja nem üres és nem V, felbomlik diszjunkt 1-pontos vágások uniójára (éspedig a D − X komponensei által meghatározott vágásokra), továbbá X 1-pontos magok metszete. A definícióból adódóan V mindig pontos. A szokásos technikával igazolható, hogy:

Lemma 3.28 Metsző pontos magok metszete és uniója pontos. •

Ebből rögtön következik, hogy egy v pontot tartalmazó pontos halmazok B(v) metszete pontos. A B(v) halmaz tehát a v-t tartalmazó egyértelmű legszűkebb pontos halmaz.

Feladat 3.9 Igazoljuk, hogy B(u) egyenlő az u-t tartalmazó 1-pontos magok metszetével. Igazoljuk, hogy B(u) pontosan azon csúcsok halmaza, amelyekből vezet u-ba két élidegen út abban a digráfban, amely D-ből keletkezik az F éleinek megfordításával és minden eredeti él párhuzamos duplázásával. Adjunk algoritmust B(u) meghatározására.

Gyakorlat 3.10 Pontos halmazokból álló összefüggő hipergráf ponthalmaza is pontos.

Az algoritmus teszőleges F kötésből indul ki (ami kezdetben lehet például egy feszítő fa). Az általános lépésben vagy egy kisebb kötést talál, vagypedig |F | élidegen irányított vágást. Készítsünk el egy D′ = (V, A′) segédgráfot, az élein egy d költség-függvénnyel, a következőképpen. A − F minden eleme A′-höz tartozik és a költsége +1. Az F elemeit megfordítva tegyük A′-be és ezen fordított élek költsége legyen −1. Végül minden v pontból vezessünk B(v) minden pontjába egy 0 költségű ún. ugró élt. Az előbbi feladat alapján uv akkor és csak akkor ugró él, ha nem lép ki 1-pontos magból. (A definícióból következik, hogy minden eredeti A − F -beli él megfordítottja ugró él lesz.)

A közismert algoritmussal döntsük el, hogy létezik-e D′-ben a d költség-függvényre nézve negatív kör. Keressünk egyet, ha van, illetve keressünk egy π megengedett (egészértékű) potenciált, ha nincs.

1. eset D′-ben nincs negatív kör, azaz létezik π megengedett potenciál.

Mivel a π konstanssal történő eltolása a megengedettséget nem befolyásolja, feltehető, hogy π minimális értéke 0. Legyen V_{i} := {v : π(v) ≤ i}.

Semelyik V_{i}-ből nem lép ki ugró él, mert ha uv ilyen volna, akkor π(v) > π(u), azaz π(v) − π(u) > 0 = d(uv) állna, ellentétben a π megengedettségével.

Következik, hogy egy uv ∈ A − F él nem lép be semelyik V_{i}-be, hiszen uv megfordítottja ugró él. Ráadásul uv legfeljebb csak egy V_{i}-ből léphet ki, hiszen uv benne van A′-ben +1 költséggel, tehát π(v) − π(u) ≤ 1.

Bármely uv ∈ F él legalább egy V_{i} halmazból kilép, hiszen vu benne van A′-ben −1 költséggel, és így π(u) − π(v) ≤ d(vu) = −1, vagyis π(v) − π(u) ≥ 1. Ebből az is adódik, hogy V_{i}-be nem lép be F -beli él, vagyis minden V_{i} mag.

Lemma 3.29 A V_{i} maghoz tartozó Δ(V_{i}) irányított vágás felbontható 1-pontos diszjunkt irányított vágások uniójára.

Biz. Mivel V_{i}-ből nem lép ki ugró él, minden v ∈ V_{i} pontra B(v) ⊆ V_{i}, és ezért a {B(v) : v ∈ V_{i}} hipergráf komponenseinek A_{1}, …, A_{l} ponthalmazai a V_{i} partícióját alkotják. A fenti gyakorlat alapján mindegyik A_{j} mag pontos, továbbá a Δ(A_{j}) vágások partícionálják a Δ(V_{i}) vágást. Miután minden pontos vágás diszjunkt 1-pontos vágások uniója, a lemma következik. •

Ha tehát az 1. eset áll fenn, akkor találtunk irányított vágásoknak egy olyan rendszerét, amelynek minden tagját F pontosan egyszer fogja le, minden A − F beli él legfeljebb egyikükben van benne, minden F -beli él pedig legalább egyikükben. Ekkor mindegyik F -beli élhez a rendszerből egy olyat kiválasztva, amelyben ő benne van, |F | darab páronként élidegen irányított vágást kapunk.

2. eset A D′ segédgráfban létezik negatív kör.

Legyen C olyan negatív kör, amelynek a legkevesebb éle van. Itt a minimalitást csak annyiban fogjuk használni, hogy nincs C-nek két olyan nem egymást követő a, b pontja, amelyekre a-ból b-be vezet ugró él és a körön a b-től a-ig vezető P ív költsége negatív. Ilyen ugró él létezése esetén ugyanis P + ab egy kisebb élszámú negatív kört adna. (Tehát tetszőleges negatív körből kiindulva az ilyen értelmű minimális negatív kört algoritmikusan is könnyen megkaphatjuk.)

Lemma 3.30 A C ugró élei elrendezhetők egy olyan e_{1} = u_{1}v_{1}, e_{2} = u_{2}v_{2}, …, e_{k} = u_{k}v_{k} sorba, hogy semelyik u_{i}-ből nem vezet ugró él v_{j}-be, ahol i < j.

Biz. C minden ugró élének feleltessünk meg egy pontot és valamely x pontból egy másik y-ba vezessünk élt, ha az x-hez tartozó ugró él tövéből vezet ugró él az y-hoz tartozó ugró él fejébe. Amennyiben az így kapott irányított segédgráf aciklikus, úgy pontjai sorba rendezhetők hogy minden él a sorrendben visszefelé mutat, és egy ilyen sorrend éppen a lemma által előírt sorrendet adja.

Az, hogy a segédgráf tartalmaz irányított kört, azt jelenti, hogy C bizonyos ugró élei ciklikusan sorbarendezhetők az f_{1} = s_{1}t_{1}, f_{2} = s_{2}t_{2}, …, f_{m} = s_{m}t_{m} sorrendbe úgy, hogy s_{i}t_{j+1} ugró él (ahol t_{m+1} = t_{1}). Legyen C_{i} a C körnek az az íve, amely t_{i+1}-ből vezet s_{i}-be. A C-re tett minimalitási feltevés alapján C_{i} költsége nemnegatív.

Könnyen látható, hogy a C minden nem-ugró éle ugyanannyi C_{i} ívhez tartozik. Jelöljük ezt a számot t-vel (t > 0). Ebből következik, hogy a C költségének t-szerese a C_{i} ívek költségének összege, ami nemnegatív, ellentétben a C kör negatív voltával. •

Módosítsuk F -t a következőképpen. Hagyjuk ki belőle azokat az elemeket, amelyeknek megfordítottja (ami tehát D′-ben van) C-ben van, és vegyük hozzá A − F azon uv elemeit, amelyeknek megfelelő D′-beli uv élek C-ben vannak. A keletkezett halmazt jelölje F′. Miután C negatív kör volt, |F′| < |F |. Belátjuk, hogy F′ kötés.

Lemma 3.31 Az előbb definiált F′ élhalmaz kötést alkot.

Biz. Egy X mag többlete legyen γ(X) := δ_{F} (X) − c′(X). Ez mindig nemnegatív, hiszen F kötés, továbbá éppen akkor 0, ha X pontos. Jelölje δ^{u}(X) (illetve ϱ^{u}(X)) a C kör azon ugró éleinek a számát, melyek X-ből kilépnek (ill. X-be belépnek). δ^{u}(X) szerinti indukcióval belátjuk, hogy

γ(X) ≥ δ^{u}(X).

Az egyenlőtlenség δ^{u}(X) = 0 esetén semmitmondó, így legyen δ^{u}(X) > 0 és legyen e_{i} = u_{i}v_{i} a Cnek az az ugró éle, amely kilép X-ből és a 3.30 lemmában megadott sorrendben a legkisebb indexű. Legyen B := B(u_{i}). Ha most u_{j}v_{j} egy másik ugró éle C-nek, amely kilép X-ből, akkor j > i, és állítjuk, hogy v_{j} ∉ B. Ha ugyanis v_{j} B-ben volna, akkor u_{i}v_{j} is ugró él lenne, ellentétben a sorrendezés tulajdonságával. Így tehát δ^{u}(X ∪ B) = δ^{u}(X) − 1. Most γ(X) + 0 = γ(X) + γ(B) ≥ γ(X∩B)+γ(X∪B) ≥ 1+γ(X∪B) ≥ 1+δ^{u}(X∪B) = δ^{u}(X), ahol az utolsó egyenlőtlenség az indukciós feltevésből adódik. Ebből kapjuk, hogy δ_{F′}(X) = δ_{F} (X) + ϱ^{u}(X) − δ^{u}(X) ≥ δ_{F} (X) − δ^{u}(X) ≥ c′(X).

• •

A 2. eset fennállásakor tehát egy olyan kötést találtunk, amely kisebb a kiindulási kötésnél. Emiatt, ha az eljárást iteráljuk, a 2. eset legfeljebb n − 1 előfordulása után bizonyosan az 1. eset következik be. • • •

3.7 Győri tétele algoritmikusan

Az alábbiakban algoritmikus bizonyítást adunk Győri tételére, amelyre a Válogatott fejezetek c. előadáshoz írott jegyzetben már szerepelt egy nem konstruktív bizonyítás. A jelöléseket és a tételt megismételjük.

Legyen P = (v_{0}, e_{1}, v_{1}, e_{2}, v_{2}, …, e_{n}, v_{n}) egyszerű irányított út, ahol az e_{i} irányított él töve v_{i−1} és feje v_{i}. Jelöljük a P csúcsainak halmazát V -vel. Legyen F := {F_{1}, …, F_{k}} a P részútjainak egy rendszere. A következőkben úton általában az út élhalmazát értjük. Egy I út kezdőpontját b(I)-vel, végpontját pedig j(I)-vel jelöljük.

Azt mondjuk, hogy P részútjainak egy B rendszere generálja F-t vagy hogy B generátora F-nek, ha F minden tagja előáll néhány B-beli út egyesítéseként. Például F saját magának generátora, és az egyelemű utakból álló {e_{1}, …, e_{n}} rendszer is generálja F-t. Jelölje γ(F) az F generátorainak minimális elemszámát.

Azt mondjuk, hogy egy F útból és annak egy e éléből álló (F, e) pár reprezentált utat alkot. Jelöljük F_{r}-rel az olyan (F, e) reprezentált utak halmazát, amelyekre F ∈ F.

Legyen I := {I_{1}, …, I_{t}} a P részútjainak egy családja és legyen R := {f_{1}, f_{2}, …, f_{t}} egy reprezentáló rendszer, azaz az f_{i} irányított élek különböző elemei P -nek és f_{i} ∈ I_{i} minden i = 1, …, t-re. Azt mondjuk, hogy R erős reprezentáló rendszer, ha I_{i} ∩ I_{j} nem tartalmazza f_{i} és f_{j} mindegyikét (i, j, 1 ≤ i < j ≤ t). Ebben az esetben a reprezentált utak {(I_{1}, f_{1}), (I_{2}, f_{2}), …, (I_{t}, f_{t})} családját függetlennek nevezzük. Az I := {I_{1}, …, I_{t}} erősen reprezentálható, ha létezik erős reprezentáns rendszere.

Jelölje σ(F) az F-ben lévő lévő erősen reprezentálható utak maximális számát. Könnyen látható, hogy ha R erősen reprezentálható útrendszer, akkor R-t nem lehet |R|-nél kevesebb úttal generálni. Ebből következik, hogy utak tetszőleges F rendszerére σ(F) ≤ γ(F). Győri tétele azt állítja, hogy itt valójában egyenlőség szerepel:

TÉTEL 3.32 (Győri Ervin) A P út részútjainak bármely F családjára fennáll σ(F) = γ(F).

Biz. Csak a nem-triviális σ ≥ γ egyenlőtlenséget igazoljuk.

Jelölje F_{r} a reprezentált utak halmazát. F_{r} egy (F, f) tagját lényegesnek mondjuk, ha nincs olyan F′ (≠ F) tagja F-nek, amelyre f ∈ F′ ⊂ F. F_{r} minden (F, f) lényeges tagjának megfeleltetünk egy (X_{K}, X_{B}) halmaz-párt, ahol X_{B} az F út f-t követő pontjaiból áll, míg V − X_{K} az F út f-t megelőző pontjaiból. Jelölje L_{F} az így kapott halmaz-párok családját.

Az algoritmus három fázisból áll. Az elsőben a lényeges párok L_{F} családjából kiválasztunk egy keresztezés-mentes K részrendszert. A második fázisban Dilworth tételt alkalmazzuk K-ra és az ismert algoritmus segítségével (amely a Dilworth tételnek Kőnig tételre való visszavezetésén és ezáltal az alternáló utas módszeren alapul) K-nak meghatározunk egy maximális I független részét valamint egy minimális lánc-felbontását. A láncfelbontás irányított élek egy olyan F rendszerének felel meg, amelyek lefogják az K-ban szereplő valamennyi halmaz-párt. Az algoritmus harmadik fázisában F -t átalakítjuk úgy, hogy elemszáma ne változzék és L_{F}-nek minden tagját lefogja.

1. Fázis Végigmegyünk a P út élein az e_{1}, …, e_{n} sorrendben és az L_{F} tagjait két csoportba soroljuk, K-ba és T -be. Kezdetben mindkét csoport üres. Az T tagjaira a későbbiek során, mint tiltott párokra hivatkozunk.

Az általános lépésben tekintjük az e_{i} élt és az összes (I_{1}, e_{i}), (I_{2}, e_{i}), …, (I_{k}, e_{i}) lényeges párt. Mivel ezen párok lényegesek, az I_{j} utak élhalmazai egymást nem tartalmazzák és a végpontjaik páronként különbözőek. Következésképp feltehető, hogy ezen utak úgy vannak indexelve, hogy b(I_{1}) < … < b(I_{k}) és j(I_{1}) < … < j(I_{k}). Mindegyik (I_{j}, e_{i}) nem tiltott párt bevesszük K-ba, és egy ilyen bevételkor letiltjuk (azaz T -be tesszük) az összes olyan (I_{h}, e_{l}) lényeges párt, amelyre j < h ≤ k, l > i és e_{l} ∈ I_{j}.

A konstrukcióból könnyen látszik, hogy az 1. fázis végén kapott K rendszer keresztezés-mentes lesz.

2. Fázis Alkalmazzuk a Dilworth tételt K-ra és számítsunk ki egy I ⊆ K független rész-rendszert és K-nak egy minimális lánc-felbontását, amely egy olyan F élrendszernek felel meg, amely K minden tagját lefogja, és amelyre |F | = |I|.

3. Fázis Amennyiben F lefogja L_{F} valamennyi tagját, akkor készen vagyunk. Tegyük fel tehát, hogy van olyan (I, f) lényeges pár, amelyet F nem fog le. Válasszuk (I, f)-t úgy, hogy az I-nek az f élt megelőző csúcsainak (I, f)^{−} halmaza minimális legyen. Mivel (I, f)-t F nem fogja le, így (I, f) tiltva lett (azaz T -be került), vagyis van a K-nak olyan (J, e) tagja, amelyre {e, f} ⊆ I ∩ J, e megelőzi f-t és J megelőzi I-t. Válasszunk egy ilyen (J, e) párt úgy, hogy (J, e)^{+} minimális legyen.

Az (I, f) és (J, e) párok lényegesek, így mind az (I, e), mind a (J, f) pár lényeges. Az (I, f)^{−} minimalitásából következik, hogy F lefogja az ((I, e)^{−}, (I, e)^{+}) párt.

Lemma 3.33 (J, f) ∈ K.

Biz. Amennyiben (J, f) tiltott volna, úgy az algoritmus előírása miatt volna egy (J′, e′) tagja K-nak úgy, hogy J′ megelőzi J-t és {e′, f} ⊆ J′ ∩ J. Nem lehet, hogy e′ megelőzi e-t, mert akkor (J, e) is tiltott lett volna, holott (J, e) ∈ K. Ezek szerint e′ vagy egyenlő e-vel, vagy követi e-t. De ekkor (J′, e′)^{+} ⊂ (J, e)^{+}, ellentétben (J, e)^{+} minimális választásával. •

Ezek alapján F lefogja mind (I, e)-t, mind (J, f)-t. Jelölje az (I, e)-t lefogó élt f_{1} = x_{1}y_{1} és a (J, f)-t lefogó élt f_{2} = x_{2}y_{2}. Legyen f′_{1} := x_{1}y_{2}, f′_{2} := x_{2}y_{1} és legyen F′ := F − {f_{1}, f_{2}} ∪ {f′_{1}, f′_{2}}. Mivel f_{1} és f_{2} sem fogja le (I, f)-t, a szóbanforgó pontok az alábbi sorrendben követik egymást.

b(J) ≤ x_{2} < b(I) ≤ x_{1} ≤ b(e) < y_{1} ≤ b(f) < y_{2} ≤ j(J) < j(I).  (12.1)

Ebből rögtön adódik, hogy az f′_{1} él lefogja az eddig lefogatlan (I, f) párt.

Lemma 3.34 Ha F lefogott egy (I′, f′) lényeges párt, akkor F′ is lefogja.

Biz. Ez nyilván így van, ha (I′, f′)-t az F -nek egy f_{1}-től és f_{2}-től különböző tagja fogta le. Az is rögtön látszik, hogy minden f_{2} által legfogott párt f′_{1} és f′_{2} valamelyike lefogja. Tehát az egyetlen problematikus eset az, amikor (I′, f′)-t az F -ből egyedül az f_{1} él fogja le.

Tegyük fel indirekt, hogy f′_{1} és f′_{2} egyike sem fogja le (I′, f′)-t. Abból hogy f′_{1} nem fogja le (I′, f′)-t, következik, hogy j(I′) < y_{2}. Abból hogy f′_{2} nem fogja le (I′, f′)-t, következik, hogy b(I′) > x_{2}. Ezért e ∈ I′ ⊆ J, ami ellentmond annak, hogy (J, e) lényeges pár. •

A lemmából kapjuk, hogy F′ szigorúan több lényeges párt fog le, mint amennyit F lefogott. Így a fenti átcserélési műveletet legfeljebb annyiszor alkalmazva, mint ahány tagja az input útcsaládnak van, L_{F}-nek egy olyan lefogását kapjuk, amelynek elemszáma megegyezik az I független rész-rendszer elemszámával. • •

2003. május 22. lgyori