Lokálisan Javító Algoritmusok a

Kombinatorikus Optimalizálásban

Diplomamunka

írta: Miklós Zoltán

matematikus szak

Témavezető:

Frank András, egyetemi tanár

Operációkutatási Tanszék

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

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

Tartalomjegyzék

1. Bevezetés 1

2. Gráfok 3 2.1. Egy irányítási feladat . . . . . . . . . . . . . . . . . . . . . . . . 3 2.2. Kőnig tétele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

3. Hálózatok 10 3.1. Folyamok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.2. Áramok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

4. Matroidok 19 4.1. Matroidokkal kapcsolatos eredmények . . . . . . . . . . . . . . . 19 4.2. Matroid partícionálási probléma . . . . . . . . . . . . . . . . . . 22 4.3. Matroid metszet probléma . . . . . . . . . . . . . . . . . . . . . 27 4.4. Matroid tagság probléma . . . . . . . . . . . . . . . . . . . . . . 33

5. Polimatroidok 38 5.1. Eredmények polimatroidokkal kapcsolatban . . . . . . . . . . . . 38 5.2. Polimatroid tagság probléma . . . . . . . . . . . . . . . . . . . . 40 5.3. Polimatroid metszet probléma . . . . . . . . . . . . . . . . . . . 43 5.4. Egy lokálisan javító algoritmikus séma . . . . . . . . . . . . . . 50 5.5. Szubmoduláris függvény minimalizálás . . . . . . . . . . . . . . 55

1. Bevezetés

A diplomamunka célja, hogy egységes algoritmikus keretben tárgyaljon a kombinatorikus optimalizálásban felmerült, néha látszólag egymástól távol fekvő kérdéseket.

A második fejezetben egy irányítatlan gráf éleinek keressük olyan irányítását, mely a gráf minden pontjában eleget tesz egy előre megadott tetszőleges alsó korlátozásnak, majd Kőnig páros gráfok maximális párosításaira vonatkozó híres tételét tárgyaljuk.

A harmadik fejezetben hálózatokban keresünk maximális folyamot, illetve megengedett áramot. A bemutatott lokálisan javító algoritmus Goldbergtől és Tarjantól származik a 80-as évek végéről. Ez volt az első megjelenése a szakdolgozat témáját képező keretmódszernek.

A tárgyalt problémák megoldására széles körben elterjedt az olyan algoritmusok használata, melyek valamely út mentén történő javító lépéssel operálnak. Ilyen például Ford és Fulkerson maximális folyamot kiszámító közismert eljárása, mely a futása során egy megengedett folyamot tart fenn, és akkor áll le, ha már nem tud út mentén növelni a folyam értékén. A kapott folyam maximalitását egy minimális vágás felmutatásával igazoljuk.

Goldberg és Tarjan eljárása ezzel szemben nem folyamokkal dolgozik, hanem egy úgynevezett megengedett előfolyamot tart fenn, és egy pont környezetében végez rajta változtatásokat. Hogy alkalmasint milyen változást eszközöljünk, azt az előfolyamhoz illesztett szintezés segítségével döntjük el, amit szintén fenntartunk, és változtatunk is a futás alatt. Egy ilyen alkalmasan választott szintezésből könnyen kiolvashatunk egy olyan vágást, ami telíti az előfolyamot. Az eljárás addig tart, amíg az előfolyamból folyam, a telítő vágásból pedig minimális vágás nem lesz.

A javító utas algoritmus lépésszáma O(nm^{2}), ha mindig egy legrövidebb javító út mentén javítunk, a Goldberg-Tarjan féle lokálisan javító algoritmusé pedig csak O(n^{2}m), ahol n a gráf csúcsainak, m pedig az éleinek a számát jelöli.

A negyedik fejezetben matroidokkal kapcsolatos kérdéseket válaszolunk meg lokálisan javító algoritmusok készítésével. Nevezetesen a matroid partíció, a matroid metszet és a matroid tagság problémákat oldjuk meg. A partícionálási és a metszet probléma javító utas megoldása Edmondstól származik. A matroid tagság problémára W.Cunningham adott szintén javító utas megoldást 1984-ben.

A fennmaradó fejezetekben az itt szerzett tapasztalatokat próbáljuk általánosítani polimatroidokra. Bemutatásra kerül a polimatroid tagság és a polimatroid metszet probléma. Ezen általánosítási törekvéseink folyamán jutunk el a központi jelentőségű szubmoduláris függvény minimalizáció kérdéséhez.

Ezen három probléma algoritmikusan ekvivalens egymással, megoldásukra már Cunningham is próbálkozott javító utakat felhasználó eljárás szerkesztésével, bár kísérletei még nem jártak teljes sikerrel, mégis jelentős észrevételeket tett ebben az irányban. Az algoritmikus ekvivalenciát Fujishige és Zhang mutatta meg 1994-ben, azzal, hogy a polimatroid metszetet a szubmoduláris minimalizációra redukálták.

Cunningham munkáira támaszkodva később születtek teljes megoldások is a problémánkra. Ezek közül kiemelendő Schrijver 2000-es algoritmusa, mert az ebben szereplő intervallumredukáló eljárás segítségével sikerült 2004-ben Iwata-nak és Fleischer-nek lokálisan javító algoritmust szerkeszteni a szubmoduláris függvény minimalizációra. Algoritmusuk komplexitása O(n^{7}γ + n^{8}), így a Schrijver-algoritmus javításának tekinthető, mert annak n-szer ennyi a futásideje.

Frank András egy észrevétele segítségével egyszerűbben lehetett elmondani Fujishige és Zhang polimatroidmetszet eljárását, így ezt az utat választottam.

A szubmoduláris minimalizáció tárgyalásánál Iwata, Fleischer és Schrijver munkáit dolgoztam fel. Először egy lokálisan javító algoritmikus keretet dolgozunk ki, majd ezután erre az elméletre vezetjük vissza a szubmoduláris függvények minimalizálásának problémáját.

Egyéni eredmény a diplomamunkában a matroid tagság algoritmus, amit Frank András segítségével sikerült kidolgozni, valamint az előbb említett lokálisan javító algoritmikus keret megfogalmazása.

Köszönettel tartozom Frank Andrásnak a rengeteg segítségért, Király Tamásnak, Pap Julinak, és Szabó Jácintnak az értékes észrevételeikért.

2. Gráfok

2.1. Egy irányítási feladat

Probléma Tekintsünk egy tetszőleges G = (V, E) irányítatlan gráfot, és a pontjain értelmezett f : V → ℕ_{+}, „igény”-függvényt. Mikor létezik G-nek olyan D = (V, A) irányítása, melyben minden v ∈ V pontra ϱ_{D}(v) ≥ f(v), ahol ϱ_{D}(v) a v ∈ V pontba belépő élek számát jelöli a G = (V, E) gráf D = (V, A) irányításában. ♠

Könnyen látható, hogy ehhez szükséges, hogy egy X ⊆ V részhalmazzal érintkező élek e(X) számára fennálljon az e(X) ≥ f(X) egyenlőtlenség. Valóban,

e(X) ≥ ∑_{x∈X} ϱ_{D}(x) ≥ f(X).

Az elégségesség bizonyítására lokálisan javító algoritmust szerkesztünk.

2.1. Tétel. Legyen G = (V, E) irányítatlan gráf, f : V → ℕ_{+} függvény. Ha teljesül az

e(X) ≥ f(X) ∀X ⊆ V

vágásfeltétel, akkor létezik G-nek olyan D = (V, A) irányítása, amely kielégíti az előírt

ϱ_{D}(v) ≥ f(v) ∀v ∈ V

fokszámkorlátozást.

Bizonyítás Induljunk ki a G = (V, E) alapgráf egy tetszőleges D = (V, A) irányításból, és egy hozzá „illeszkedő ” h : V → ℕ szintfüggvényből. Ezen azt értjük, hogy

• h(u) ≤ h(v) + 1 ∀(u, v) ∈ A

• h(u) = 0 ∀u : ϱ_{D}(u) > f(u).

Az első feltétel azt fejezi ki, hogy a megirányított élek mentén legfeljebb egyet csökkenhet a szintfüggvény. A második feltétel miatt a D-túltelített pontok a nulladik szintre kerülnek.

Világos, hogy a D = (V, A) irányításhoz megadható illeszkedő szintezés. Valóban, h ≡ 0 megfelelő választás. Végig fenn kívánunk tartani egy ilyen (D, h) párt. Akkor vagyunk készen, ha nincs ϱ_{D}(v) < f(v) hiányos csúcs. Egy kézenfekvő lokális műveletpár kínálkozik az általános eset kezelésére, az élfordítás és a szintemelés. Ha egy u ∈ V hiányos csúcsra illeszkedő, h(u) = h(v) + 1, azaz pontos (u, v) ∈ A él mentén végrehajtunk egy élfordítást, vagy ha ilyen él nem létezik, egyet emelünk u szintjén, akkor világos, hogy fennmaradnak az illeszkedési feltételek. Hatékony algoritmust készíthetünk ezen terv, és az alábbi megfigyelés alapján.

2.2. Lemma (megoldás). Tegyük fel, hogy létezik telítetlen pont. Ha minden telítetlen pont az n-edik szinten van, akkor létezik egy X ⊆ V halmaz, melyre e(X) < f(X).

Bizonyítás Mivel n pont van, és n + 1 szint, létezik üres szint. Rögzítsünk egyet, és definiáljuk X-et, mint ezen szint feletti pontok összességét. X-ből nem lép ki él, hiszen a szintfüggvény legalább kettőt csökkenne egy ilyen él mentén. Ezenkívül nincs túltelített pont X-ben, és legalább egy telítetlen pont van benne. Tehát, e(X) = ∑_{x∈X} ϱ_{D}(x) < ∑_{x∈X} f(x) = f(X). ♣

X tehát sérti G-re tett feltevésünket.

2.1. Algoritmus. Tegyük fel, hogy létezik az n-edik szint alatt telítetlen pont. Válasszunk egy ilyen u ∈ V pontot! Ha létezik belőle kilépő, pontos (u, v) él, akkor ennek fordítsuk u felé az irányítását! Ha nem létezik ilyen él, akkor tegyük az u pontot egyel magasabb szintre! Ha már nem létezik telítetlen pont az n-edik szint alatt, akkor álljunk meg! ♣

Algoritmusunk helyessége világos, hiszen lokális műveleteink tartják az illeszkedést. Hátramaradt a végesség bizonyítása.

2.3. Lemma (lépésszám). Algoritmusunk hatékony. Legfeljebb O(n^{2}) szintemelést, és legfeljebb O(n^{3}) élfordítást végzünk. Tehát köbös az eljárásunk lépésszáma.

Bizonyítás Minden v ∈ V pont szintje legfeljebb n, legalább 0, és ez a szint sosem csökken az eljárás során. Tehát legfeljebb n^{2} szintet emelünk meg.

Minden (u, v) él h({u, v}) := h(u) + h(v) szintje legalább kettőt nő két rajta elvégzett élfordítás között, hiszen csak pontos élek irányítását fordítjuk meg; emellett pontos él szintje ≥ 1 és ≤ 2n−1 , és sosem csökken. Így (u, v)-n legfeljebb \frac{2n}{2} -ször fordítunk, tehát összesen legfeljebb mn élfordítást hajtunk végre. ♣ ♣

Megjegyzés A bizonyítás alapján látható egy olyan algoritmus létezése, amely durván n^{3} apró lépés megtétele után, egy adott G = (V, E) irányítatlan gráf, az előre megadott f : V → ℕ befokszám alsó korlátokat kielégítő D = (V, A) irányítását, vagy ha ilyen nincs, akkor erről egy tanúsítványt szerkeszt, azaz egy az érintkezési feltételeket megsértő X ⊆ V vágást szolgáltat. ♣

2.2. Kőnig tétele

Probléma Keressünk M maximális párosítást egy G = (S, T, E) páros gráfban! Ezzel a problémával rokon feladat, és vele egyszerre megoldható, ha a páros gráf éleit lefogó minimális sok pontból álló, L ponthalmazt keresünk. Ez abból a tényből fakad, hogy nyilván |M| ≤ |L| minden M párosításra, és L lefogó rendszerre, az egyenlőségről pedig látni fogjuk, hogy elérhető. ♠

2.4. Tétel (Kőnig). Adott G = (S, T, E) páros gráfra,

max{|M| : M ⊆ E párosítás} = min{|L| : L ⊆ V lefogó rendszer}.

Bizonyítás Megmutatjuk, hogy létezik olyan (M, L) pár is , hogy |M| = |L|. Ehhez ismét könnyen inicializálható, egymáshoz illeszkedő objektumokat fogunk fenntartani, (H, d)-t, melyre, ha struktúráltan végrehajtunk két egyszerű műveletből álló sorozatot, véges, sőt a bemeneti gráf méretének polinomiális függvényével korlátozhatóan sok lépés után szükségképp egy olyan (H, d) párhoz jutunk, amelyből már egyszerűen megkonstruálhatjuk feladatunk egy megoldását.

Definíció Egy H ⊆ E élhalmazt félpárosításnak nevezünk, ha minden S-beli pontra legfeljebb egy H-beli él illeszkedik, más szóval, ha d_{H}(s) ≤ 1 minden s ∈ S pontra. ♣

Definíció Legyen H ⊆ E félpárosítás. Ha egy T -beli pontra nem illeszkedik H-beli él, akkor H-fedetlennek, ha egynél több H-beli él is illeszkedik rá, akkor H-túlfedettnek nevezzük. Legyen t_{1}, t_{2} ∈ T és s ∈ S. Tegyük fel, hogy (t_{1}, s) ∉ H, viszont (t_{2}, s) ∈ H. Ekkor a (t_{1}, s, t_{2}) hármast H-alternáló cseresznyének nevezzük. ♣

Definíció Legyen d : T → ℕ egy egész vektor. A d vektor által a T halmazon meghatározott osztályozást a T halmaz szintezésének nevezzük. A 0-adik szinten lévő pontokról szemléletesen azt is mondjuk, hogy bal oldalon vannak, míg a max(d)-szintű pontokról azt, hogy jobb oldalra vannak tolva. ♣

Definíció Legyen H ⊆ E félpárosítás. Egy d : T → ℕ szintezést H-illeszkedőnek mondunk, ha • a H által fedetlen T -beli pontok a bal oldalon vannak,

• minden (t_{1}, s, t_{2}) H-alternáló cseresznyére d(t_{2}) − d(t_{1}) ≤ 1.

Ezt a második kritériumot úgy is kifejezhetjük, hogy nincsenek a gráfban ”rossz„ H-alternáló cseresznyék. ♣

Az E által fedetlen pontok nem játszanak szerepet a tétel állítására vonatkozólag, ezért feltehetjük, hogy minden pont foka pozitív. Így biztosan létezik egy H félpárosítás, és a d ≡ 0 szintezés illeszkedik hozzá. Ezzel inicializáltuk a fenntartandó objektumokat.

Tegyük fel, hogy d ≤ n.

2.5. Lemma (megoldás). Legyen (H, d) illeszkedő pár. Ha minden túlfedett pont az n-edik szinten van, akkor már könnyen konstruálhatunk egy M párosítást és egy L lefogó pontrenszert, melyekre |M| = |L|.

Bizonyítás Mivel n + 1 szint van, és csak n pont, létezik egy üres szint. Rögzítsünk le egyet, és tekintsük e szinttől jobbra lévő pontok X ⊆ T halmazát. Legyen Y := Γ_{H}(X) ⊆ S, azaz X H-szomszédainak halmaza.

Nem létezik T \ X és Y között vezető E-beli él. Valóban, egy ilyen él vagy H-beli él volna, csakhogy egy Y -béli pont H-szomszédja X-beli pont, vagy egy (t_{1}, s) ∈ E \ H él volna, ami az egyértelmű (s, t_{2}) ∈ M éllel együtt, egy ”rossz„ H-alternáló cseresznyét adna G-ben. Tehát L := X ∪ (S \ Y) lefogó pontrendszer.

Válasszunk ki minden t ∈ X pontra egy őt fedő H-beli élt. Ez megtehető, hiszen X nem tartalmaz H-fedetlen pontot. Ezekhez az élekhez még vegyük hozzá az összes S \ Y -t fedő H-beli élt.

Az így kapott M ⊆ E élhalmaz nyilván a G gráf párosítása. Valóban, M ⊆ H így az S-beli pontokra legfeljebb egy M-beli él illeszkedik, hiszen H félpárosítás, a H-túlfedett pontok X-ben vannak, de egy X-beli pont Hszomszédja Y -beli, így erre csak egy M-beli él illeszkedik.

Konstrukciónkból világos, hogy |M| = |L|. ♣

Az általános esetben létezik egy túlfedett t pont az n-edik szinttől balra. Hiszen ha egyáltalán nincs túlfedett pont, akkor H egy S-et fedő párosítás, s így az M := H, L := S választással készen vagyunk. Ha minden túlfedett pont az n-edik szinten van , akkor pedig a lemma miatt vagyunk készen.

Csináljuk a következőt! Válasszunk egy az n-edik szinttől balra lévő t ∈ T túlfedett pontot, és toljuk egy szinttel jobbra. A bajnak, azaz ha megsértettük az illeszkedést, csak egyetlen oka lehet, nevezetesen hogy létezik egy ”pontos„ ,H-alternáló (u, s, t) cseresznye, azaz olyan, melyre d(t) = d(u) + 1 teljesül. Ilyen esetben inkább hajtsunk végre egy (u, s, t)-élcserét H-n, magyarán térjünk át a H − (t, s) + (s, u) félpárosításra.

2.6. Lemma (érvényesség). A fent definiált általános lépés megőrzi az Hilleszkedést, és H félpárosítás marad.

Bizonyítás Világos, hogy egy H-alternáló cseresznyével való cserélés félpárosítást eredményez.

Ha az (u, s, t)-n végrehajtott cserélés után (a, b, c) egy rossz H-alternáló cseresznye volna, akkor (a, b, c) = (a, s, u) lenne. De akkor (a, s, t) egy rossz H-alternáló cseresznye volna a cserélés előtt. Így rossz H-alternáló cseresznye nem keletkezhet. Mivel az u pont H-túlfedett, nem keletkezik H-fedetlen pont sem, így a H félpárosítás (u, s, t-kicserélése egy d-illeszkedő félpárosítást eredményez.

Egyrészt az u pontra nem illeszkedik pontos H-alternáló cseresznye. másrészt az u pont H-túlfedett, így a d szintezés u-jobbra tolása H-illeszkedő szintezést eredményez. ♣

Addig hajtsuk végre a fenti eljárást a kiválasztott t ponton, amíg jobb oldalra nem rendezzük az összes H-túlfedett pontot. Hogy hatékony legyen eljárásunk, mindig válasszuk t-t bal felől, azaz vegyük a min{d(t) : t túlfedett} program egy megoldását.

2.2. Algoritmus. Induljunk ki egy tetszőleges H félpárosításból, és egy hozzá illeszkedő d szintezésből. Válasszunk egy minimális szintű túlfedett t pontot az n-edik szinttől balra! Ha nincs, álljunk meg! Egyébként vegyünk egy rá illeszkedő d-pontos, H-alternáló (u, s, t) cseresznyét. Ha nincs, toljuk a t pontot egy szinttel jobbra. Egyébként cseréljük ki H-ban az (s, t) él (u, s)-re, s ezt addig ismételgessük, amíg el nem fogynak a H-túlfedett pontok, vagy minden H-túlfedett pont az n-edik szintre nem kerül. ♣

2.7. Lemma (lépésszám). Ez az algoritmus legfeljebb O(n^{3}) lépés után terminál.

Bizonyítás Mivel mindig balról választjuk t-t, legfeljebb n élcsere után, vagy csökken egyel a H-fedetlen pontok száma, vagy ha nem, a következő lépésben t-t eggyel jobbra kell tolnunk. H-fedetlen pont nem keletkezik, és legfeljebb n van belőle, így az első eset legfeljebb n-szer fordulhat elő. Nem használunk n-nél nagyobb szinteket, ezért egy pontot legfeljebb n-szer tolhatunk jobbra , n pont van, tehát a második eset legfeljebb n^{2}-szer fordulhat elő. Tehát legfeljebb (n + n^{2})n-el arányosat lépünk. ♣

Az első két lemma igazolja algoritmusunk helyességét, a harmadik a hatékonyságát, együtt pedig a tételt igazolják. ♣

Megjegyzés A fenti algoritmussal igazoltuk Hall tételét is. Hiszen vagy bepárosítottuk S-et T -be, vagy létezett egy X ⊆ T halmaz, melynek a végső H félpárosításra vett Y = Γ_{H}(X) ⊆ S szomszédossága megsérti a Hall feltételt. Valóban, |Γ_{E}(Y)| < |Y |, amint az első lemma bizonyításából könnyen látható, hiszen |Γ_{E}(Y)| ≤ |Γ_{H}(Y)| = |X| < |Y |, mert X-ben nincs H-fedetlen pont, viszont van benne H-túlfedett, és H-alternáló cseresznyén keresztül nem lehet kilépni belőle. ♣

3. Hálózatok

3.1. Folyamok

Legyen D = (V, A) irányított gráf, élein g : A → ℝ_{+} kapacitásfüggvény, és legyen kitüntetve egy (s, t) ∈ V^{2}, s ≠ t, forrásnak, illetve nyelőnek nevezett pontpár, melyre ϱ_{A}(s) = 0 és δ_{A}(t) = 0. Az így nyert, (D = (V, A), g) objektumot, hálózatnak nevezzük. Egy x : A → ℝ vektor megengedett, ha 0 ≤ x ≤ g, és (hálózati)folyam, ha minden v ∈ V − {s, t} köztes pontra teljesül a megmaradási feltétel, ϱ_{x}(v) = δ_{x}(v). Egy folyam értéke, a val(x) := δ_{x}(X) − ϱ_{x}(X) = ϱ_{x}(Y) − δ_{x}(Y) ∈ ℝ_{+} szám, ahol X, Y ⊆ V, tetszőlegesen rögzített, st̄, illetve s̄t-halmazok, azaz s ∈ X, t ∉ X, és s ∉ Y,t ∈ Y. X = s esetén val(x), az x folyam s forrásból való teljes kiáramlása, míg Y = t esetén az x folyam t nyelőbe való teljes beáramlása. Ez a definíció egyértelmű.

3.1. Állítás. val(x) értéke nem függ X, illetve Y megválasztásától.

Bizonyítás Feltehető, hogy X = V − Y, így csak az egyik, mondjuk az X változótól való függetlenséget kell bizonyítani.

δ_{x}(X) − ϱ_{x}(X) = ∑_{v∈X}(δ_{x}(v) − ϱ_{x}(v))

Tehát δ_{x} − ϱ_{x} , a pontokon értelmezett vektor, így a megmaradási szabály, illetve ϱ_{x}(s) = 0 értelmében, val(x) = δ_{x}(s). ♣

Ezek után megfogalmazhatjuk problémánkat. Mikor létezik egy hálózatban maximális értékű folyam? Hogyan találjunk meg egy ilyet?

Megjegyzés Problémánk igen erős, abban az értelemben, hogy számos, más elméletekben felmerülő kérdés és megoldása megfogalmazható a fent definiált fogalmakkal, egy hálózati folyam konstrukcíó megalkotása után. ♣

Megjegyzés Világos, hogy max{val(x) : x megengedett folyam} ≤ δ_{g}(X) minden X st̄-halmazra. A jobboldali értéket az X vágás kapacitásának nevezzük. Ha tudnánk találni egy x folyamot és egy X st̄-vágást, melyekre val(x) = δ_{g}(X) teljesül, akkor ezzel igazolnánk, hogy mindig létezik a fenti, formálisan felírt maximum, azaz van maximális folyam. Valóban, x maximális folyam lenne min{δ_{g}(X) : X st̄ vágás} értékkel, az X tanúsítvány szerint.

Ez az út járható. Egy "megengedett előfolyam"-nak nevezett, x objektumot fogunk javítgatni, míg folyam nem lesz belőle. A maximalitással nem lesz gondunk. ♣

3.2. Tétel (Ford-Fulkerson). Legyen (D = (V, A), g) hálózat.

max{val(x) : x megengedett folyam} = min{δ_{g}(X) : X ⊆ V st̄ vágás}

Bizonyítás

• max ≤ min: val(x) = δ_{x}(X) − ϱ_{x}(X) ≤ δ_{g}(X) − ϱ_{0}(X) = δ_{g}(X) ,mert 0 ≤ x ≤ g

• max ≥ min: A fenti egyenlőtlenségben akkor áll egyenlőség, ha az X-ből kilépő éleken x értéke eléri a g kapacitást, a belépőkön pedig 0 értéket vesz fel. Ezt úgy fejezzük ki, hogy x telíti az X vágást. Adjunk példát ilyen párra!

Definíció Legyen 0 ≤ x ≤ g megengedett vektor, (u, v) ∈ V^{2}. Azt mondjuk, hogy (u, v) az x-hez tartozó segédgráf éle, azaz (u, v) ∈ A_{x}, ha (u, v) ∈ A, és x(u, v) < g(u, v), vagy ha (v, u) ∈ A és x(v, u) > 0. Ha (u, v) ∉ A_{x}, azaz x(u, v) = g(u, v) és x(v, u) = 0, akkor azt mondjuk, hogy x telíti az (u, v) párt. Tehát mondhatjuk, hogy x akkor telít egy X vágást, ha minden X-ből kilépő párt telít. ♣

Definíció Legyen h : V → ℕ szintfüggvény. Tegyük fel, hogy h normált, azaz h(s) = n, és h(t) = 0. Azt mondjuk, hogy a h normált szintfüggvény illeszkedik az x megengedett vektorhoz, ha a segédgráf élei mentén legfeljebb egyet csökken, azaz h(u) − h(v) ≤ 1, minden (u, v) ∈ A_{x} élre. ♣

3.3. Lemma. Tegyük fel, hogy x megengedett, h normált, és illeszkednek. Ekkor létezik egy X ⊆ V st̄-vágás, hogy x telíti X-et.

Bizonyítás Nyilván van egy üres k szint, melyre 0 < k < n. A k-nál nem kisebb szintű pontok X halmaza jó lesz. Egyrészt s ∈ X és t ∉ X. Másrészt nincs olyan (u, v) pár, mely kilépne X-ből, és a segédgráfnak éle volna. Tehát x telíti X-et. ♣

Hogy egy x vektor mennyire nem folyam, azt a λ_{x}(v) := ϱ_{x}(v) − δ_{x}(v) pontokon értelmezett függvénnyel mérhetjük. Ha λ_{x} ≥ 0, akkor x-et előfolyamnak hívjuk.

3.4. Lemma. Egy x előfolyam pontosan akkor folyam, ha λ_{x}(v) = 0 minden v ≠ s, t pontra. ♣

3.5. Lemma. Létezik olyan (x, h) pár, hogy x megengedett előfolyam, h normált szintezés, és h illeszkedik x-hez.

Bizonyítás Legyen h(s) = n, másutt h = 0. Így h normált szintezés. Legyen x olyan megengedett előfolyamfolyam, hogy minden (s, v) ∈ A élre: x(s, v) = g(s, v). Ekkor h illeszkedik x-hez. Ilyen x létezik. Legyen x = 0 azokon az éleken, ahol nincs előírva az értéke. Ekkor x megengedett, és minden s-től különböző pontnak nemnegatív a többlete. ♣

Tehát tudjuk az (x, h) párt inicializálni, hogy a kezdeti feltételek fennálljanak. Tudjuk a terminálási kritériumot, miszerint nincs nem kitüntetett többletes pont. Ekkor x már folyam, és h igazolja a maximalitását. Viszont az nem világos, hogy hogyan definiáljuk az általános lépést , hogy a kezdeti feltételek fennmaradjanak, és véges sok lépés után teljesüljön a terminálási kritérium. Azért nézünk előfolyamokat, mert van egy kellemes tulajdonságuk.

3.6. Lemma. Legyen x előfolyam. Minden λ_{x}(v) > 0 többletes pontból vezet az A_{x} segédgráf éleiből álló P irányított út az s forráspontba. Legyen h egy x-hez illeszkedő normált szintezés. Ekkor a többletes pontokon h(v) = O(n).

Bizonyítás Legyen S ⊆ V azon v ∈ V pontok halmaza, melyek s-ből az éleken visszafelé haladva elérhetők A_{x}-ben. Nyilván pontosan ezen v-kből létezik s-be vezető P irányított út A_{x}-ben.

v ∈ S (v többletes) ⟺ ∑_{v∉S} λ_{x}(v) = 0

Node, 0 ≤ ∑_{v∉S} λ_{x}(v) = δ_{x}(S) − ϱ_{x}(S) = δ_{0}(S) − ϱ_{g}(S) ≤ 0, hiszen S-be nem lép él A_{x}-ben.

Adjuk össze az h(a)−h(b) szinteséseket az (a, b) ∈ P párokra. Mivel P -ben legfeljebb n−1 él lehet, és A_{x} élei legfeljebb 1 szintet lépnek lefelé, azt kapjuk, hogy h(v) − h(s) ≤ n − 1. Tehát h(v) = 2n − 1 = O(n). (A konstans 2-nek választható!) ♣

Megjegyzés Az a tervünk, hogy veszünk egy előfolyamot, illesztünk hozzá egy szintezést, majd egy u többletes pontot eggyel magasabbra emelünk. Többletes pontot aktívnak is nevezünk, mert mindig ilyenekkel fogunk dolgozni. Akkor van baj, ha megsértjük az illeszkedést. Ennek az az oka, hogy létezik egy (u, v) él A_{x}-ben, melyre h(u) = h(v) + 1. Ezt az élt telítjük, azaz (u, v)-n x-et g-re állítjuk, (v, u)-n pedig 0-ra. Ha nem okozunk ezzel újra valamilyen bajt, akkor (u, v) ∉ A_{x} lesz a szaturálás után. Bajt pontosan akkor okoztunk, ha az operációnk után λ_{x}(u) negatív lett, vagyis x már nem előfolyam. Ilyenkor el tudjuk tüntetni a λ_{x}(u) többletet, azaz csak annyira emeljük x-et (u, v)- n, illetve csökkentjük (v, u)-n, hogy λ_{x}(u) = 0 legyen. Ekkor persze v még inkább többletes lesz, λ_{x}(v) + λ_{x}(u) többlettel, de úgy tekinthetjük, hogy a λ_{x}(u) többletet eggyel alacsonyabb szintre nyomtuk. Globálisan szemlélve, a többletet lefelé, mintegy t-be nyomjuk, ha ez nem megy, felemeljük, hogy sbe visszajuttathassuk majd. Mivel a többlet O(n) szintet emelkedhet csak, plauzibilis, hogy eljárásunk véget ér majd.

3.1. Lokális művelet. Legyen λ_{x}(u) > 0 (u ≠ s, t), többletes pont.

• Nincs (u, v) ∈ A_{x} ↦ Emeljük meg u szintjét! h(u) := h(u) + 1 !

• Van (u, v) ∈ A_{x} ↦ Számoljuk ki ε-t!

ε = min{λ_{x}(u), Δ_{x}(u, v)}, ahol Δ_{x}(u, v) = g(u, v) − x(u, v) + x(v, u)!

• ε = Δ_{x}(u, v) ↦ Telítsük az (u, v) párt! x(u, v) := g(u, v), x(v, u) := 0 !

• ε = λ_{x}(u) ↦ Inaktivizáljuk az u pontot! λ_{x}(u) − δ_{1} − δ_{2} = 0 , x(u, v) := x(u, v) + δ_{1} ≤ g(u, v) ; x(v, u) := x(v, u) − δ_{2} ≥ 0 ; δ_{1}, δ_{2} ≥ 0! ♣

3.1. Algoritmus (előfolyam).

• input: (D, g) hálózat. {s, t} kitüntetett pontok.

• output: x maximális folyam, h normált, x-hez illeszkedő szintezés.

• inicializálás: Legyen h(s) = n, h(v) = 0 egyébként! Legyen x(u, v) = g(u, v), ha u = s, x(u, v) = 0 egyébként!

• általános lépés: Vegyünk egy λ_{x}(u) > 0 többletes pontot, u ≠ s, t! Hajtsuk végre rajta a lokális műveletet! Ezt iteráljuk!

• terminálás: Nincs többletes pont. ♣

3.7. Tétel (komplexitás). Az előfolyam algoritmus lépésszáma O(mn^{2}). Szintemelést O(n^{2}), telítést O(mn^{2}), inaktivizálást O(mn^{2}) lépésben hajtunk végre.

Bizonyítás 0 ≤ h(u) ≤ 2n − 1, mert csak aktív pont szintjét emeljük. h(u) egyik lépésben sem csökken. Tehát legfeljebb (n − 2)(2n − 1) szintemelést hajtunk végre.

Az (u, v) ∈ A_{x} élen való telítés hatására (u, v) ∉ A_{x}. Ahhoz, hogy ez megváltozzon, a (v, u) élen kell telítni, vagy inaktivizálni. Ehhez viszont h(v) = h(u) + 1 kell. Mivel az (u, v) telítésekor h(u) = h(v) + 1, ehhez az kell, hogy h(v) szintjet legalább 2-vel megemeljük. Ha k-szor telítünk (u, v)-n, akkor tehát 0 ≤ 2(k − 1) + 1 ≤ 2n − 1.(Az utolsó, már lehet, hogy nem vezet h(v) emelésére). Így k ≤ n. Legfeljebb 2 ∗ m darab (u, v) ∈ A_{x} él van, hiszen (u, v) ∉ A esetén g(u, v) = 0, (u, v) ∉ A-ra pedig (u, v) és (v, u) is segédél lehet, bár ezek nem feltétlenül páronként különbözőek. Összevetve, legfeljebb 2 ∗ m ∗ n telítést kell elvégeznünk.

Tegyük fel, hogy már 0 ≤ k < ∞ lépést megtettünk. Legyen A az aktív pontok halmaza. h_{k}(A) ≥ 0 és kezdetben h_{0}(A) = 0. h_{k}(A) = h_{0}(A) + Δ_{+} − Δ_{−}, ahol H := h(A)-t növelő, illetve csökkentő lépések számát jelöljük Δ-val. Tehát Δ_{−} ≤ Δ_{+}. Minden inaktivizálás legalább 1-gyel csökkenti H-t, hiszen pontos él mentén történik, és a magasabb szinten lévő pont kikerül A-ból. Minden szintemelés , és minden telítés nem-csökkenti H-t. Szintemelés 1-gyel növel, telítés esetén pedig A vagy bővül 1 ponttal, és akkor legfeljebb 2n − 1-et emelH értékén, vagy nem változik. Tehát s_{k} ≤ Δ_{−}, és Δ_{+} ≤ r_{k} +a_{k}(2n−1), ahol s a telítések, r és a pedig a szintemelések, illetve az inaktivizálások száma. Ez utóbbi kettőt pedig már megbecsültük. Összevetve, s_{k} ≤ Δ_{−} ≤ Δ_{+} ≤ (n − 2)(2n − 1) + 2mn(2n − 1). ♣

3.2. Áramok

Probléma Legyen D = (V, A) digráf. f, g : A → ℝ kapacitások. Egy x : A → ℝ vektor megengedett, ha minden e ∈ A élre fennáll, hogy f(e) ≤ g(e). Feltehetjük, hogy f ≤ g, különben nem létezik megengedett vektor. Ha minden v ∈ V pontra fennáll a megmaradási feltétel, ϱ_{x}(v) = δ_{x}(v), akkor x-et áramnak nevezzük. Mikor létezik egy (D, f, g) típusú hálózatban megengedett áram? Ha létezik, hogyan találhatunk áramot? Ha nem létezik áram, létezik-e erre könnyen ellenőrizhető bizonyíték, és ha létezik bizonyíték, hogyan találjuk meg? ♠

3.8. Tétel. Ha létezik x megengedett áram, akkor

ϱ_{g}(X) − δ_{f}(X) ≥ 0 (X ⊆ V).

Bizonyítás

ϱ_{x}(X) − δ_{x}(X) = \{ \begin{matrix}≤ ϱ_{g}(X) − δ_{f}(X), \\ ≥ 0. \end{matrix} ♣

3.9. Tétel (Hoffman). Vagy létezik egy x ∈ ℝ^{A} megengedett áram, vagy létezik egy X ⊆ V halmaz, melyre ϱ_{g}(X) < δ_{f}(X).

Bizonyítás

• Az előző tétel miatt a két feltétel kizárja egymást.

• Lokálisan javító algoritmust használva látjuk be, hogy e két egzisztenciafeltétel közül az egyik mindig fennáll.

Először fogalmazzuk meg a kezdeti feltételünket és a megállási kritériumot! Definíció Legyen x ∈ ℝ^{A} megengedett vektor, és h ∈ ℕ^{V} egy szintezés. Ha minden v ∈ V pontra h(v) ≤ n, és ϱ_{x}(v) > δ_{x}(v) esetén h(v) = 0, tehát ha az x-többletes pontok a nulla szinten vannak, akkor azt mondjuk, hogy a h szintezés x-normált. ♣

Definíció Legyen x ∈ ℝ^{A} megengedett vektor. Egy (u, v) ∈ A élre \overrightarrow{e} = (u, v) növelhető x-segédél, ha x(e) < g(e), ha pedig x(e) > f(e), akkor \overleftarrow{e} = (v, u) csökkenthető x-segédél. Az x-segédélek gráfját A_{x}-el jelöljük. ♣

Definíció Egy (x, h) pár illeszkedik, ha x megengedett vektor, h normált szintezés, és teljesül az illeszkedési feltétel, azaz minden (u, v) ∈ A_{x} segédélre h(u) ≤ h(v) + 1. ♣ 3.10. Lemma (kezdeti feltétel). Létezik (x, h) illeszkedő pár.

Bizonyítás Legyen h ≡ 0. Ez a normált szintezés bármely x megengedett vektorhoz illeszkedik. Létezik ilyen, például x ≡ f. ♣

3.11. Lemma (terminálás). Pontosan akkor nincs ϱ_{x}(v) > δ_{x}(v) többletes pont, ha nincs ϱ_{x}(v) < δ_{x}(v) hiányos pont, és ekkor x megengedett áram. Tegyük fel, hogy h illeszkedik x-hez. Ha van v többletes pont, és minden v többletes pontra h(v) = n, akkor könnyen meghatározhatunk egy olyan X ⊆ V halmazt, melyre teljesül a másik feltétel, azaz ϱ_{g}(X) < δ_{f}(X).

Bizonyítás ∑_{v∈V} (ϱ_{x}(v) − δ_{x}(v)) = 0, így az első rész világos. Létezik k üres szint, melyre 0 < k < n. Legyen X egy ilyen k szint feletti pontok összessége. X jó lesz. Valóban, h illeszkedése miatt nem lép ki X-ből segédél, így minden X-ből kilépő (u, v) pár szaturált x által, azaz x(u, v) = g(u, v), illetve x(v, u) = f(v, u). X-ben létezik többletes pont, viszont nem létezik benne hiányos, hiszen h normált, és feltettük, hogy van hiányos pont az n. szinten. Összevetve:

ϱ_{g}(X) − δ_{f}(X) = ϱ_{x}(X) − δ_{x}(X) = ∑_{v∈X} ϱ_{x}(v) − δ_{x}(v) < 0

Tehát X valóban megsérti a feltételt. ♣

Az általános eset kezelése maradt hátra. λ_{x} := ϱ_{x} − δ_{x}.

3.2. Lokális művelet. Legyen λ_{x}(u) < 0 , hiányos pont, h(u) < n.

• Nincs (u, v) ∈ A_{x} ↦ Emeljünk! h(u) := h(u) + 1 !

• Van (u, v) ∈ A_{x} ↦ Számoljuk ki! ε = min{λ_{x}(u), Δ_{x}(u, v)}, ahol Δ_{x}(u, v) = g(u, v) − x(u, v) + x(v, u) − f(v, u)!

• ε = Δ_{x}(u, v) ↦ Szaturáljunk! x(u, v) := g(u, v), x(v, u) := f(v, u) !

• ε = λ_{x}(u) ↦ Inaktivizáljunk! λ_{x}(u) − δ_{1} − δ_{2} = 0 , x(u, v) := x(u, v) + δ_{1} ≤ g(u, v) ; x(v, u) := x(v, u) − δ_{2} ≥ f(v, u) ; δ_{1}, δ_{2} ≥ 0! ♣ 3.2. Algoritmus (áram).

• input: (D, g, f) hálózat.

• output: x megengedett áram, vagy (x, h) illeszkedő pár, hogy minden v, hiányos pontra, h(v) = n.

• inicializálás: Legyen h ≡ 0, x ≡ f!

• általános lépés: Vegyünk egy λ_{x}(u) < 0 hiányos pontot, melyre h(u) < n! Hajtsuk végre rajta a lokális műveletet! Ezt iteráljuk!

• terminálás: Nincs hiányos pont, vagy minden hiányos pont az n-edik szinten van. ♣

Megjegyzés Ez az algoritmus analóg a folyamproblémára megismert előfolyam algoritmussal. Meggyőződhetünk róla, hogy ez az analógia átmegy a komplexitásának az elemzésére is. Most cseppet módosítunk rajta, hogy könnyebben elintézhessük a lépésszám megbecslését. ♣

3.1. Szabály (maximális választás).

• Az általános lépésben a max{h(u) : λ_{x}(u) < 0 ; h(u) < n} program u megoldásával dolgozzunk! ♣

3.12. Tétel (komplexitás). Az áramalgoritmus lépésszáma maximális választás esetén O(n^{3}). Szintemelést O(n^{2}), szaturálást O(mn), inaktivizálást O(n^{3}) lépésben végzünk.

Bizonyítás Az n-edik szint alatti, hiányos pontokat nevezzük aktívnak! 0 ≤ h(u) ≤ n, mert csak az n-edik szint alatti aktív pontok szintjét emeljük. h(u) egyik lépésben sem csökken. Tehát legfeljebb n^{2} szintemelést hajtunk végre.

Az (u, v) ∈ A_{x} élen való szaturálás hatására (u, v) ∉ A_{x}. Ahhoz, hogy ez megváltozzon, a (v, u) élen kell szaturálni vagy inaktivizálni. Ehhez viszont h(v) = h(u) + 1 kell. Mivel az (u, v) szaturálásakor h(u) = h(v) + 1, ehhez az kell, hogy h(v) szintjét legalább 2-vel megemeljük. Ha k-szor szaturáltunk (u, v)-n, akkor tehát 2(k − 1) ≤ n.(Az utolsó, már lehet, hogy nem vezet h(v) emelésére). Így k ≤ \frac{n}{2} +1. Legfeljebb 2m darab (u, v) ∈ A_{x} él van. Összevetve, legfeljebb O(mn) szaturálást kell elvégeznünk.

Eddig nem használtuk a választási szabályt! Vizsgáljuk meg, hányszor inaktivizálunk, mialatt h változatlan! Egy inaktivizálás hatására vagy h-t, az aktívakon maximalizáló, u pontok száma csökken, vagy csökken a h(u) maximum érték. Tehát legrosszabb esetben végiginaktivizáljuk a h által, a V -n létesített összes szinthalmazt, azaz V pontjait. Tehát fix h-ra legfeljebb n-szer inaktivizálunk. Legfeljebb O(n^{2}) h-t használunk, így legfeljebb O(n^{3}) inaktivizálást végzünk el. ♣

4. Matroidok

4.1. Matroidokkal kapcsolatos eredmények

Legyen S egy n elemű alaphalmaz. Egy M matroidot S-en több ekvivalens módon is megadhatunk. Például az r_{M} rangfüggvényével, az F_{M} független halmazainak rendszerével, a bázisainak B_{M} összességével, vagy megadhatjuk például köreinek C_{M} halmazrendszerével is.

Algoritmikus megközelítéssel ezen azt értjük, hogy adott egy orákulum, aminek egy tetszőleges M matroidot és egy X ⊆ S részhalmazt beadva, visszatér annak r(X) rangjával, vagy visszatér egy kérdésre adott helyes válasszal, miszerint X független, bázis, kör vagy sem, attól függően, hogy melyik kérdésre voltunk kíváncsiak.

Elméleti síkon persze axiómákban rögzítjük r, F, B, és C ”matroidszervező tulajdonságait„ , kimutatjuk róluk, hogy ekvivalensek, és ha tekintünk például egy konkrét ”ilyen„ r objektumot, akkor azt mondjuk, hogy megadtunk egy (S, r) matroidot. Ezt azért tehetjük meg, mert r egy másik elméleten belül, konkrétan az S → ℕ függvények között értelmes. Ezzel az eljárással valójában a matroidelméletet vezettük vissza erre az ”egyszerűbb„ , mondjuk egy orákulum segítségével kezelt elméletre.

Egy r : S → ℕ függvény pontosan akkor egy M matroid rangfüggvénye, ha normalizált, monoton növő, szubmoduláris és szubkardinális, tehát ha r(∅) = 0; r(X) ≤ r(Y) ha X ⊆ Y; r(X) + r(Y) ≥ r(X ∪ Y) + r(X ∩ Y); illetve r(X) ≤ |X|.

Egy F ⊆ 2^{S} halmazrendszer pontosan akkor alkotja egy M matroid függetlenjeinek halmazát, ha ∅ ∈ F, leszálló, és ha akármelyik X ⊆ S halmaz tartalmazásra maximális F-beli F ⊆ X részhalmazának az elemszáma csak az X halmaztól függ. Ez a szám adja vissza természetesen az X halmaz r(X) rangját. Az r(F) = |F | egyenlet megoldásai pedig a függetleneket.

Egy F ∈ F független halmaz feszíti az X ⊆ S halmazt, ha |F ∩X| = r(X). Ennek csak az az oka, hogy X minden F -en kívüli x pontjának egyértelműen létezik egy teljes egészében X-ben fekvő C(F, x) ∈ C-el jelölt alapköre, azaz egy olyan C ∈ C kör, melyre C − x ⊆ F. A C körhalmaz matroidszervező tulajdonsága, hogy nem tartalmazza az üres halmazt; körnek nincs olyan része, mely szintén kör; és teljesül egy köraxióma; ez lehet például az, hogy két kör metszetében lévő pontot mindig el tudunk kerülni egy a két kör egyesítésében haladó harmadik kör segítségével.

A bázisokat például azon tulajdonságuk tünteti ki a függetlenek közül, hogy egy bázison kívül fekvő pontnak mindig létezik a bázisra vonatkozó alapköre, más szóval maximális a függetlenné bővítésre nézve. A B bázishalmaz matroidszervező tulajdonsága, hogy nemüres és igaz az egyik báziscserélési axióma. Például a kicserélési, miszerint egy bázisbeli elemet kicserélhetünk egy bázison kívüli elemre a bázis tulajdonság fenntartásával, ha ezt a külső elemet alkalmasan megválasztjuk egy másik bázisból, mely elkerüli ezt az elemet. Egy választás attól lesz alkalmas, hogy a kiválasztott pont alapköre átmegy ezen az elemen.

Ha egy elemet becserélni próbálunk egy bázisba, akkor jutunk el a becserélési axiómához. Eszerint egy bázison kívüli elemet becserélhetünk egy alkalmasan választott bázison belüli elemre, ha egy másik bázisnak eleme, mely elkerüli a kiválasztott pontot. Egy választás attól lesz alkalmas, hogy az elem alapkörének egy másik pontját választjuk ki.

Könnyen generálhatunk bázisokat egy rangorákulum birtokában. A generáló eljárást mohó algoritmusnak nevezzük. Az S alaphalmaz egy tetszőleges < sorbarendezéséből indul ki. Fenntart egy F ⊆ S halmazt, mely kezdetben üres, majd a sorrend szerint végigszalad S pontjain, és minden lépésben megpróbálja kibővíteni F -et a függetlenség megtartásával. Egy bővítés attól sikeres, hogy hatására megugrik eggyel a bővítendő F független halmaz rangja. Az eljárás végére F = F_{<} ∈ B, azaz a fenntartott független F, az algoritmus által bizonyítottan nem bővíthető már tovább.

Egy matroidot többféleképpen is ábrázolhatunk az n-dimenziós térben. Például definiálhatjuk a P (r) matroid poliédert vagy a B(r) bázispoliédert.

P (r) := {y ∈ ℝ^{S} : y ≥ 0, y(X) ≤ r(X)},
B(r) := {y ∈ ℝ^{S} : y ∈ P (r), y(S) = r(S)}.

P (r), illetve B(r) elemeit független, illetve bázis vektoroknak nevezzük. Mégha ezen utóbbi helytelen asszociációkra is adhat okot. A 0 − 1-értékű függetlenek megfelelnek a független halmazoknak. Valóban, hiszen egy pont, illetve egy halmaz a karakterisztikus függvényével ábrázolható ℝ^{S}-ben. Jelölésben nem fogunk különbséget tenni ezek között, tehát egy s ∈ S pont és egy X ⊆ S halmaz karakterisztikus függvényét is s-el, illetve X-el jelöljük majd. Ugyanígy nem teszünk különbséget egy {s} ⊆ S szingleton és egy s ∈ S pont között sem. Ezek az azonosítások egyrészt megtehetők, hiszen az azonosított objektumok kölcsönösen egyértelműen meghatározzák egymást, másrészt nem okozhatnak gondot, hiszen a szövegösszefüggésből általában kiderül melyik szóhasználatról van szó, harmadrészt, ha megszokjuk őket, egyszerűsíthetik az érdemi eligazodást. Mindezek ellenére tanulságos lehet, ha nyomon követjük, hogy például egy X ⊆ S halmazt mikor használunk n-dimenziós pontként, irányként, egy mátrix soraként, vagy éppenséggel úgy, mint ahogy egy lineáris célfüggvényt szokás.

4.2. Matroid partícionálási probléma

Probléma Legyen M = {M_{i} = (S, r_{i})}_{i=1}^{k}, k darab matroid, a közös S alaphalmazon. Egy olyan F ⊆ S halmazt, mely lefedhető k darab, az egyes matroidokban független, H = {F_{i} ∈ F_{i}}_{i=1}^{k} halmaz uniójával, partícionálhatónak mondunk! Keressünk egy maximális elemszámú F ⊆ S, partícionálható halmazt. Más szóval oldjuk meg a

max{|F | : F ⊆ S, és ∃ F_{i} ∈ F_{i}, melyre ⋃_{i=1}^{k} F_{i} = F }

programot! ♠

Felső korlát Legyen X ⊆ S tetszőleges halmaz. Ekkor

|S − X| + ∑_{i=1}^{k} r_{i}(X) ≥ |F |.

u.i.: |F | = |F − X| + |F ⋂ X| |F − X| ≤ |S − X| |F ⋂ X| = | ⋃_{i=1}^{k} F_{i} ⋂ X| ≤ ∑_{i=1}^{k} |F_{i} ⋂ X| |F_{i} ⋂ X| ≤ r_{i}(X) ♣

Könnyen látszik, hogy mikor áll egyenlőség becsléseinkben.

Optimalitási feltétel F = ⋃_{i=1}^{k} F_{i} optimális, ha:

• {F_{i}}_{i=1}^{k} részpartíció X-ben

• {F_{i}}_{i=1}^{k} fedi S − X-et

• F_{i} feszíti X-et az M_{i} matroidban minden 1 ≤ i ≤ k-re ♣

Megmutatjuk, hogy az optimalitási feltételeket mindig ki lehet elégíteni. Nyilván elég lesz bázisokra szorítkoznunk.

4.1. Tétel (Edmonds-Fulkerson). Legyen {M_{i} = (S, r_{i})}_{i=1}^{k}, k darab matroid S-en. Ekkor

max_{F_{i}∈F_{i}}{ | ⋃_{i=1}^{k} F_{i}| } = min_{X⊆S}{ |S − X| + ∑_{i=1}^{k} r_{i}(X) }.

Bizonyítás Lokálisan javító algoritmust szerkesztünk. Fenntartunk majd minden matroidból egy H = {B_{i} ∈ B_{i} ⊆ F_{i}}_{i=1}^{k} bázist, és S pontjainak egy olyan h : S → ℕ szintezését, melyre teljesülnek bizonyos illesztési feltételek.

Definíció H rétegszámvektorát jelöljük f_{H}-val. Tehát f_{H}(s) = l, ha pontosan l darab H-beli bázisban van benne az s ∈ S pont. Egy s ∈ S pont fedetlen, illetve többszörösen fedett, ha f_{H}(s) = 0, illetve f_{H}(s) > 1 teljesül. ♣

Definíció Legyen 1 ≤ i ≤ k egy fix index. Legyen továbbá u ∉ B_{i}. Minden v ∈ B_{i} pontra, ha v ∈ C(u, B_{i}), irányítsunk egy e élt v-ből u-ba. Az így kapott élek A_{i} összességét, a B_{i} bázishoz tartozó, kifelé irányított bázisgráfnak nevezzük, és D_{i} = (S, A_{i})-vel jelöljük. A D_{H} = (S, A_{H}) := (S, ⋃_{i=1}^{k} A_{i}) digráfot, a H-hoz tartozó segédgráfnak nevezzük. Világos, hogy egy (u, v) ∈ S^{2} pár pontosan akkor éle a segédgráfnak, ha u a kitüntetett pontja valamelyik C_{i} alapkörnek, v pedig egy másik pontja neki. Még másképp, B_{i} + u − v ∈ B_{i} teljesül valamelyik 1 ≤ i ≤ k indexre. ♣

Definíció Legyen h : S → ℕ_{+} szintezés. Ha minden fedetlen pont a legalsó szinten van, és minden segédél legfeljebb egy szintet lép lefelé, akkor Hnormált, illetve H-illeszkedő szintezésről beszélünk. Más szóval az

• f_{H}(u) = 0 ⟹ h(u) = 0

• (u, v) ∈ A_{H} ⟹ h(u) ≤ h(v) + 1.

illesztési feltételeket követeljük meg. ♣

4.2. Lemma (Terminálás). Legyen H = {B_{i} ∈ B_{i} ⊆ F_{i}}_{i=1}^{k}. Legyen továbbá h : S → ℕ_{+} H-hoz illesztett szintezés. Tegyük fel, hogy minden többszörösen fedett pont az n-szinten van. Ekkor készen vagyunk, azaz létezik, sőt egyszerűen számítható egy olyan X ⊆ S halmaz, amely kielégíti az ⋃_{i=1}^{k} B_{i}-re vonatkozó optimalitási feltételeket.

Bizonyítás Létezik k üres szint, melyre 0 < k ≤ n. Legyen X a k-nál kisebb szintű pontok halmaza. X-ben nincs többszörösen fedett pont, S − X-ben nincs fedetlen pont, és nincs S − X-ből X-be lépő segédél. Ez azt jelenti, hogy H részpartíció X-ben, és lefedi S −X-et, valamint minden 1 ≤ i ≤ k indexre és minden u ∈ X\B_{i} pontra C(B_{i}, u) ⊆ X, azaz C(B_{i}, u) ⊆ B_{i} ⋂ X + u, tehát B_{i} feszíti X-et mindegyik matroidban, vagyis r(B_{i} ⋂ X) = |B_{i} ⋂ X|. Ezt kellett bizonyítani. ♣

4.3. Lemma (Inicializálás). Létezik, és egyszerűen számítható egy (H, h) illeszkedő pár.

Bizonyítás Valóban. h ≡ 0 minden H = {B_{i} ∈ B_{i}}_{i=1}^{k} -hoz illeszkedik. Az M_{i} matroidban futtatott mohó algoritmus pedig egy B_{i} bázissal tér vissza. ♣

Térjünk át az általános esetre! Úgy akarunk értelmezni egy lokális műveletet, hogy fenntartsa az illeszkedést, és alkalmasan iterálva, véges sok lépés után teljesüljön a terminálási lemma feltétele is.

4.1. Lokális művelet (partíciós). Legyen f_{H}(u) > 1 többszörösen fedett pont, h(u) < n.

• Nincs (u, v) ∈ A_{H} , h(u) = h(v) + 1 ↦ Emeljünk u szintjén! h(u) := h(u) + 1 !

• Van (u, v) ∈ A_{H}, h(u) = h(v) + 1 ↦ (u, v)-kicserélés! Legyen i olyan, hogy (u, v) ∈ A_{i}. B_{i} := B_{i} − u + v. ♣

4.4. Lemma (kicserélés). Legyen M egy matroid S-en, és B ∈ B(M) egy bázis. Legyen továbbá h : S → ℕ a kifelé irányított D = (S, A_{B}) bázisgráfhoz illesztett szintezés. Tegyük fel, hogy u ∈ C(B, v), és h(u) = h(v) + 1.

Ekkor a h szintezés illeszkedik a B − u + v ∈ B(M) bázishoz is, más szóval a kicserélés h-illeszkedéstartó, ha a kifelé irányított bázisgráf egy pontos éle mentén hajtjuk végre.

Bizonyítás Vezessük be a B_{1} = B és B_{2} = B_{1} − u + v jelöléseket! Legyen (x, y) ∈ A_{2}\A_{1} egy új segédél! Tehát x ∈ C(B_{2}, y), és x ∉ C(B_{1}, y), vagy a C(B_{1}, y) kör nem is létezik.

Tegyük fel először, hogy ez a helyzet, tehát y ∈ B_{1}, azaz y = u. Ekkor x ∈ C(B_{2}, y) = C(B_{2}, u) = C(B_{1}, v), így

h(x) ≤ h(v) + 1 = h(u) = h(y) < h(y) + 1.

Másodjára vizsgáljuk azt az esetet, amikor y ≠ u, vagyis y ∉ B_{1}. Ekkor létezik C(B_{1}, y). Belátjuk, hogy \underline{u ∈ C(B_{1}, y)}. Ez azért igaz, mert x ∈ C(B_{2}, y)\C(B_{1}, y), tehát az 1 → 2 átmenet mentén y alapköre megváltozik, és ez csak úgy lehet, ha eredetileg tartalmazta a kicserélt u pontot.

Tehát u ∈ C(B_{1}, y) ⋂ C(B_{1}, v), és y ∉ C(B_{1}, v), mert y ∉ B_{1}, és y = v sem lehet, hiszen y ∉ B_{2}, viszont v ∈ B_{2}. Az első köraxióma miatt létezik egy y ∈ C ⊆ C(B_{1}, y) ⋃ C(B_{1}, v) − u kör. Világos, hogy y ∈ C ⊆ B_{2} + y, ezért C = C(B_{2}, y). Tehát, mivel x ∈ C(B_{2}, y)\C(B_{1}, y), \underline{x ∈ C(B_{1}, v)}.

Ezért h(x) ≤ h(v) + 1 = h(u) ≤ h(y) + 1. Tehát az (x, y) új él mindkét esetben legfeljebb egy szintet léphet lefelé. Ezt kellett bizonyítanunk. ♣

4.5. Lemma (érvényesség). Partíciós műveletünk fenntartja a kezdeti feltételeket.

Bizonyítás Már megállapítottuk, hogy B_{i} − u + v ∈ B_{i}, mert csak segédél mentén végezzük a cserét. Tehát H végig bázisokból áll.

A H-normalitást vagy úgy ronthatjuk el, hogy a 0-szint felett keletkezik egy fedetlen pont, vagy úgy, hogy megemeljük egy fedetlen pont szintjét. Mivel csak többszörösen fedett pontot cserélünk ki, és csak többszörösen fedett pont szintjét emeljük meg, nem tudjuk elrontani a h szintezés H-normalitását.

A H-illeszkedést csak úgy ronthatjuk el, ha megemeljük egy pontos segédél talpának a szintjét, vagy ha valamelyik bázison végrehajtott kicseréléssel behozunk a segédgráfba egy olyan élt, mely a csere előtt még nem segédél, viszont megsértené az illeszkedést, ha az volna.

Az első eset kizárt, hiszen csak olyan pont szintjét emeljük, melyre nem illeszkedik pontos él.

A második eset is kizárt. Ehhez tegyük fel, hogy a B_{i} bázison az (u, v)- kicserélést hajtottuk végre, tehát B′_{i} = B_{i} − u + v, és az (s, t) ∈ A′_{i}\A_{i} egy új segédél. A kicserélési lemmánk szerint ekkor h(s) ≤ h(t) + 1, tehát A′_{i} is h-illeszkedő. Ez azt jelenti, hogy h illeszkedik H′-höz. ♣

4.1. Algoritmus (matroid partíció).

• input: {M_{i} = (S, r_{i})}_{i=1}^{k} .

• output: (H = {B_{i} ∈ B_{i}}_{i=1}^{k}, h : S → ℕ) illeszkedő pár, hogy minden v ∈ S többszörösen fedett pontra, h(v) = n.

• inicializálás: Legyen h ≡ 0, H = {B_{i} ∈ B_{i}}_{i=1}^{k}, ahol B_{i}=mohó(M_{i})!

• általános lépés: Vegyünk egy f_{H}(u) > 1 többszörösen fedett pontot, melyre h(u) < n ! Hajtsuk végre rajta a lokális műveletet! Ezt iteráljuk!

• terminálás: Nincs többszörösen fedett pont, vagy minden többszörösen fedett pont az n. szinten van. ♣

4.1. Szabály (minimális választás). Az általános lépésben a min{h(u) : f_{H(u)} > 1} < n program megoldásával dolgozzunk! ♣

4.2. Szabály (lefelé lépegetés). Az általános lépésben, egy h(u) = h(v) + 1 élen való csere után válasszuk v-t, ha lehetséges! ♣

Megjegyzés A minimális választás speciális esete a lefelé lépegetésnek.

4.6. Lemma (komplexitás). A lefelé lépegetés szabállyal módosított partíciós algoritmus legfeljebb O(n^{3}) lokális műveletet hajt végre.

Bizonyítás Legfeljebb n^{2} szintemelést hajtunk végre. Fedetlen pont nem keletkezik, így legfeljebb n-szer csökken a számuk. Az (u, v) segédélen végrehajtott csere hatására vagy csökken a kiválasztott u pont szintje, mert áttérünk u-ról v-re, vagy csökken a fedetlen pontok halmaza v-vel, mert ha nem tudunk v-re váltani, akkor v fedetlen volt a csere előtt. Tehát legfeljebb n csere után vagy meg kell emelni u szintjét, vagy megszüntetjük v fedetlenségét. Összevetve, legfeljebb n^{3} + n^{2} cserét hajtunk végre. ♣

Mindent összevetve: durván n^{3} lépés alatt, egy min_{X⊆S}{ |S−X|+∑_{i=1}^{k} r_{i}(X) }- elemszámú, partícionálható halmazt konstruáltunk. ♣

4.3. Matroid metszet probléma

Probléma Legyen M = {M_{i} = (S, r_{i})}_{i=1}^{2}, két darab matroid, a közös S alaphalmazon. Egy olyan F ⊆ S halmazt, mely mindkét matroidban független, közös függetlennek mondunk! Keressünk egy maximális elemszámú F ⊆ S, közös független halmazt! Más szóval oldjuk meg a

max{|F | : F ⊆ S és F ∈ F_{1} ⋂ F_{2}}

programot! ♠

Felső korlát Legyen X ⊆ S tetszőleges halmaz! Ekkor bármely F ⊆ S közös független halmazra

|F | ≤ r_{1}(S − X) + r_{2}(X).

u.i.: |F | = |F \X| + |F ⋂ X| |F \X| ≤ r_{1}(S − X) |F ⋂ X| ≤ r_{2}(X) ♣

Könnyen látszik, hogy mikor áll egyenlőség becsléseinkben.

Optimalitási feltétel F optimális, ha:

• F feszíti S − X-et az M_{1} matroidban

• F feszíti X-et az M_{2} matroidban ♣

Megmutatjuk, hogy az optimalitási feltételeket mindig ki lehet elégíteni.

4.7. Tétel (Edmonds). Legyen M = {M_{i} = (S, r_{i})}_{i=1}^{2}, két darab matroid S-en. Ekkor

max{|F | : F ⊆ S és F ∈ F_{1} ⋂ F_{2}} = min_{X⊆S}{ r_{1}(S − X) + r_{2}(X) }.

Bizonyítás max ≤ min: Felső korlátunk alapján világos. max ≥ min: Lokálisan javító algoritmust fogunk szerkeszteni. A maximális közös független halmazok nyilvánvalóan éppen a maximális bázismetszetek.

Ezért F -et B_{1} ⋂ B_{2} alakban keressük majd, ahol B_{1} ∈ B_{1} és B_{2} ∈ B_{2}. Fenntartunk tehát mindkét matroidból egy H = {B_{i} ∈ B_{i}}_{i=1}^{2} bázist. Ezenkívül illesztjük még H-hoz az S pontjainak egy olyan h : S → ℕ szintezését is, melyre teljesülnek bizonyos feltételek.

Fogalmak Legyen H = {B_{i} ∈ B_{i}}_{i=1}^{2}.

Definíció Egy s ∈ S pont (1, ¯2)-típusú, illetve (2, ¯1)-típusú, ha s ∈ B_{1}\B_{2}, illetve s ∈ B_{2}\B_{1} teljesül. ♣

Definíció Legyen u, v ∈ S.

• Ha u ∉ B_{1} és v ∈ C(B_{1}, u), akkor irányítsunk egy e élt u-ból v-be. Az így kapott élek A_{1} összességét, az S alaphalmazon értelmezett, a B_{1} bázishoz tartozó, befelé irányított bázisgráfnak nevezzük, és D_{1} = (S, A_{1})-gyel jelöljük.

• Ha u ∉ B_{2} és v ∈ C(B_{2}, u), akkor irányítsunk egy e élt v-ből u-ba. Az így kapott élek A_{2} összességét, az S alaphalmazon értelmezett, a B_{2} bázishoz tartozó, kifelé irányított bázisgráfnak nevezzük, és D_{2} = (S, A_{2})-vel jelöljük.

A D_{H} = (S, A_{H}) := (S, A_{1} ⋃ A_{2}) digráfot, a H-hoz tartozó segédgráfnak, éleit, a H-hoz tartozó segédéleknek nevezzük. ♣

Megjegyzés Világos, hogy egy (u, v) ∈ S^{2} pár pontosan akkor éle a segédgráfnak,

• ha u a kitüntetett pontja, v pedig egy másik pontja, az egyik B_{1}-re vonatkozó C_{1} alapkörnek,

• vagy ha v a kitüntetett pontja, u pedig egy másik pontja, az egyik B_{2}-re vonatkozó C_{2} alapkörnek.

Másképp szólva, (u, v) pontosan azért segédél, mert u-t becserélhetjük v helyett a B_{1} bázisba, vagy mert u-t kicserélhetjük v-re a B_{2} bázisból, a bázis tulajdonság fenntartásával. ♣ Definíció Legyen h : S → ℕ_{+} szintezés. Ha minden (1, ¯2)-típusú pont a legalsó szinten van, és minden segédél legfeljebb egy szintet lép lefelé, akkor H-normált, illetve H-illeszkedő szintezésről beszélünk. Más szóval, h-tól az

• u ∈ B_{1}\B_{2} ⟹ h(u) = 0

• (u, v) ∈ A_{H} ⟹ h(u) ≤ h(v) + 1.

illesztési feltételeket követeljük meg. ♣♣

4.8. Lemma (Terminálás). Legyen H = {B_{i} ∈ B_{i}}_{i=1}^{2}. Legyen továbbá h : S → ℕ_{+} H-hoz illesztett szintezés. Tegyük fel, hogy minden (¯1, 2)-típusú pont az n-edik szinten van. Ekkor készen vagyunk, tehát konstruálható egy olyan X ⊆ S halmaz, mellyel teljesülnek a B_{1} ⋂ B_{2}-re vonatkozó optimalitási feltételek.

Bizonyítás Létezik egy k üres szint, melyre 0 < k ≤ n. Legyen X a k-nál kisebb szintű pontok halmaza.

• X-ben nincs (¯1, 2)-típusú pont,

• S − X-ben nincs (1, ¯2)-típusú pont

• nincs S − X-ből X-be lépő segédél.

Ez azt jelenti, hogy minden B_{1} ⋂ B_{2}-n kívüli pontnak létezik alapköre B_{2}-re, illetve B_{1}-re vonatkozólag, attól függően, hogy X-nek, vagy S − X-nek az eleme. A harmadik tulajdonság miatt ezek az alapkörök teljes egészében Xben, illetve S − X-ben fekszenek. Összevetve, (B_{1} ⋂ B_{2}) ⋂ X nem bővíthető független X-ben az M_{2} matroidra vonatkozólag, és (B_{1} ⋂ B_{2}) ⋂(S − X) nem bővíthető független S − X-ben az M_{1} matroidra vonatkozólag. Tehát B_{1} ⋂ B_{2} feszíti X-et M_{2}-ben, és feszíti S − X-et M_{1}-ben. Ezt kellett igazolni. ♣

4.9. Lemma (Inicializálás). Konstruálható egy (H, h) illeszkedő pár.

Bizonyítás Valóban. h ≡ 0 minden H = {B_{i} ∈ B_{i}}_{i=1}^{2} -hoz illeszkedik. Az M_{i} matroidban futtatott mohó algoritmus pedig egy B_{i} bázissal tér vissza. ♣

Térjünk át az általános esetre! Úgy akarunk értelmezni egy lokális műveletet, hogy fenntartsa az illeszkedést, más szóval a kezdeti feltételeket, és alkalmasan iterálva, véges sok lépés után teljesüljön a terminálási lemma feltétele is.

4.2. Algoritmus (matroid metszet).

• input: M = {M_{i} = (S, r_{i})}_{i=1}^{2}

• output: (H = {B_{i} ∈ B_{i}}_{i=1}^{2}, h : S → ℕ) illeszkedő pár, hogy minden v ∈ S (¯1, 2)-típusú pontra, h(v) = n.

• inicializálás: Legyen h ≡ 0, H = {B_{i} ∈ B_{i}}_{i=1}^{2}, ahol B_{i}=mohó(M_{i})!

• általános lépés: Vegyünk egy (¯1, 2)-típusú u ∈ S pontot, melyre h(u) < n ! Hajtsuk végre rajta a lokális műveletet! Ezt alkalmasan iteráljuk!

• terminálás: Minden (¯1, 2)-típusú pont az n-edik szinten van.(Esetleg nincs is (¯1, 2)-típusú pont.) ♣

4.2. Lokális művelet (metszet). Legyen u ∈ S, (¯1, 2)-típusú pont, h(u) < n.

• Nincs (u, v) ∈ A_{H} , h(u) = h(v) + 1 ↦ Emeljünk u szintjén!

– h(u) := h(u) + 1!

• Van (u, v) ∈ A_{H}, h(u) = h(v) + 1 ↦ (u, v)-becseréljünk az első, és (u, v)-kicseréljünk a második matroidban!

– Ha (u, v) ∈ A_{1}, akkor B_{1} := B_{1} + u − v!

– Ha (u, v) ∈ A_{2}, akkor B_{2} := B_{2} − u + v! ♣

Alkalmas Iterálási Szabályok

4.3. Szabály (minimális választás). A min{h(u) : u (¯1, 2)-típusú} < n program egy megoldását válasszuk ki az általános lépésben! ♣

4.4. Szabály (lefelé lépegetés). Az u kiválasztása, majd egy (u, v) segédélen való csere elvégzése után, ha lehetséges, válasszuk ki v-t az általános lépésben! ♣

Megjegyzés A minimális választás speciális esete a lefelé lépegetésnek. ♣

4.10. Lemma (komplexitás). A lefelé lépegetés szabállyal módosított metszet algoritmus legfeljebb O(n^{3}) lokális műveletet hajt végre.

Bizonyítás Kísérő paraméterek változásait fogjuk megfigyelni. Ezen megfigyeléseinket összerakva, egyfajta szemmel már át tudjuk tekinteni az algoritmus lefutásának a struktúráját.

Kísérő Paraméterek

• h szintfüggvény: kezdetben azonosan 0, sosem csökken, és az n-edik szint fölé nem emelkedik.

• |B_{1}\B_{2}| elemszám: kezdetben legfeljebb n, és sosem nő.

• h(u), ahol u a kiválasztott pont: legalább 0, legfeljebb n, és ha a fenti

két paraméter nem változik, akkor ez csökken. ♣ Ebből már világos az O((n^{2} + n)n) futásidőbecslés.

(1, ¯2)-típusú pont nem keletkezik, mert egy ilyen szükségképpen (1, ¯ ¯2), illetve (¯1, ¯2)-típusú volna a cserélés előtt, attól függően, hogy B_{2}-n, vagy B_{1}-en hajtottuk végre azt, tehát ez a pont nem lehet sem a kiszemelt u pont, mert az (¯1, 2)-típusú, sem a másik v pont, hiszen az a B_{2}-n történő kicserélés esetén (∗, ¯2)-típusú, B_{1}-en történő becserélés esetén pedig (1, ∗)-típusú pont, és nem lehet a többi pont sem, mert ezeknek a bázisokhoz viszonyított elhelyezkedése nem változik meg, lokális műveletről lévén szó. Tehát a |B_{1}\B_{2}| elemszám sosem nő.

Ha az u kiszemelt pont, szintje nem csökken egy lépésben, (ezen természetesen, kicsit pongyolán azt értjük, hogy a lépés után egy nem kisebb szintű pontot szemelünk ki u helyett), akkor a választási szabály miatt, ebben a lépésben vagy nem volt egy szinttel alacsonyabban olyan v pont, mellyel u-t cserélhettük volna, és ilyenkor u szintjét növeljük meg eggyel, vagy volt ilyen v pont, de az u-val való cserélés után v nem-(¯1, 2)-típusú ponttá vált, és ezért nem szemelhettük ki u helyett. Ilyenkor cserélés előtt v szükségképpen (1, ¯2)-típusú, tehát |B_{1}\B_{2}| lecsökken eggyel, ahogy állítottuk. Valóban, máskülönben v csak (¯1, ¯2) vagy (1, 2)-típusú pont lehetne cserélés előtt, de mindkét esetben (¯1, 2)-típusú pont lenne belőle a cserélés után, hiszen első esetben csak B_{2}-n, második esetben csak B_{1}-en cserélhetünk. Tehát, ha h nem nő, és |B_{1}\B_{2}| sem csökken, akkor h(u) csökken egyet.

Ezzel beláttuk a kísérő paraméterek nem nyilvánvaló változási tulajdonságait is. ♣

4.11. Lemma (megmaradási). Műveletünk fenntartja az illesztési feltételeket.

Bizonyítás B_{1} + u − v ∈ B_{1}, és B_{2} − u + v ∈ B_{2}, mert csak segédél mentén végezzük a cserét. Tehát H végig bázisokból áll.

A H-normalitást vagy úgy ronthatjuk el, hogy a 0-szint felett keletkezik egy (1, ¯2)-típusú pont, vagy úgy, hogy megemeljük egy (1, ¯2)-típusú pont szintjét. A komplexitás vizsgálatánál már láttuk, hogy nem keletkezik (1, ¯2)-típusú pont, és csak (¯1, 2)-típusú pont szintjét emeljük meg, tehát nem tudjuk elrontani a H-normalitást.

A H-illeszkedést csak úgy ronthatjuk el, ha megemeljük egy pontos segédél talpának a szintjét, vagy ha valamelyik bázison végrehajtott cseréléssel behozunk a segédgráfba egy olyan élt, mely a csere előtt még nem segédél, viszont megsértené az illeszkedést, ha az volna.

Az első eset kizárt, hiszen csak olyan pont szintjét emeljük, melyre nem illeszkedik pontos él.

A második eset is kizárt, hiszen ha egy h-illeszkedő bázison kicserélést hajtunk végre, akkor egy h-illeszkedő bázishoz jutunk, amint azt korábban megmutattuk. Ez a becserélésre is igaz. Valóban, egyrészt

D(M, B, be) =: D = D(M^{∗}, B^{∗}, ki),

másrészt ha egy B ∈ B(M) bázison (u, v)-becserélést hajtunk végre az M matroidban, és a B + u − v ∈ B(M) bázis D′ befelé irányított bázisgráfjához jutunk, akkor ez ugyanaz a művelet, mint amikor a B^{∗} ∈ B(M^{∗}) bázison (u, v)- kicserélést hajtunk végre az M^{∗} matroidban, és a B^{∗} − u + v ∈ B(M^{∗}) bázis D′ kifelé irányított bázisgráfjához jutunk, hiszen

D(M, B + u − v, be) =: D′ = D(M^{∗}, B^{∗} − u + v, ki).

Tehát, ha a D befelé irányított bázisgráf h-illeszkedő, akkor D′ befelé irányított bázisgráf is az. ♣

Mindent összevetve, durván n^{3} lépés alatt, egy min_{X⊆S}{ r_{1}(S − X) + r_{2}(X) }- elemszámú, közös független halmazt konstruáltunk. ♣

4.4. Matroid tagság probléma

Probléma Legyen M = (S, r) egy matroid az S alaphalmazon, és legyen m ∈ ℝ^{S} egy pont az n-dimenziós térben. Döntsük el, hogy a B(r) bázispoliéder tartalmazza-e ezt a pontot vagy sem! ♠

Feltehető

• m(u) ≥ 0 (∀u ∈ S)

• m(S) = r(S) ♣

Definíció S pontjait súlyoknak is mondjuk, egy u pont súlya m(u). ♣

Definíció Legyen y ∈ ℝ^{S}. Egy u ∈ S súly y-túlfedett, ha y(u) > m(u), és y-fedetlen, ha y(u) < m(u). ♣

Eldöntési Feltételek Legyen y ∈ conv{B(M)}!

• nincs y-fedetlen súly S-ben ⟹ m ∈ conv{B(M)}

• van olyan X ⊆ S halmaz, mely tartalmaz egy y-fedetlen súlyt, de egyetlen y-túlfedett súly sincs benne, ezenfelül az y, egy konvex kombinációként való előállításában szereplő bázisok feszítik X-et. ⟹ m ∉ B(r).

Bizonyítás

• Nyilvánvaló, hiszen m(S) = y(S), és minden u ∈ S-ra m(u) ≤ y(u), tehát ilyenkor m = y ∈ conv{B(M)}.

• Legyen y = ∑_{i=1}^{k} λ_{i}B_{i}, ahol B_{i} ∈ B(M), λ_{i} ≥ 0 , és ∑_{i=1}^{k} λ_{i} = 1. m(X) > y(X) = ∑_{i=1}^{k} λ_{i}B_{i}(X) = r(X). Tehát m ∉ B(r). ♣

Megmutatjuk, hogy az eldöntési feltételek valamelyikét mindig ki lehet elégíteni.

4.12. Tétel (Edmonds). B(r) egész poliéder, azaz B(r) = conv{B(M)}.

Bizonyítás

• azaz: Világos, hogy a B(r) bázispoliéder egész pontjai éppen az M matroid bázisai, hiszen 0 ≤ m(u) ≤ r(u) ≤ 1, m(B) ≤ r(B) ≤ |B|, ahol B := {u ∈ S : m(u) ≠ 0}, és m(S) = r(S).

• ⊇: B(M) ⊆ B(r), és B(r) konvexitása miatt nyilvánvaló.

• ⊆: Lokálisan javító algoritmust fogunk szerkeszteni annak belátására, hogy B(r)\conv{B(M)} = ∅, más szóval, vagy m ∈ conv{B(M)}, vagy m ∉ B(r), vagyis készen vagyunk, ha az eldöntési feltételek valamelyikét mindig ki lehet elégíteni.

Fogalmak Legyen y = ∑_{i=1}^{k} λ_{i}B_{i} ∈ conv{B(M)}!

Definíció Legyen A_{i} ⊆ S^{2}, a B_{i} bázishoz tartozó befelé irányított bázisgráf élhalmaza! A D_{y} = (S, A_{y}) := (S, ⋃_{i=1}^{k} A_{i}) digráfot, az y-hoz tartozó segédgráfnak, éleit az y-hoz tartozó segédéleknek nevezzük. ♣

Definíció Legyen h : S → ℕ_{+} szintezés! Ha minden túlfedett súly a legalsó szinten van, és minden segédél legfeljebb egy szintet lép lefelé, akkor y-normált, illetve y-illeszkedő szintezésről beszélünk. Más szóval, h-tól az

• y(u) > m(u) ⟹ h(u) = 0

• (u, v) ∈ A_{y} ⟹ h(u) ≤ h(v) + 1.

illesztési feltételeket követeljük meg. ♣♣

4.13. Lemma (Terminálás). Legyen y = ∑_{i=1}^{k} λ_{i}B_{i}! Legyen továbbá h : S → ℕ_{+} y-hoz illesztett szintezés! Tegyük fel, hogy minden fedetlen súly az n-edik szinten van! Ekkor készen vagyunk, tehát teljesül valamelyik eldöntési feltétel.

Bizonyítás Ha nincs fedetlen súly, akkor készen vagyunk. Ha van, akkor létezik egy k üres szint, melyre 0 < k < n. Legyen X a k-nál nagyobb szintű súlyok halmaza!

• X-ben nincs túlfedett súly, • X-ben van fedetlen súly

• nincs X-ből S − X-be lépő segédél.

X utolsó tulajdonsága azt jelenti, hogy semelyik B_{i} ⋂ X bázismetszet sem bővíthető a függetlenség megtartásával X-ben, tehát B_{i} feszíti X-et. Ezt kellett igazolni. ♣

4.14. Lemma (Inicializálás). Konstruálható egy (y, h) illeszkedő pár.

Bizonyítás Valóban. h ≡ 0 minden y konvex kombinációhoz illeszkedik. Az M matroidban futtatott mohó algoritmus pedig egy B_{1} bázissal tér vissza, amit egytagú konvex kombinációnak tekinthetünk. ♣

Térjünk át az általános esetre! Úgy akarunk értelmezni egy lokális műveletet, hogy fenntartsa az illeszkedést, más szóval a kezdeti feltételeket, és alkalmasan iterálva, véges sok lépés után teljesüljön a terminálási lemma feltétele is.

4.3. Algoritmus (matroid tagság).

• input: M = (S, r), m ∈ ℝ_{+}^{S}, m(S) = r(S).

• output: (y = ∑_{i=1}^{k} λ_{i}B_{i}, h : S → ℕ) illeszkedő pár, hogy minden u ∈ S fedetlen súlyra, h(u) = n.

• inicializálás: Legyen h ≡ 0, y = 1B_{1}, ahol B_{1}=mohó(M) !

• általános lépés: Vegyünk egy fedetlen u ∈ S súlyt, melyre h(u) < n ! Hajtsuk végre rajta a lokális műveletet! Ezt alkalmasan iteráljuk!

• terminálás: Minden fedetlen súly az n-edik szinten van.(Esetleg nincs is fedetlen súly.) ♣

4.3. Lokális művelet (matroid tagság). Legyen (y, h) illeszkedő pár, és u ∈ S fedetlen súly, melyre h(u) < n!

• Nincs (u, v) ∈ A_{y} , h(u) = h(v) + 1 ↦ Emeljük meg u szintjét!

– h(u) := h(u) + 1!

• Van (u, v) ∈ A_{y}, h(u) = h(v)+1 ↦ u-n növeljük, v-n csökkentsük y értékét valamelyik matroidban! Számítsuk ki ε := min{m(u) − y(u), λ_{i}}-t! Válasszuk meg i-t, hogy (u, v) ∈ A_{i} teljesüljön!

– Ha ε = λ_{i}, akkor y := ∑_{j≠i} λ_{j}B_{j} + λ_{i}(B_{i} + u − v)! [az (u, v) élt telítő javító lépés az i-edik matroidban]

– Ha ε = m(u) − y(u), akkor y := ∑_{j≠i} λ_{j}B_{j} +(λ_{i} − ε)B_{i} + ε(B_{i} + u − v)! [az u kiválasztott pontot semlegesítő javító lépés az i-edik matroidban] ♣

Alkalmas Iterálási Szabályok

4.5. Szabály (maximális választás). A max{h(u) : u fedetlen} < n program egy megoldását válasszuk ki az általános lépésben! ♣

Megszakítás[Carathéodory tétellel való módosítás] Ha olyan telítő lépést hajtunk végre, ami az y konvex felbontásának a tagszámát n fölé növeli, akkor fejezzük ki y-t ezen bázisokból, legfeljebb n tag konvex kombinációjaként. A Carathéodory tétel értelmében ez O(n^{3}) lépésben megtehető, hiszen a bázisok a B(S) = r(S) hipersíkban fekszenek. ♣ Meg kell vizsgálnunk algoritmusunk komplexitását és a lokális művelet érvényességét.

4.15. Lemma (érvényesség). Lokális műveletünk fenntartja a kezdeti feltételeket.

Bizonyítás B_{i} − u + v ∈ B, mert csak segédél mentén végezzük a javító lépéseinket. Tehát H végig bázisokból áll.

A H-normalitást vagy úgy ronthatjuk el, hogy a 0-szint felett keletkezik egy túlfedett pont, vagy úgy, hogy megemeljük egy túlfedett pont szintjét. Mivel csak fedetlen pontnál emeljük y értékét, és ott se m értéke fölé, nem keletkezik túlfedett pont. Csak fedetlen pont szintjét emeljük meg, így nem tudjuk elrontani a h szintezés H-normalitását.

A H-illeszkedést csak úgy ronthatjuk el, ha megemeljük egy pontos segédél talpának a szintjét, vagy ha valamelyik bázison végrehajtott javító lépéssel behozunk a segédgráfba egy olyan élt, mely a csere előtt még nem segédél, viszont megsértené az illeszkedést, ha az volna.

Az első eset kizárt, hiszen csak olyan pont szintjét emeljük, melyre nem illeszkedik pontos él.

A második eset is kizárt, hiszen ha egy h-illeszkedő bázison becserélést hajtunk végre, egy h-illeszkedő bázishoz jutunk. Javító lépésünk pedig egy ilyen gráf éleit adja hozzá a javítógráfhoz. ♣

4.16. Lemma (komplexitás). A maximális választási szabállyal módosított matroid tagság algoritmus legfeljebb O(n^{6}) lokális műveletet hajt végre.

Bizonyítás Kísérő paraméterek változásait fogjuk megfigyelni. Ezen megfigyeléseinket összerakva, egyfajta szemmel már át tudjuk tekinteni az algoritmus lefutásának a struktúráját. Kísérő Paraméterek

• h szintfüggvény: kezdetben azonosan 0, sosem csökken, és az n-edik szint fölé nem emelkedik.

• h(u), ahol u a kiszemelt pont: legalább 0, legfeljebb n, és ha a fenti paraméter nem változik, akkor ez nem nő.

• ∑_{λ(B)>0} h(B) szintösszeg: Legalább 0, a Carathéodory tétellel való módosítás miatt legfeljebb n^{2}|{B : λ(B) > 0}| ≤ n^{3}, és ha a fenti két paraméter nem változik, akkor ez csökken egyet. ♣

Ebből már világos az O(n^{2}nn^{3}) futásidőbecslés.

A szintfüggvény két változása között javító lépéseket teszünk. Az (u, v) élen végrehajtott javítás hatására csak v válhat fedetlenné, de ennek h(v) szintje kisebb, mint u szintje, így a maximális választás miatt valóban nem nő a h(u) paraméter értéke.

A szintfüggvény két változása között a h(u) paraméter csak akkor csökkenhet, ha az u-t semlegesítő lépést hajtunk végre. Tehát, ha ezen két paraméter változatlan, akkor telítő javítást végzünk, és ez valóban h(u) − h(v) = 1-gyel csökkenti a szintösszeget. ♣ Mindent összevetve, durván n^{6} lépés alatt eldöntöttük, hogy a m ∈ ℝ^{S} vektor benne van-e a B(r) bázispoliéderben vagy sem. ♣

5. Polimatroidok

5.1. Eredmények polimatroidokkal kapcsolatban

Legyen S egy n elemű halmaz! Legyen b : S → ℝ szubmoduláris, azaz b(X) + b(Y) ≥ b(X ∪ Y) + b(X ∩ Y) teljesül minden X ⊆ S halmazra! Egy halmazfüggvényről mindig feltesszük, hogy normalizált, azaz b(∅) = 0, mert a felmerülő feladatok invariánsak lesznek a konstanssal való eltolásra.

Egy szubmoduláris függvényből a következő két poliédert szokás elkészíteni,

S(b) := {y ∈ ℝ^{S} : y(X) ≤ b(X) ∀X ⊆ S},
B(b) := {y ∈ P (f) : y(S) = b(S)}.

Az S(b) poliédert szubmoduláris poliédernek, a B(b) poliédert bázispoliédernek nevezzük. Egy y vektort függetlennek vagy szubbázisnak, illetve bázisnak nevezünk, ha eleme S(b)-nek, illetve B(b)-nek.

Tegyük fel, hogy y ∈ B(b) bázis. Egy olyan X ⊆ S halmazt, melyhez tartozó sor egyenlőséggel teljesül, azaz y(X) = b(X), y-pontos halmaznak nevezünk. Az y-pontosságnak tehát definíció szerint az az oka, hogy y feszíti X-et a b szubmoduláris függvényre vonatkozólag, azaz y(X) = b(X). A két fogalom között csupán annyi a különbség, hogy melyik objektum szemszögéből vizsgáljuk a kapcsolatukat. Ezen megjegyzés folytán beszélhetünk X-pontos bázisról, és hogy ennek az az oka, hogy X feszíti őt.

Az y-pontos halmazok összességét P(y)-nal jelöljük. A szubmodularitás folytán P(y) zárt a metszetre és az egyesítésre. Így minden s ∈ S elemhez létezik egy egyértelmű, minimális őt tartalmazó pontos halmaz, nevezetesen az összes ilyen metszete, hiszen egy mindenképpen van, nevezetesen az alaphalmaz ilyen. Az így legyártott pontos halmazt P_{y}(s)-sel jelöljük, és az s pont pontos burkának nevezzük. Egy pontos halmaz egyébként pontosan akkor pontos burka valamelyik pontjának, ha egyesítés irreducibilis. Valóban, a pontos burkok ilyenek, és egy egyesítés irreducibilis pontos halmaznak létezik olyan pontja, amelyet nem lehet nálánál szűkebb pontos halmazzal lefedni. Így ezen pontját tartalmazó pontos halmazok mindannyian tartalmazzák őt, tehát előáll ezek metszeteként.

Ha b-ről feltesszük, hogy valamely matroid r rangfüggvényével egyenlő, yról pedig azt, hogy a matroid egy B ∈ B bázisa, akkor könnyen látható, hogy s ∈ B esetén P_{B}(s) = {s}, s ∉ B esetén pedig P_{B}(s) = C(B, s).

Ha b-ről a szubmodularitáson és normáltságon túl még azt is feltesszük, hogy monoton növő, akkor polimatroidfüggvénynek nevezzük, és f-el jelöljük. Polimatroidfüggvényből polimatroidot készíthetünk,

P (f) := {y ∈ S(f) : y ≥ 0}.

Azért is nézzük ezt S(f) helyett, mert ha például egy y ∈ S(f) szubbázisnak y(s) negatív komponense, akkor y(s)-et nullára növelhetjük anélkül, hogy ki kellene lépnünk a szubmoduláris poliéderből. Valóban, a növelés akadálya csak egy s-et tartalmazó pontos halmaz lehet, így az s elem y-pontos burkának is léteznie kell, de erre y(P_{y}(s)) < y(P_{y}(s) − s) ≤ b(P_{y}(s) − s) ≤ b(P_{y}(s)) lenne, y-pontossága ellenére. Speciálisan B(f) ⊆ P (f) is teljesül.

A P (f) polimatroidról világos, hogy van eleme, hiszen 0 ∈ P (f). Ellenben ugyanez már nem mondható el a B(f) bázispoliéderről. A választ a tetszőleges b szubmoduláris függvényre futtatható mohó algoritmus adja meg.

Rögzítsük S egy ≤ lineáris rendezését! Egy s ∈ S elemnél nem nagyobb elemek halmazát jelöljük s_{≤}-vel. Világos, hogy egyértelműen létezik egy olyan y_{≤} ∈ ℝ^{S} vektor, melyre y(s_{≤}) = b(s_{≤}), minden s ∈ S elemre. b szubmodularitását felhasználva könnyen igazolható, hogy y ∈ S(b). y valójában eleme B(b)-nek is, hiszen S = s_{≤}, ahol s ∈ S, a ≤ lineáris rendezésre nézve legnagyobb elem. Kaptuk tehát, hogy a bázispoliéder sem üres.

5.2. Polimatroid tagság probléma

Probléma Legyen f : 2^{S} → ℝ_{+} polimatroidfüggvény az S alaphalmazon, és legyen m ∈ ℝ^{S} egy pont az n-dimenziós térben. Döntsük el, hogy a P (f) polimatroid tartalmazza-e ezt a pontot vagy sem! Felvethető ez a kérdés a B(f) bázispoliéderre, és az S(f) szubmoduláris poliéderre is. ♠

Megjegyzés Nyilván elég eldönteni a kérdést az S(f) szubmoduláris poliéderre vonatkozólag, hiszen

• m ∈ P (f) ⟺ m ≥ 0 és m ∈ S(f)

• m ∈ B(f) ⟺ m ∈ P (f) és m(S) = f(S).

f tulajdonságai közül is csak a szubmodularitást fogjuk kihasználni, ezért a továbbiakban b-vel jelöljük. ♣

Megjegyzés Az előző megjegyzés valójában nem növeli az általánosságot ugyanis megadható olyan z = z_{b} ∈ ℝ^{S} vektor, hogy

m ∈ S(b) ⟺ m + z_{b} ∈ S(f_{b}),

ahol f_{b} = b + z_{b} polimatroidfüggvény. Valóban, az ekvivalencia, a szubmodularitás és a normáltság automatikusan teljesül bármely z vektorral való eltolás esetén. A monotonitás követelményét írhatjuk a b(X) − b(Y) + z(X − Y) ≥ 0 alakba, ahol X ⊇ Y. Elég z-t az X = Y + u speciális esetre meghatározni, hiszen ha az u ∈ S-ra nyert egyenlőtlenségeket a X ⊇ Z + u ⊃ Z ⊇ Y fedésekre összeadjuk, ahol Z-t egy finomíthatatlan lánc elemein futtatjuk végig, ahol Z + u a láncban Z-re rákövetkező elem, akkor az X ⊇ Y párra vonatkozó általános egyenlőtlenséget kapjuk vissza. A speciális esetnek z_{b}(u) := b(S − u) − b(S) megoldása, mert b szubmoduláris. ♣

5.1. Lemma (eldöntés). Legyen y ∈ B(b).

• ha minden u ∈ S-ra: y(u) ≥ m(u), akkor \underline{m ∈ S(b)}.

• ha létezik egy X ⊆ S, melyre

1. ∀x ∈ X : y(x) ≤ m(x)

2. ∃x ∈ X : y(x) < m(x)
3. y feszíti X-et b-re vonatkozólag, akkor \underline{m ∉ S(b)}.

Bizonyítás

• Nyilvánvaló, hiszen bármely X ⊆ S halmazra m(X) ≤ y(X), és b(X) ≥ y(X), tehát m(X) ≤ b(X), vagyis m ∈ S(b).

• Nyilvánvaló, hiszen m(X) > y(X), és b(X) = y(X), tehát m(X) ≤ b(X), így m ∈ S(b). ♣

Mutassuk meg, hogy az eldöntési feltételek valamelyikét mindig ki lehet elégíteni! A fejezet további részében ennek a tervnek a megvalósítását készítjük elő.

Fogalmak Legyen y ∈ B(b)!

Definíció Legyen u ∈ S! Ha y(u) < m(u), akkor u-t y-fedetlennek, ha y(u) > m(u), akkor y-túlfedettnek hívjuk. Egy u pontot súlynak is képzelhetünk, m(u) súllyal. ♣

Megjegyzés Ha minden súlyt lefedtünk, készen vagyunk, m ∈ S(b). ♣

Definíció Minden u ∈ S pontból húzzunk egy élt a P_{y}(u) halmaz u-tól különböző pontjaiba, azaz u y-pontos burkának többi elemébe! Az így nyert éleket segédéleknek nevezzük, és A_{y}-al jelöljük az általuk alkotott összességet. A D_{y} := (S, A_{y}) kifelé irányított bázisgráfot az y-hoz tartozó segédgráfnak hívjuk. ♣

Definíció Legyen h : S → ℕ_{+} szintezés! Ha minden túlfedett súly a legalsó szinten van, és minden segédél legfeljebb egy szintet lép lefelé, akkor y-normált, illetve y-illeszkedő szintezésről beszélünk. Más szóval, h-tól az

• y(u) > m(u) ⟹ h(u) = 0

• (u, v) ∈ A_{y} ⟹ h(u) ≤ h(v) + 1.

illesztési feltételeket követeljük meg. ♣♣ Példa[eldöntés] Legyen y ∈ B(b)! Legyen továbbá h : S → ℕ_{+} y-hoz illesztett szintezés!

Tegyük fel, hogy minden fedetlen súly az n-edik szinten van! Ekkor készen vagyunk, tehát teljesül valamelyik eldöntési feltétel. Bizonyítás Ha nincs fedetlen súly, akkor készen vagyunk. Ha van, akkor létezik egy k üres szint, melyre 0 < k < n. Legyen X a k-nál nagyobb szintű súlyok halmaza!

• X-ben nincs túlfedett súly,

• X-ben van fedetlen súly,

• nincs X-ből S − X-be lépő segédél.

X utolsó tulajdonsága azt jelenti, hogy X = ⋃_{u∈X} P_{y}(u), tehát X y-pontos, vagyis y feszíti X-et. Ezt kellett igazolni. ♣

Megjegyzés Tegyük fel, hogy az (y, h) pár kielégíti példánk feltételeit! Legyen x = m ⋀ y! Ekkor x ≤ m, és x ∈ S(b). Fenti bizonyításunkból világos az is, hogy x(S) = m(S − X) + y(X) = m(S − X) + b(X), ahol X ⊆ S az üres k szint feletti pontok halmaza. Megfordítva, ha felteszzük, hogy x ≤ m, és x ∈ S(b), ezenkívül X ⊆ S egy tetszőleges halmaz, akkor x(S) ≤ m(S − X) + x(X) ≤ m(S − X) + b(X). Ezeket összevetve megállapíthatjuk, hogyha sikerül találni egy ilyen (y, h) párt, akkor ezzel bizonyítást nyer az alábbi minimax formula is:

5.2. Tétel (Edmonds). Legyen b : 2^{S} → ℝ_{+} szubmoduláris függvény, m ∈ ℝ^{S} n-dimenziós vektor! Ekkor

max{x(S) : x ≤ m és x ∈ S(b)} = min_{X⊆S}{m(S − X) + b(X)}. ♣

Megjegyzés Egy m ∈ ℝ^{S} vektort moduláris halmazfüggvénynek tekinthetünk. Vezessük be a b_{1} = m, b_{2} = b jelöléseket! b_{1}, b_{2} : 2^{S} → ℝ szubmoduláris halmazfüggvények. Ha formálisan behelyettesítjük ezeket a jeleket a fenti formulába, ezen a kényelmesebbnek tűnő nyelven megfogalmazott sejtéshez jutunk:

max{x(S) : x ∈ S(b_{1}) ⋂ S(b_{2})} = min_{X⊆S}{b_{1}(S − X) + b_{2}(X)}. ♣

A következő fejezetben általánosítjuk eddigi eredményeinket, és kísérletet teszünk az itteni kedvező tulajdonságokkal rendelkező (y, h) párnak megfelelő, ott (y_{1}, y_{2}, h) hármas képében jelentkező objektum felkutatására.

5.3. Polimatroid metszet probléma

Probléma Legyen b_{1}, b_{2} : 2^{S} → ℝ két darab szubmoduláris függvény, a közös S alaphalmazon. Egy olyan x ∈ ℝ^{S} vektort, mely mindegyik b_{i} szubmoduláris függvény által meghatározott S(b_{i}) szubmoduláris poliéderben benne van, közös független vektornak vagy pontnak nevezünk! Keressünk egy maximális komponensösszegű x ∈ ℝ^{S}, közös független vektort! Más szóval oldjuk meg a

max{x(S) : x ∈ ℝ^{S} és x ∈ S(b_{1}) ⋂ S(b_{2})}

programot! ♠

Felső korlát Legyen X ⊆ S tetszőleges halmaz! Ekkor bármely x ∈ ℝ^{S} közös független vektorra

x(S) ≤ b_{1}(S − X) + b_{2}(X).

Bizonyítás Legyen y_{1} ∈ B(b_{1}), y_{2} ∈ B(b_{2}), és z := y_{1} ⋀ y_{2} ≥ x! Mivel x-et bázissá terjeszthetjük b_{i}-re vonatkozólag, léteznek ilyen y_{i} ∈ B(b_{i}) vektorok. Ekkor bármely X ⊆ S halmazra:

• x(S) ≤ z(S) = z(S\X) + z(X) ≤ y_{1}(S\X) + y_{2}(X)

• y_{1}(S\X) ≤ b_{1}(S − X)

• y_{2}(X) ≤ b_{2}(X) ♣

Könnyen látszik, hogy mikor áll egyenlőség becsléseinkben. Például szükséges ehhez, hogy x = z, azaz x bázismetszet alakú legyen.

Optimalitási feltétel z = y_{1} ⋀ y_{2} optimális, ha:

• u ∈ S − X ⟹ y_{1}(u) ≤ y_{2}(u),

• u ∈ X ⟹ y_{2}(u) ≤ y_{1}(u),

• y_{1} feszíti S − X-et az S(b_{1}) polimatroidban,

• y_{2} feszíti X-et az S(b_{2}) polimatroidban. ♣

Megmutatjuk, hogy az optimalitási feltételeket mindig ki lehet elégíteni.

5.3. Tétel (Edmonds). Legyen b_{1}, b_{2} : 2^{S} → ℝ két szubmoduláris függvény S-en! Ekkor

max{x(S) : x ∈ S(b_{1}) ⋂ S(b_{2})} = min_{X⊆S}{ b_{1}(S − X) + b_{2}(X) }.

Bizonyítás max ≤ min: Felső korlátunk alapján világos. max ≥ min: Lokálisan javító algoritmust fogunk szerkeszteni. A maximális közös független vektorok nyilvánvalóan éppen a maximális bázismetszetek. Ezért x-et z = y_{1} ⋀ y_{2} alakban keressük majd, ahol y_{1} ∈ B(b_{1}) és y_{2} ∈ B(b_{2}). Fenntartunk tehát mindkét matroidból egy (y_{1}, y_{2}) bázist. Ezenkívül illesztjük még (y_{1}, y_{2})-höz az S pontjainak egy olyan h : S → ℕ szintezését is, melyre teljesülnek bizonyos feltételek.

Fogalmak Legyen y_{1} ∈ B(b_{1}), y_{2} ∈ B(b_{2}), y := (y_{1}, y_{2}) !

Definíció Egy u ∈ S pont y-aktív, illetve y-passzív, ha y_{2}(u) < y_{1}(u), illetve y_{1}(u) < y_{2}(u) teljesül. ♣

Definíció Minden u ∈ S pontból húzzunk egy élt a P_{1}(u) halmaz u-tól különböző pontjaiba, azaz u y_{1}-pontos burkának többi elemébe! Az így nyert éleket y_{1}-segédéleknek nevezzük, és A_{1}-el jelöljük az általuk alkotott összességet. Minden u ∈ S pontba húzzunk egy élt a P_{1}(u) halmaz u-tól különböző pontjaiból, azaz u y_{2}-pontos burkának többi eleméből u-ba! Az így nyert éleket y_{2}-segédéleknek nevezzük, és A_{2}-vel jelöljük az általuk alkotott összességet. A D_{12} := (S, A_{1} ⋃ A_{2}) kifelé, illetve befelé irányított bázisgráf unióját y-segédgráfnak hívjuk. ♣

Definíció Legyen h : S → ℕ_{+} szintezés! Ha minden y-passzív pont a legalsó szinten van, és minden y-segédél legfeljebb egy szintet lép lefelé, akkor y-normált, illetve y-illeszkedő szintezésről beszélünk. Más szóval, h-tól az

• y_{1}(u) < y_{2}(u) ⟹ h(u) = 0,

• (u, v) ∈ A_{y} ⟹ h(u) ≤ h(v) + 1

illesztési feltételeket követeljük meg. ♣♣ 5.4. Lemma (Terminálás). Legyen y_{1} ∈ B(b_{1}), y_{2} ∈ B(b_{2}), y = (y_{1}, y_{2})! Legyen továbbá h : S → ℕ_{+}, y-hoz illesztett szintezés! Tegyük fel, hogy minden y-passzív pont az n-edik szinten van! Ekkor készen vagyunk, tehát konstruálható egy olyan X ⊆ S halmaz, mellyel teljesülnek az y-ra vonatkozó optimalitási feltételek.

Bizonyítás Létezik egy k üres szint, melyre 0 < k ≤ n. Legyen X a k-nál nagyobb szintű pontok halmaza!

• X-ben nincs y-passzív pont,

• S − X-ben nincs y-aktív pont,

• nincs S − X-ből X-be lépő y-segédél.

Tehát, ha a u pont X-beli, akkor y_{2}(u) < y_{1}(u), ha S − X-beli, akkor y_{1}(u) < y_{2}(u). Ezenkívül X = ⋃_{u∈X} P_{2}(u), és S − X = ⋃_{u∈S−X} P_{1}(u). Tehát az X halmaz y_{2}-pontos, az S − X halmaz pedig y_{1}-pontos, azaz y_{2} feszíti S − X-et, y_{1} pedig feszíti X-et, b_{2} illetve b_{1}-re vonatkozólag. Ezt kellett bizonyítanunk. ♣

5.5. Lemma (Inicializálás). Konstruálható egy (y, h) illeszkedő pár.

Bizonyítás Valóban. h ≡ 0 minden y-hoz illeszkedik. Az b_{i} szubmoduláris függvénnyel futtatott mohó algoritmus pedig egy y_{i} bázissal tér vissza. ♣

Térjünk át az általános esetre! Úgy akarunk értelmezni egy lokális műveletet, hogy fenntartsa az illeszkedést, más szóval a kezdeti feltételeket, és alkalmasan iterálva, véges sok lépés után teljesüljön a terminálási lemma feltétele is.

5.1. Algoritmus (polimatroid metszet).

• input: b_{1}, b_{2} : 2^{S} → ℝ polimatroid függvények S-en.

• output: (y = (y_{1}, y_{2}), h) illeszkedő pár, hogy minden u ∈ S y-aktív pontra, h(u) = n.

• inicializálás: Legyen h ≡ 0, y_{1} ∈ B(b_{1}), y_{2} ∈ B(b_{2}), ahol y_{i}=mohó(b_{i})!

• általános lépés: Vegyünk egy y-aktív u ∈ S pontot, melyre h(u) < n ! Hajtsuk végre rajta a lokális műveletet! Ezt alkalmasan iteráljuk!

• terminálás: Minden y-aktív pont az n-edik szinten van.(Esetleg nincs is y-aktív pont.) ♣ 5.1. Lokális művelet (polimatroid metszet). Legyen (y, h) illeszkedő pár! Legyen u ∈ S, y-aktív pont, h(u) < n!

• Nincs olyan (u, v) ∈ A_{y}, melyre h(u) = h(v) + 1 ↦ Emeljünk!:

– h(u) := h(u) + 1!

• Van olyan (u, v) ∈ A_{y}, melyre h(u) = h(v) + 1 ↦ Számítsuk ki !:

– Ha (u, v) ∈ A_{1}, akkor ε_{1} := min{ε_{11} + ε_{12}}, ahol ε_{11} := max{δ_{1} : y_{1} + δ_{1}(−u + v) ∈ B(b_{1})}, ε_{12} := y_{1}(u) − y_{2}(u), és y_{1} := y_{1} + ε_{1}(−u + v)! (csökkentés,növelés)-ε_{1}-el

– Ha (u, v) ∈ A_{2}, akkor ε_{2} := min{ε_{21} + ε_{22}}, ahol ε_{21} := max{δ_{2} : y_{2} + δ_{2}(−u + v) ∈ B(b_{2})}, ε_{22} := y_{1}(u) − y_{2}(u), és y_{2} := y_{2} + ε_{2}(+u − v)! (növelés,csökkentés)-ε_{2}-vel ♣

Alkalmas Iterálási Szabályok

5.1. Szabály (maximális választás). Az általános lépésben a max{ h(u) : u y-aktív } < n program megoldásával dolgozzunk! ♣

Definíció A művelet elvégzése során választott u pontot kiválasztott pontnak, a benne kezdődő kiválasztott segédél v végpontját kiszemelt pontnak nevezzük. ♣

Definíció Azonosítsuk S-et az {1, .., n} halmazzal egy π : S → {1, .., n} leképezés segítségével! Minden s ∈ S pontra jelöljünk ki egy τ(s) ∈ S pontot, amely kezdetben legyen egyenlő 1-gyel! τ(s)-et az s ponthoz tartozó futó pontnak nevezzük, ha s = u, tehát abban az esetben, ha s a kiválasztott, akkor kurrensnek is mondjuk. ♣

Definíció Ha az (u, v) élen végzett művelet hatására u elveszíti aktivitását, a műveletet megszakításnak nevezzük, különben pedig telítésnek. ♣ 5.2. Szabály (körbejárás). Az (u = s) kiválasztás után addig maradjunk s-sel, amíg megszakítást nem hajtunk végre valamelyik (u, v) élen. A v kiszemelt pont legyen mindig a kurrens τ(u) pont, ezt úgy értve, hogy τ(u)-t a rögzített π azonosítás szerint futtassuk körbe S pontjain, minden kiszemelés előtt egyet léptetve rajta. (τ(u) = n esetén τ(u) = 1-re léptetés következik.) Ha megszakítást hajtunk végre az (u = s, τ(u) = t) segédélen. akkor következő alkalommal , azaz ha majd újra u = s, ezen t pont kiszemelésével folytatjuk majd az S alaphalmaz s pont körüli körbejárását.(Egy s-körüli körbejárás τ(u) = 1-gyel kezdődik, és akkor végződik, ha τ(u) = 1 újra teljesül; ezen kívül csak azok az műveleti lépések tartoznak hozzá, amelyek során u = s a kiválasztott pont.) ♣ ♣

5.6. Lemma (új élek). Tegyük fel, hogy az (s, t) él egy új éle az y-segédgráfnak a művelet elvégzése után! Ekkor (u, t), (s, v) ∈ A_{y}, vagy ha nem, akkor u = t és (s, v) ∈ A_{y}, vagy (u, t) ∈ A_{y} és v = s, vagy u = t és v = s a művelet elvégzése előtt. (u a kiválasztott, v a kiszemelt pont.)

Bizonyítás Vesszővel jelöljük a művelet utáni állapotot! Tegyük fel, hogy (s, t) ∈ A1^{′}! Az állítás ekkor azzal ekvivalens, hogy u ∈ P_{1}(t), és s ∈ P_{1}(v). P1^{′}(t) nem része P_{1}(t)-nek, mivel s ∈ P1^{′}(t)\P_{1}(t), tehát y(P_{1}(t)) lecsökken a művelet hatására, ami csak u ∈ P_{1}(t) esetén lehetséges. Ha s ∉ P_{1}(v) volna, akkor s ∉ Z := P_{1}(v) ⋃ P_{1}(t), node y1^{′}(Z) = y_{1}(Z) = b_{1}(Z), tehát P1^{′}(t) ⊆ Z, speciálisan s ∉ P_{1}′(t), ellentétben feltevésünkkel. Az (s, t) ∈ A2^{′} eset analóg bizonyítható. ♣

5.7. Lemma (illesztés). Tegyük fel, hogy (s, t) az y segédgráf egy új éle. Ekkor h(s) ≤ h(t) + 1.

Bizonyítás Új élek csak az előző lemma által leírt szigorú szükséges feltételek mellett kerülhetnek be a segédgráfba. Ez alapján

h(s) ≤ h(v) + 1 = h(u) ≤ h(t) + 1. ♣

5.8. Lemma (megengedettség). Lokális műveletünk fenntartja az (y, h) pár illeszkedését, és az y_{1} ∈ B(b_{1}), illetve az y_{2} ∈ B(b_{2}) relációt.

Bizonyítás Világos, hogy [y_{1} +δ_{1}(−u+v)](S) = b_{1}(S), és [y_{2} +δ_{2}(u−v)](S) = b_{2}(S), és δ-t úgy választjuk, hogy y_{1} ∈ S(b_{1}) és y_{2} ∈ S(b_{2}) fennmaradjon. Tehát y végig két bázisból áll.

Az y-normalitást vagy úgy ronthatjuk el, hogy a 0-szint felett keletkezik egy y-passzív pont, vagy úgy, hogy megemeljük egy y-passzív pont szintjét. Mivel ε-t úgy választjuk meg, hogy se emelésnél, se csökkentésnél ne keletkezzék ypasszív pont, és kizárólag csak y-aktív pont szintjét emeljük meg, nem tudjuk elrontani az y-normalitást.

Az y-illeszkedést csak úgy ronthatjuk el, ha megemeljük eggyel egy pontos segédél, azaz olyan (u, v) ∈ A_{y} pár u talpának a h(u) szintjét, melyre h(u) = h(v) + 1, vagy ha valamelyik bázison végrehajtott változtatással behozunk a segédgráfba egy olyan új (u, v) ∈ S^{2} párt, mely a csere előtt még nem segédél, de utána az, és h(u) > h(v) + 1 teljesül rá.

Az első eset kizárt, hiszen csak olyan u pont szintjét emeljük, melyre nem illeszkedik pontos él.

A második eset is kizárt, hiszen illeszkedési lemmánk szerint egy h-illeszkedő bázisból h-illeszkedő bázishoz jutunk, műveletünk alkalmazása során. Tehát az y-illeszkedést sem tudjuk elrontani. ♣

5.9. Lemma (körbejárás). Lokális műveletünk nem hoz be olyan (s, t) párt a segédgráfba, melyre t < τ(s) és h(s) = h(t) + 1 egyszerre teljesülne. (a < reláció az alaphalmaz számokkal való azonosítása révén értelmes)

Bizonyítás Tegyük fel, hogy mégis, és legyen (s, t) az első ilyen sértő pár. h(s) = h(t) + 1 csak úgy fordulhat elő, ha (u, t), (s, v) ∈ A_{y}, az új élekről szóló lemma alapján. (u a kiválasztott, v = τ(u) a kiszemelt pont). Ilyenkor h(s) = h(u) és h(t) = h(v). Az (u, t) él miatt nem lehet t < v, hiszen (s, t) az első sértő pár. Az (s, v) él miatt pedig t ≥ v nem lehet, hiszen ekkor τ(s) < v, és akkor (s, t) nem sértene. Tehát e két él miatt nem keletkezhet sértő pár. ♣

5.10. Lemma (komplexitás). A körbejárás és maximális választás szabállyal módosított polimatroid metszet algoritmus legfeljebb O(n^{3}) lokális műveletet hajt végre.

Bizonyítás

0 ≤ h(u) ≤ n, mert csak az n-edik szint alatti aktív pontok szintjét emelhetjük meg. h(u) egyik lépésben sem csökken. Tehát legfeljebb n^{2} szintemelést hajtunk végre.

Tegyük fel, hogy egy s ∈ S ponton megszakítást hajtunk végre. Ekkor s inaktívvá válik. Ahhoz, hogy újra elkezdhessük s-et körbejárni, és egy új megszakítást hajthassunk végre rajta, először újra aktívvá kell tenni. Ehhez azonban kellene hogy legyen egy s szintje feletti aktív pont. A maximális választás miatt ilyen pont nem létezik, tehát először meg kell majd emelnünk egy másik pont szintjét. Így s-en legfeljebb O(n^{2}), összesen pedig legfeljebb O(n^{3}) megszakítást tudunk csak végrehajtani.

Tegyük fel, hogy egy s ∈ S pontra illeszkedő élen telítünk! Ekkor legfeljebb n ilyen telítés után befejeződik s egy körbejárása, és megemeljük s szintjét. Tehát s-en legfeljebb O(n^{2}), összesen pedig legfeljebb O(n^{3}) telítést tudunk csak végrehajtani. • Mindent összevetve, durván n^{3} lépés alatt, egy min_{X⊆S}{ b_{1}(S − X) + b_{2}(X) }- elemszámú, közös független halmazt konstruáltunk. ♣

Megjegyzés Bajt okoz, hogy nem világos, hogyan kell kiszámítani az ε_{11} = ε_{11}(y_{1}, u, v), illetve az ε_{21} = ε_{21}(y_{2}, u, v) értékeket. Mindenesetre világos, hogy az y_{1} pontnak az S(b_{1}) szubmoduláris poliéderben való bentmaradását egyetlen típusú ok gátolja, miközben az y_{1} + δ_{1}(−u + v) vektorban δ_{1} → ∞, mégpedig az, hogy fenn kell tartani minden u ∉ X ∋ v-re az y_{1}(X) ≤ b_{1}(X) egyenlőtlenséget. Magyarán,

max{δ_{1} : y_{1} + δ_{1}(−u + v) ∈ B(b_{1})} = min{b_{1}(X) − y_{1}(X) : u ∉ X ∋ v}.

Világos, hogy ez az érték éppen akkor pozitív, ha u ∈ P_{1}(v), különben pedig 0-val egyenlő. Vegyük észre, hogy a jobb oldalon tulajdonképpen a b(Y) := b_{1}(Y + v) − y_{1}(Y + v) szubmoduláris függvényt kell minimalizálni az Y = X − v ⊆ S − u − v feltétel mellett, tehát az S − u − v részhalmazain. Hogy egy ilyen minimalizálást miként hajtsunk végre, azt a következő fejezetben fogjuk tárgyalni. Mindenesetre megállapíthatjuk, hogy egy minimalizáló orákulum megléte esetén megoldottuk a polimatroid metszet feladatot, hiszen ε_{21} kiszámításáról egy analóg minimax tétel mondható:

max{δ_{2} : y_{2} + δ_{2}(+u − v) ∈ B(b_{2})} = min{b_{2}(X) − y_{2}(X) : v ∉ X ∋ u}. ♣

5.4. Egy lokálisan javító algoritmikus séma

Definíció Legyen S egy n-elemű alaphalmaz! Legyen ezenfelül y egy tetszőleges eleme egy rögzített B halmaznak! y-t paraméternek, B-t paramétertérnek nevezzük. ♣

Megjegyzés y-t néha nem tekintjük fixnek, ilyenkor inkább változónak nevezzük, B-t pedig értelmezési tartománynak. y nem fogja szabadon változtatni az értékét, ez az algoritmus „eddigi lépéseinek ” a függvénye lesz.♣

Definíció Tegyük fel, hogy minden y paraméterhez létezik S-nek egy három tagú F_{y} = {S_{1}(y), S_{2}(y), S_{3}(y)} partíciója, tehát S = S_{1}(y) ⋃^{∗} S_{2}(y) ⋃^{∗} S_{3}(y)! (Megengedjük, hogy némely tagok üresek is lehetnek). S_{1}(y) egy elemét yaktívnak, S_{2}(y) egy elemét y-semlegesnek, S_{3}(y) egy elemét y-passzívnak nevezzük. ♣

Definíció Tegyük fel, hogy minden y paraméterhez adott egy A_{y} ⊆ S^{2} irányított élekből álló halmaz! A_{y} elemeit y-segédéleknek, az általuk alkotott D_{y} = (S, A_{y}) irányított gráfot pedig y-segédgráfnak nevezzük. ♣

Definíció Legyen y paraméter, és h : S → ℕ az alaphalmaz szintezése! Legyen K ≥ n egy adott korlát! Tegyük fel, hogy

• h(u) ≤ K,

• u ∈ S_{3}(y) ⟹ h(u) = 0,

• (u, v) ∈ A_{y} ⟹ h(u) ≤ h(v) + 1.

Ilyen esetben az (y, h) párt illeszkedőnek mondjuk. Az első pont h korlátosságát fejezi ki. A második pontra y-normáltságként, a harmadikra a h szintezés y-illeszkedéseként fogunk hivatkozni. ♣

Definíció Legyen P : S^{2} × B → B leképezés! Tehát minden (u, v) ∈ S^{2} párra adott B-nek egy önmagába képező P_{uv} : B → B transzformációja. y′ := P_{uv}(y). u a kiválasztott, v a kiszemelt pont. Tegyük fel, hogy

1. y′ ≠ y ⟹ u ∈ S_{1}(y) és (u, v) ∈ A_{y} (csak aktívra illeszkedő segédélen végzünk műveletet), 2. u ∉ S_{1}(y)′ vagy (u, v) ∉ A_{y′} (inaktivizáló vagy telítő),

3. s ∈ S_{1}(y′)\S_{1}(y) ⟹ s = v (új aktív csak a kiszemelt v lehet),

4. S_{3}(y′)\S_{3}(y) = ∅ (új passzív nem keletkezik),

5. (s, t) ∈ A_{y′}\A_{y} ⟹ [(u, t), (s, v), (u, v) ∈ A_{y}] vagy [u = t; (s, v), (u, v) ∈ A_{y}] vagy [s = v; (u, t), (u, v) ∈ A_{y}] vagy [u = t, s = v; (u, v) ∈ A_{y}] (az új segédélek speciálisan helyezkednek el ).

Ha P kielégíti ezen öt tulajdonság mindegyikét, akkor helyi javító műveletnek nevezzük. ♣

Probléma Tegyük fel, hogy az (D_{y}, F_{y})_{y∈B} rendszerhez megadható egy helyi javító művelet! Létezik-e olyan y paraméter, melyhez létezik egy olyan h szintezés, melyre az (y, h) pár illeszkedő, és minden y-aktív pont a K-adik szinten van? ♠

A problémára igenlő válasz adható.

5.2. Algoritmus (lokálisan javító algoritmus séma).

• input: (D_{y}, F_{y})_{y∈B}

• output: (y, h) illeszkedő pár, hogy minden u ∈ S y-aktív pontra, h(u) = K.

• inicializálás: h ≡ 0, y ∈ B

• általános lépés: Vegyünk egy y-aktív u ∈ S pontot, melyre h(u) < K ! Hajtsuk végre rajta a lokális műveletet! Ezt alkalmasan iteráljuk!

• terminálás: Minden y-aktív pont a K-adik szinten van.(Esetleg nincs is y-aktív pont.) ♣

5.2. Lokális művelet (séma). Legyen (y, h) illeszkedő pár! Legyen u ∈ S, y-aktív pont, h(u) < K!

• Nincs olyan (u, v) ∈ A_{y}, melyre h(u) = h(v) + 1 ↦ Emeljünk!:

– h(u) := h(u) + 1!

• Van olyan (u, v) ∈ A_{y}, melyre h(u) = h(v) + 1 ↦ Helyileg javítsunk !:

– y := P_{uv}(y)!

Alkalmas Iterálási Szabályok

5.3. Szabály (maximális választás). Az általános lépésben a max{ h(u) : u y-aktív } < K program megoldásával dolgozzunk! ♣

Definíció A művelet elvégzése során választott u pontot kiválasztott pontnak, a benne kezdődő kiválasztott segédél v végpontját kiszemelt pontnak nevezzük. ♣

Definíció Azonosítsuk S-et az {1, .., n} halmazzal egy π : S → {1, .., n} leképezés segítségével! Minden s ∈ S pontra jelöljünk ki egy τ(s) ∈ S pontot, amely kezdetben legyen egyenlő 1-gyel! τ(s)-et az s ponthoz tartozó futó pontnak nevezzük; ha s = u, tehát abban az esetben ha s a kiválasztott, kurrensnek is mondjuk. ♣

Definíció Ha az (u, v) élen végzett művelet hatására u elveszíti aktivitását, a műveletet megszakításnak vagy inaktivizálásnak nevezzük, különben pedig telítésnek. ♣

5.4. Szabály (körbejárás). Az (u = s) kiválasztás után addig maradjunk s-sel, amíg megszakítást nem hajtunk végre valamelyik (u, v) élen! A v kiszemelt pont legyen mindig a kurrens τ(u) pont, ezt úgy értve, hogy τ(u)-t a rögzített π azonosítás szerint futtassuk körbe S pontjain, minden kiszemelés előtt egyet léptetve rajta! (τ(u) = n esetén τ(u) = 1-re léptetés következik.) Ha megszakítást hajtunk végre az (u = s, τ(u) = t) segédélen. akkor következő alkalommal , azaz ha majd újra u = s, ezen t pont kiszemelésével folytatjuk majd az S alaphalmaz s pont körüli körbejárását.(Egy s-körüli körbejárás τ(u) = 1-gyel kezdődik, és akkor végződik, ha τ(u) = 1 újra teljesül; ezen kívül csak azok az műveleti lépések tartoznak hozzá, amelyek során u = s a kiválasztott pont.) ♣ ♣

5.11. Lemma (illesztés). Tegyük fel, hogy (s, t) az y-segédgráf egy új éle. Ekkor h(s) ≤ h(t) + 1.

Bizonyítás Új élek csak az ötödik tulajdonság által leírt szigorú szükséges feltételek mellett kerülhetnek be a segédgráfba. Ez alapján

h(s) ≤ h(v) + 1 = h(u) ≤ h(t) + 1. ♣

5.12. Lemma (megengedettség). Lokális műveletünk fenntartja az (y, h) pár illeszkedését.

Bizonyítás Az y-normalitást vagy úgy ronthatjuk el, hogy a 0-szint felett keletkezik egy y-passzív pont, vagy úgy, hogy megemeljük egy y-passzív pont szintjét. A negyedik tulajdonság miatt nem keletkezik y-passzív pont és kizárólag csak y-aktív pont szintjét emeljük meg, tehát nem tudjuk elrontani az y-normalitást.

Az y-illeszkedést csak úgy ronthatjuk el, ha megemeljük eggyel egy pontos segédél, azaz olyan (u, v) ∈ A_{y} pár u talpának a h(u) szintjét, melyre h(u) = h(v) + 1, vagy ha valamelyik bázison végrehajtott változtatással behozunk a segédgráfba egy olyan új (u, v) ∈ S^{2} párt, mely a csere előtt még nem segédél, de utána az, és h(u) > h(v) + 1 teljesül rá.

Az első eset kizárt, hiszen csak olyan u pont szintjét emeljük, melyre nem illeszkedik pontos él.

A második eset is kizárt, hiszen illeszkedési lemmánk szerint egy h-illeszkedő paraméterből h-illeszkedő paraméterhez jutunk, helyi javító műveletünk alkalmazása során. Tehát az y-illeszkedést sem tudjuk elrontani. ♣

5.13. Lemma (körbejárás). Lokális műveletünk nem hoz be olyan (s, t) párt a segédgráfba, melyre t < τ(s) és h(s) = h(t) + 1 egyszerre teljesülne. (a < reláció az alaphalmaz számokkal való azonosítása révén értelmes)

Bizonyítás Tegyük fel, hogy mégis, és legyen (s, t) az első ilyen sértő pár! h(s) = h(t) + 1 csak úgy fordulhat elő, ha (u, t), (s, v) ∈ A_{y}, az ötödik tulajdonság alapján. (u a kiválasztott, v = τ(u) a kiszemelt pont). Ilyenkor h(s) = h(u) és h(t) = h(v). Az (u, t) él miatt nem lehet t < v, hiszen (s, t) az első sértő pár. Az (s, v) él miatt pedig t ≥ v nem lehet, hiszen ekkor τ(s) < v, és akkor (s, t) nem sértene. Tehát e két él miatt nem keletkezhet sértő pár. ♣

5.14. Lemma (komplexitás). A körbejárás és maximális választás szabállyal módosított lokálisan javító algoritmus séma legfeljebb O(n^{2}K) lokális műveletet hajt végre. Speciálisan, K = O(n) esetén köbös a lépésszám.

Bizonyítás

0 ≤ h(u) ≤ K, mert csak a K-adik szint alatti aktív pontok szintjét emelhetjük meg. h(u) egyik lépésben sem csökken. Tehát legfeljebb nK szintemelést hajtunk végre.

Tegyük fel, hogy egy s ∈ S ponton megszakítást hajtunk végre! Ekkor s inaktívvá válik. Ahhoz, hogy újra elkezdhessük s-et körbejárni, és egy új megszakítást hajthassunk végre rajta, először újra aktívvá kell tenni. Ehhez azonban kellene hogy legyen egy s szintje feletti aktív pont. A maximális választás és a harmadik tulajdonság miatt, ilyen pont nem létezik, tehát először meg kell majd emelnünk egy másik pont szintjét. Így s-en legfeljebb O(nK), összesen pedig legfeljebb O(n^{2}K) megszakítást tudunk csak végrehajtani.

Tegyük fel, hogy egy s ∈ S pontra illeszkedő élen telítünk! Ekkor a 2-es tulajdonság és a körbejárási lemma miatt, legfeljebb n ilyen telítés után befejeződik s egy körbejárása, és megemeljük s szintjét. Tehát s-en legfeljebb O(n^{2}), összesen pedig legfeljebb O(n^{3}) telítést tudunk csak végrehajtani. ♣

Mindent összevetve, durván n^{2}K lépés alatt megtaláljuk a keresett (y, h) párt.

5.5. Szubmoduláris függvény minimalizálás

Probléma Legyen b : 2^{S} → ℝ szubmoduláris függvény az S alaphalmazon! Legyen X ⊆ S tetszőleges halmaz, a b(X) értéket az X halmaz szubmoduláris rangjának nevezzük. Keressünk egy minimális rangú X ⊆ S halmazt! Más szóval oldjuk meg a

min{b(X) : X ⊆ S}

programot! ♠

Az előző fejezetben kidolgozott modellre fogjuk visszavezetni feladatunkat. Ehhez definiálnunk kell az alaphalmazt, a B paraméterteret, az y paraméterhez tartozó F_{y} partíciót, és D_{y} segédgráfot. Ezenkívül kell mutatnunk egy P helyi javító műveletet ehhez a (D_{y}, F_{y})_{y∈B} rendszerhez, majd a séma által kiszámított speciális (y, h) illeszkedő párból meg kell konstruálnunk a problémánk egy X megoldását. K := n. Az alaphalmaz természetesen S lesz.

Definíció S_{n}-el jelöljük S összes < lineáris rendezéseinek a halmazát. I a továbbiakban mindig egy legfeljebb n-elemű indexhalmazt jelöl. ♣

Megjegyzés I-t S_{n} részhalmazának tekintjük majd, tehát egy i ∈ I indexet azonosíthatunk egy <_{i} lineáris rendezéssel. ♣

Definíció

• B := {y = ∑_{i∈I} λ_{i}y_{i} : y_{i} = mohó(i) ∈ ext(B(b)), ∑ λ_{i} = 1, λ_{i} ≥ 0}

• S_{1}(y) := {s ∈ S : y(s) > 0}, S_{3}(y) := {s ∈ S : y(s) < 0}

• A_{y} := {(s, t) ∈ S^{2} : ∃i ∈ I, (s, t]_{i} > 0} ♣

Megjegyzés A b-re vonatkozó mohó algoritmus alapján úgy is tekinthetünk a fenti B paraméterterünkre, hogy egy eleme a B(b) bázispoliéder y_{i} csúcsainak egy legfeljebb n elemű I részhalmazára koncentrált λ eloszlás. Ennek a várható értéke y, és egy y_{i} csúcs, az i lineáris rendezés formájában áll a rendelkezésünkre. ♣ 5.15. Lemma (megoldás). Legyen (y, h) illeszkedő pár! Tegyük fel, hogy S_{1}(y) minden eleme az n-edik szinten van! Ekkor készen vagyunk, tehát konstruálható egy minimális rangú X ⊆ S halmaz.

Bizonyítás Ha nincs S_{1}(y)-beli elem, akkor készen vagyunk. Valóban, b(S) = y(S) ≤ y(Y) ≤ b(Y), ahol Y ⊆ S egy tetszőleges halmaz, tehát S minimalizálja a b szubmoduláris függvényt.

Ha van S_{1}(y)-beli elem, akkor létezik egy k üres szint, melyre 0 < k < n. Legyen X a k-nál kisebb szintű elemek halmaza!

• X-ben nincs S_{1}(y)-beli pont,

• X-ben van minden S_{3}(y)-beli pont,

• nincs S − X-ből X-be lépő segédél.

X utolsó tulajdonsága azt jelenti, hogy X = ⋃_{t∈X}[0, t]_{i}, tehát X y_{i}-pontos, vagyis y feszíti X-et. Tehát készen vagyunk, ugyanis b(X) = y(X) = y^{−}(S), ahol y^{−} = y ⋀ 0. Más halmazra pedig b(Y) ≥ y(Y) ≥ y^{−}(S). ♣

Definíció Legyen y_{<} ∈ ext(B(b)) a < lineáris rendezésből a mohó algoritmus által generált extrém bázis! Legyen továbbá u, v ∈ S^{2} két elem, és t ∈ S melyre u < t ≤ v! Tegyük a t elemet közvetlenül u elé! Ezzel egy új <_{t} lineáris rendezéshez jutottunk. Az általa generált y_{t} extrém bázist y egy (u,v)- mutációjának nevezzük. Ezen mutációk |(u, v]_{<}|-elemű halmazát M_{y}(u, v]-vel jelöljük. ♣

5.16. Tétel (Schrijver, intervallum redukálás). Legyen y_{<} ∈ ext(B(b)) a mohó algoritmus által generált extrém bázis! Legyen továbbá (u, v) ∈ S^{2} pár, melyre u < v. Ekkor létezik egy y_{uv} ∈ conv(ext(B(b))) vektor, melyre

• y_{uv} = ∑_{t=u+1}^{v} λ_{t}y_{t}, ahol (λ_{t})_{t=u+1}^{v} konvex kombinációs együtthatók, és y_{t} ∈ M_{y}(u, v], (u, v)-mutációja az y extrém bázisnak,

• létezik egy δ_{uv} ≥ 0 szám, melyre y_{uv} = y + δ_{uv}(−u + v),

• y_{uv} kiszámítható O(n^{2}γ) időben, ahol γ a b szubmoduláris függvény kiértékeléséhez szükséges idő.

5.17. Következmény. Definiálható egy P helyi javító művelet a (D_{y}, F_{y})_{y∈B} rendszerhez.

Bizonyítás [köv.] Legyen y = ∑_{i∈I} λ_{i}y_{i} ∈ B, u ∈ S_{1}(y) és (u, v) ∈ A_{y}! Egy eljárást fogunk megkonstruálni, ami egy olyan P_{uv}(y) := y′ ∈ B vektort eredményez legfeljebb O(n^{2}) lépésben , amely kielégíti a P -től megkövetelt öt tulajdonságot.

Az eljárás egy lépése előtti paramétert y-nal, a lépés után nyert paramétert y′-vel fogjuk jelölni, csakúgy mint az egész eljárás kezdetén és végén meglévő paramétereket. (Ez nem okozhat zavart, hiszen pontosan ez az a két paraméter, mely paramétereket nem lehet egyszer y-ként máskor y′-ként felfogni. Ugyanez érvényes az összes többi fenntartott objektumra is.)

• leállás: Ha (u, v) ∉ A_{y}, azaz nem létezik olyan i ∈ I index, melyre |(u, v]_{i}| > 0, akkor álljunk le!

• általános lépés: Különben válasszunk egy ilyen i indexet! Vagyis, u <_{i} v. Az intervallum redukáló eljárásunk nyomán, y_{uv}^{i}-t felbonthatjuk O(n^{2}γ) időben az y paraméter l darab y_{j}^{i} (u, v)-mutációjának λ_{j}^{i} súlyokkal képzett konvex kombinációjára (1 ≤ j ≤ l). Cseréljük ki y felbontásában a λ_{i}-vel súlyozott y_{i} extrém bázist ezekre a λ_{j}^{i}λ_{i} együtthatókkal súlyozott y_{j}^{i} extrém bázisokra, és az így nyert új konvex kombináció legyen az új y′ paraméter! A tételből azt is leolvashatjuk, hogy y′ = y + λ_{i}δ_{uv}^{i}(−u + v), tehát y-ból λ_{i}δ_{uv}^{i}\sqrt{2} egységet léptünk −u + v irányában. Képletben,

y′ := y+λ_{i}(−y_{i}+y_{uv}^{i}) = ∑_{j∈I} λ_{j}y_{j} −λ_{i}y_{i}+∑_{j=1}^{l}(λ_{j}^{i}λ_{i})y_{j}^{i} = y+λ_{i}δ_{uv}^{i}(−u+v).

• megszakítások

– Ha az eljárás valamelyik lépésében |I′| > n, akkor y′ konvex kombinációs felbontását csökkentsük le a Carathéodory-tétel alkalmazásával, egy legfeljebb n eredeti tagból álló felbontásra! Ez O(n^{3}) időben megtehető, mint ismeretes, és folytassuk az eljárást!

– Ha az eljárás valamelyik lépésében u ∉ S_{1}(y′)-re jutunk, tehát y′(u) ≤ 0. Ekkor létezik egyértelműen egy 0 ≤ ν < 1 szám, melyre νy(u) + (1 − ν)y′(u) = 0. Ilyenkor y′ helyett vegyük νy + (1 − ν)y′-t az új paraméternek, és álljunk meg!

• választási szabály: Az általános lépésben válasszuk a max_{i∈I}|(u, v]_{i}| program egy megoldását! ♣

Meg kell vizsgálnunk eljárásunk komplexitását! A választási szabály miatt minden redukálásnál vagy a max_{i∈I}|(u, v]_{i}|, vagy az |{i ∈ I : i = max_{j∈I}|(u, v]_{j}}| kísérő paraméter értéke csökken. Így legfeljebb O(n^{2}) redukálást végzünk, hiszen bármely 0 ≤ k ≤ n érték is a maximum, ez legfeljebb n indexen realizálódhat, mert a Carathéodory tétel alkalmazása miatt, |I| ≤ n teljesül az eljárás alatt. Tehát legfeljebb O(n^{4}γ + n^{5}) idő alatt számítjuk az átmenetet. Valóban, egy redukálást és egy esetleges Carathéodory tételt, O(n^{2}γ + n^{3}) időben tudunk lebonyolítani.

Világos, hogy y′ ∈ B, és P első négy tulajdonsága is nyilvánvalóan teljesül, hiszen így alkottuk meg az eljárásunkat.

Az ötödik tulajdonság belátásához tegyük fel, hogy (s, t) egy új y′-segédél, és az y_{i}-segédgráf (u, v) éle mentén redukáltunk! Ekkor világos, hogy u ≤_{i} t <_{i} s ≤ v az intervallumredukálás előtt, és s <_{i} u ≤_{i} t <_{i} v a redukálás után, hiszen szükségképpen s-et helyeztük u elé, és t-nek valahol az [u, s)_{i} intervallumban kellett elhelyezkednie. Két azonosodás lehetséges a = d vagy b = c. Attól függően, hogy mely azonosodások teljesülnek, kapunk négy esetet. Például, ha egyik azonosodás sem teljesül, tehát a ≠ d és c ≠ b, akkor redukálás előtt (u, t),(u, v) és (s, v)) is y_{i}-segédél, tehát élei a redukálás előtti ysegédgráfnak is. Világos, hogy ez az eljárás kezdetén meglévő y-segédgráfra is igaz, hiszen az erre vonatkozó valamely (u, v]_{i} intervallumból, bizonyos elemek kiszórásával jutottunk a tekintett redukálásunk előtti (u, v]_{i} intervallumhoz. ♣

Bizonyítás [tétel] Az (S, <) lineárisan rendezett halmazt azonosíthatjuk az 1-től n-ig terjedő természetes számok rendezett halmazával. Vezessük be a

T := (u, t]_{<}
U := {e ∈ T × S : e = (t, s), t ∈ T, s = u}
D := {e ∈ T × S : e = (t, s), t ∈ T, s = t}
A := {e ∈ T × S : e = (t, s), t ∈ T, u + 1 ≤ s ≤ t − 1}

jelöléseket. Legyen a : T × S → ℝ olyan mátrix, melyre

• e ∈ U ⋃ A ⟹ a(e) ≤ 0, • e ∈ D ⟹ a(e) ≥ 0,

• e ∈ (T × S) − (U ⋃ A) − D ⟹ a(e) = 0,

• minden t ∈ T -re ∑_{s∈S} a_{ts} = 0.

Az a mátrix sorait jelöljök z_{1},...,z_{l}-lel.

5.18. Lemma. Létezik egy olyan δ ≥ 0 szám, melyre δ(−u+v) ∈ conv(z_{1}, .., z_{l}), és a konstruált előállítás nem triviális, azaz van benne nemnulla konvex együttható is.

Bizonyítás Ha létezik olyan e ∈ D diagonális elem, melyre a(e) = 0, akkor a eltűnik e sorának többi elemén is, hiszen azokon nempozitív, és a sorösszeg zérus. Tehát ilyenkor vehetjük δ-t nullának.

Ellenkező esetben először határozzunk meg olyan (ϑ_{t} ≥ 0)_{t=1}^{l} nemnegatív számokat, melyekre

(−u + v)(s) = (∑_{t=1}^{l} ϑ_{j}z_{t})(s), ha v ≥ s ≥ u + 1.

Ezt mohón megtehetjük az a-ra vonatkozó előjelszabályok alapján s magasabb értékei felől haladva. Mivel minden sorösszeg zérus, a fenti egyenlőség s = u esetén is érvényes lesz, tehát a két vektor egyenlő. Osszuk le az egyenletet ∑_{t=1}^{l} ϑ_{t} ≠ 0-val. Kapjuk, hogy δ := \frac{1}{∑_{t=1}^{l} ϑ_{t}} választás kielégíti a lemma kívánalmait. ♣

Megmutatjuk, hogyha az a mátrix z_{t} sorát y_{t} − y-nak definiáljuk, akkor teljesül az a-tól megkövetelt négy tulajdonság. A lemma alapján, ezzel az O(n^{2}γ) futásidővel is készen leszünk, hiszen világos, hogy bár az együtthatók kiszámítása O(n^{2}) időben megy, azonban minden mátrixelem kiszámításához ki kell értékelnünk még a b szubmoduláris függvényt is. Azt kell tehát belátni, hogy minden t ∈ T -re,

y_{t}(s) ≤ y(s) ha u ≤ s < t,
y_{t}(s) ≥ y(s) ha s = t,
y_{t}(s) = y(s) egyébként,

mivel a sorösszeg eltűnése triviális, bázisokról lévén szó. Mindkét oldal b(X +s)−b(X) alakú. Ez a szubmodularitás miatt X-nek csökkenő függvénye, midőn X ⊆ S − s. Tegyük fel, hogy y_{t}(s) = b(X + s) − b(X) és y(s) = b(Y + s) − b(Y). Ekkor könnyen ellenőrízhető, hogy X ⊆ Y, Y ⊆ X és X = Y, attól függően, hogy u ≤ s < t, s = t, illetve s < u vagy s > t. Tehát az y extrém bázis (u, v)-mutációiból alkotott a mátrix kielégíti a kívánt tulajdonságokat. ♣

Tehát az átmenetet, azaz a kívánt tulajdonságokkal rendelkező P műveletet O(n^{4}γ + n^{5})) időben számíthatjuk. Mivel a modellünk legfeljebb O(n^{3}) alkalommal hajtja végre P -t, az eredményül kapott szubmoduláris függvényt minimalizáló algoritmus futásidejére az O(n^{7}γ + n^{8}) felső korlát adódik.

Hivatkozások

[1] W.H.Cunningham, Testing membership in matroid polyhedra, J. Combinatorial Theory B36 (1984) 161-188.

[2] W.H.Cunningham, On submodular function minimization, Combinatorica5 (1985) 185-192.

[3] R.E.Bixby, W.H.Cunningham,D.M.Topkis, The poset of a polymatroid extreme point Math.Oper.Res. 10 (1985), 367-378.

[4] S.Fujishige, X.Zhang, New Algorithms for the Intersection Problem of Submodular Systems, Japan J. Indust.Appl. Math., 9 (1992), 369-382.

[5] A.Schrijver, A Combinatorial Algorithm Minimizing Submodular Functions in Strongly Polinomial Time J.Combnatorial Theory B80 (2000), 346-355.

[6] S.Iwata, L.Fleischer, A push-relabel framework for submodular function minimization and applications to parametric optimization (2004)