Mathematics | Higher education » Miklós Zoltán - Lokálisan javító algoritmusok a kombinatorikus optimalizálásban

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 2006 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 3.1 Folyamok 3.2 Áramok 10 . 10 . 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 II 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(nm2 ), 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(n2 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 WCunningham adott szintén javító utas megoldást 1 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 így a Schrijver-algoritmus javításának tekinthet®,

mert annak O(n7 γ + n8 ), 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 2. Gráfok 2.1 Egy irányítási feladat Probléma pontjain értelmezett olyan %D (v) G = (V, E)

Tekintsünk egy tetsz®leges f : V N+ , igény-függvényt. D = (V, A) irányítása, melyben minden v ∈ V a v∈V irányításában. irányítatlan gráfot, és a pontba belép® élek számát jelöli a pontra G-nek %D (v) ≥ f (v), ahol G = (V, E) gráf D = (V, A) ♠ Könnyen látható, hogy ehhez szükséges, hogy egy érintkez® élek Mikor létezik e(X) számára fennálljon az X ⊆ V e(X) ≥ f (X) részhalmazzal egyenl®tlenség. Való- ban, e(X) ≥ X %D (x) ≥ f (X). x∈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 N+ 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) irányításból, és egy hozzá illeszked®  alapgráf egy tetsz®leges

h:V N D = (V, A) szintfüggvényb®l. Ezen azt értjük, hogy • h(u) ≤ h(v) + 1 • h(u) = 0 ∀(u, v) ∈ A ∀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 Valóban, h ≡ 0 (D, h) párt. D = (V, A) irányításhoz megadható illeszked® szintezés. megfelel® választás. Végig fenn kívánunk tartani egy ilyen Akkor vagyunk készen, ha nincs 3 %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 azaz pontos (u, v) ∈ A u∈V hiányos csúcsra illeszked®, h(u) = h(v) + 1, é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 meggyelé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 egyet, és deniáljuk pont van, és X -et, n+1 szint, létezik üres szint. Rögzítsünk 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. X -ben, és legalább egy telítetlen P x∈X %D (x) < x∈X f (x) = f (X). ♣ Ezenkívül nincs túltelített pont pont van benne. Tehát, e(X) = P 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(n2 ) szintemelést, és legfeljebb O(n3 ) é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 sosem csökken az eljárás során. Tehát legfeljebb Minden (u, v) él h({u, v}) := h(u) + h(v) n, n2 legalább 0, és ez a szint szintet emelünk meg. 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. 4 Így (u, v)-n legfeljebb végre. 2n -ször fordítunk, tehát összesen legfeljebb 2 mn élfordítást hajtunk ♣♣ Megjegyzés A

bizonyítás alapján látható egy olyan algoritmus létezése, amely durván n3 apró lépés megtétele után, egy adott az el®re megadott f :V N G = (V, E) irányítatlan gráf, 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® 5 X⊆V vágást szolgáltat. ♣ 2.2 K®nig tétele Probléma ban! Keressünk M maximális párosítást egy G = (S, T, E) páros gráf- 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ó, abból a tényb®l fakad, hogy nyilván |M | ≤ |L| L ponthalmazt keresünk. minden M Ez 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á- (H, d) lis függvényével korlátozhatóan sok lépés után szükségképp egy olyan párhoz jutunk, amelyb®l már egyszer¶en megkonstruálhatjuk feladatunk egy megoldását. Deníció Egy H⊆E pontra legfeljebb egy s∈S pontra. Deníció H -beli kor él, akkor H ⊆E él illeszkedik, más szóval, ha félpárosítás. Ha egy H -fedetlennek, H -túlfedettnek viszont Legyen ha egynél több nevezzük. Legyen (t2 , s) ∈ H . resznyének nevezzük. Deníció H -beli dH (s) ≤ 1 S -beli minden ♣ Legyen (t1 , s) ∈ / H, élhalmazt félpárosításnak nevezünk, ha minden T -beli pontra nem illeszkedik H -beli él is

illeszkedik rá, ak- t1 , t2 ∈ T Ekkor a és (t1 , s, t2 ) s ∈ S. hármast Tegyük fel, hogy H -alternáló cse- ♣ d:T N egy egész vektor. A zon meghatározott osztályozást a T d vektor által a T halma- 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. Deníció Legyen H ⊆ E félpárosítás. Egy mondunk, ha 6 ♣ d : T N szintezést H -illeszked®nek • a • minden H által fedetlen T -beli pontok a bal oldalon vannak, (t1 , s, t2 ) H -alternáló cseresznyére d(t2 ) − d(t1 ) ≤ 1. Ezt a második kritériumot úgy is kifejezhetjük, hogy nincsenek a gráfban H -alternáló rossz Az E cseresznyék. ♣ által fedetlen pontok nem játszanak szerepet a tétel állítására vonat- kozólag, ezért feltehetjük, hogy minden pont foka pozitív. Így biztosan létezik egy H

d≡0 félpárosítás, és a 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. zítsünk le egyet, és tekintsük e szintt®l jobbra lév® pontok Legyen Y := ΓH (X) ⊆ S , Nem létezik T X azaz Y és X H -szomszédainak között vezet® E -beli X ⊆T Rög- halmazát. halmaza. é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 (t1 , s) ∈ E H H -alternáló Tehát él volna, ami az egyértelm¶ cseresznyét adna L := X ∪ (S Y ) X nem tartalmaz hozzá az összes S Y -t M ⊆ H H így az S -beli félpárosítás, a szomszédja pontra

egy ®t fed® H -fedetlen fed® H -beli pontok így erre csak egy X -ben M -beli G M -beli pont az n-edik Valóban, él illeszkedik, hiszen vannak, de egy X -beli pont H- |M | = |L|. ♣ t pont az Hiszen ha egyáltalán nincs túlfedett pont, akkor M := H , L := S gráf párosítása. él illeszkedik. Az általános esetben létezik egy túlfedett s így az élt. Ez megtehet®, élt. pontokra legfeljebb egy Konstrukciónkból világos, hogy H -beli pontot. Ezekhez az élekhez még vegyük élhalmaz nyilván a H -túlfedett Y -beli, G-ben. t∈X M ⊆ E Az így kapott éllel együtt, egy rossz lefogó pontrendszer. Válasszunk ki minden hiszen (s, t2 ) ∈ M H n-edik szintt®l balra. S -et fed® párosítás, egy választással készen vagyunk. Ha minden túlfedett szinten van , akkor pedig a lemma miatt vagyunk készen. 7 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 Ilyen esetben inkább hajtsunk végre egy jünk át a H − (t, s) + (s, u) d(t) = d(u) + 1 (u, s, t)-élcserét H -n, teljesül. magyarán tér- félpárosításra. 2.6 Lemma (érvényesség) A fent deniált általános lépés meg®rzi az H illeszkedé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 cseresznye volna, akkor H -alternáló (a, b, c) = (a, s, u) nye nem keletkezhet. Mivel az H félpárosítás u pont egy rossz lenne. De akkor cseresznye volna a cserélés el®tt. pont sem, így a (a, b, c) végrehajtott cserélés után (u, s, t-kicserélése (a, s, t) nem keletkezik egy egy rossz H -alternáló Így rossz H -túlfedett, H

-alternáló d-illeszked® cseresz- H -fedetlen félpárosítást eredményez. Egyrészt az részt az u u pont pontra nem illeszkedik pontos H -túlfedett, szintezést eredményez. így a d szintezés H -alternáló u-jobbra cseresznye. más- tolása H -illeszked® ♣ Addig hajtsuk végre a fenti eljárást a kiválasztott oldalra nem rendezzük az összes H -túlfedett pontot. eljárásunk, mindig válasszuk t-t bal fel®l, azaz vegyük a t ponton, amíg jobb Hogy hatékony legyen 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(n3 ) lépés után terminál 8 Bizonyítás Mivel mindig balról választjuk t-t, legfeljebb n élcsere után, vagy csökken egyel a t-t n pontok száma, vagy ha nem, a következ® lépésben eggyel jobbra kell tolnunk. H -fedetlen van bel®le, így az els® eset legfeljebb n-nél n H -fedetlen pont nem keletkezik, és legfeljebb n-szer fordulhat el®. Nem használunk nagyobb szinteket, ezért egy pontot legfeljebb pont van, tehát a második eset legfeljebb feljebb (n + n2 )n-el n 2 n-szer tolhatunk jobbra , -szer fordulhat el®. Tehát leg- ♣ 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 párosítottuk A fenti algoritmussal igazoltuk Hall tételét is. Hiszen vagy

be- S -et T -be, félpárosításra vett Valóban, hiszen vagy létezett egy Y = ΓH (X) ⊆ S |ΓE (Y )| < |Y |, viszont van benne X⊆T halmaz, melynek a végs® H szomszédossága megsérti a Hall feltételt. amint az els® lemma bizonyításából könnyen látható, |ΓE (Y )| ≤ |ΓH (Y )| = |X| < |Y |, kilépni bel®le. ♣ H -túlfedett, és mert H -alternáló ♣ 9 X -ben nincs H -fedetlen pont, cseresznyén keresztül nem lehet 3. Hálózatok 3.1 Folyamok Legyen D = (V, A) legyen kitüntetve egy pontpár, melyre (s, t) ∈ V 2 , s 6= t, %A (s) = 0 és δA (t) = 0. mot, hálózatnak nevezzük. Egy és (hálózati)folyam, ha minden radási feltétel, %x (v) = δx (v). %x (Y ) − δx (Y ) ∈ R+ s̄t-halmazok, x folyam s azaz g : A R+ irányított gráf, élein forrásnak, illetve nyel®nek nevezett vektor megengedett, ha v ∈ V − {s, t} köztes X, Y ⊆ V , és 0 ≤ x ≤ g, pontra teljesül a megma- val(x) := δx

(X) − %x (X) = Egy folyam értéke, a s ∈ X, t ∈ / X, (D = (V, A), g) objektu- Az így nyert, x:AR szám, ahol kapacitásfüggvény, és st̄, tetsz®legesen rögzített, s∈ / Y ,t ∈ Y . X = s forrásból való teljes kiáramlása, míg Y =t val(x), esetén esetén az illetve x az folyam t nyel®be való teljes beáramlása. Ez a dení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) = X (δx (v) − %x (v)) v∈X Tehát δx − %x illetve %x (s) = 0 , a pontokon értelmezett vektor, így a megmaradási szabály, é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 deniált fogalmakkal, egy hálózati folyam konstrukcíó megalkotása után. Megjegyzés minden vezzük. Világos, hogy X st̄-halmazra. max{val(x) : x val(x) = δg (X) megengedett folyam} A jobboldali értéket az Ha tudnánk találni egy x X ≤ δg (X) vágás kapacitásának ne- folyamot és egy X st̄-vágást, melyekre teljesül, akkor ezzel igazolnánk, hogy mindig létezik a fenti, formálisan felírt maximum, azaz van maximális folyam. Valóban, folyam lenne ♣ min{δg (X) : X st̄ vágás} értékkel, az 10 X x maximális tanúsítvány szerint. Ez az út járható. Egy "megengedett el®folyam"-nak nevezett, x objektu- mot 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) • max ≥ min: A fenti egyenl®tlenségben akkor áll egyenl®ség, ha az g téke eléri a ki, hogy x Deníció hogy és kapacitást, a belép®kön pedig telíti az az X x-hez x(u, v) < g(u, v), x(u, v) = g(u, v) és Legyen illeszkedik az x Ezt úgy fejezzük tartozó segédgráf éle, azaz vagy ha (v, u) ∈ A x(v, u) = 0, x és (u, v) ∈ V 2 . (u, v) ∈ Ax , x(v, u) > 0. Ha akkor azt mondjuk, hogy akkor telít egy X Azt mondjuk, ha (u, v) ∈ A, (u, v) ∈ / Ax , x telíti az vágást, ha minden azaz (u, v) X -b®l ♣ kilép® párt telít. h(s) = n, 0 értéket vesz fel. megengedett vektor, párt. Tehát mondhatjuk, hogy azaz X -b®l kilép® éleken x ér- vágást. Adjunk példát ilyen párra! 0≤x≤g Legyen (u, v) Deníció 0≤x≤g ,mert és h : V N h(t) = 0. szintfüggvény. Tegyük fel, hogy Azt

mondjuk, hogy a h h normált, normált szintfüggvény megengedett vektorhoz, ha a segédgráf élei mentén legfeljebb egyet csökken, azaz h(u) − h(v) ≤ 1, minden (u, v) ∈ Ax é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 kisebb szint¶ pontok nincs olyan x telíti (u, v) X k szint, melyre halmaza jó lesz. Egyrészt pár, mely kilépne X -b®l, X -et. ♣ 11 0 < k < n. s∈X és A k -nál t∈ / X. nem Másrészt és a segédgráfnak éle volna. Tehát x vektor mennyire nem folyam, azt a λx (v) := %x (v) − δx (v) pon- Hogy egy tokon é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 6= 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 gyen x Legyen h(s) = n, másutt h = 0. Így h olyan megengedett el®folyamfolyam, hogy minden x(s, v) = g(s, v). Ekkor h illeszkedik x-hez. Ilyen x azokon az éleken, ahol nincs el®írva az értéke. Ekkor den normált szintezés. s-t®l különböz® pontnak nemnegatív a többlete. Tehát tudjuk az álljanak. (x, h) (s, v) ∈ A létezik. x Legyen Leélre: x = 0 megengedett, és min- ♣ párt inicializálni, hogy a kezdeti feltételek fenn- 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 deniá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 Ax 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 visszafelé haladva elérhet®k vezet® P irányított út v∈V Ax -ben. pontok halmaza, melyek s-b®l az éleken v -kb®l létezik s-be Nyilván pontosan ezen Ax -ben. v∈S (v többletes) ⇐⇒ X λx (v) = 0 v ∈S / Node, lép él 0≤ P v ∈S / λx (v) = δx (S) − %x (S) = δ0 (S) − %g (S) ≤ 0, S -be nem Ax -ben. Adjuk össze az legfeljebb hogy hiszen h(a)−h(b) szinteséseket az (a, b) ∈ P n − 1 él lehet, és Ax h(v) − h(s) ≤ n − 1. élei legfeljebb Tehát párokra. Mivel 1 szintet lépnek lefelé, azt kapjuk, h(v) = 2n − 1 = O(n). 12 P -ben (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) Ezt az élt telítjük, azaz g -re él Ax -ben, állítjuk, akkor melyre (v, u)-n (u, v) ∈ / Ax h(u) = h(v) + 1. pedig 0-ra. Ha nem okozunk ezzel újra valamilyen bajt, lesz a szaturálás után. Bajt pontosan akkor okoztunk, ha az operációnk után λx (u) el tudjuk tüntetni a negatív lett, vagyis λx (u) x már nem el®folyam. Ilyenkor többletet, azaz csak annyira emeljük n, illetve csökkentjük (v, u)-n, inkább többletes lesz, λx (v) + λx (u) λx (u) (u, v)-n x-et hogy λx (u) = 0 legyen. x-et (u, v)- Ekkor persze v még többlettel, de úgy tekinthetjük, hogy a többletet eggyel alacsonyabb szintre nyomtuk. Globálisan szemlélve, a többletet lefelé, mintegy t-be be visszajuttathassuk majd. nyomjuk, ha ez nem megy,

felemeljük, hogy s- 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 6= s, t), többletes pont • Nincs (u, v) ∈ Ax 7 Emeljük meg u szintjét! h(u) := h(u) + 1 ! • Van (u, v) ∈ Ax 7 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) 7 Telítsük az (u, v) párt! x(u, v) := g(u, v), x(v, u) := 0 ! • ε = λx (u) 7 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! 13 Vegyünk egy λx (u) > 0 többletes

pontot, u 6= s, t! Hajtsuk végre rajta a lokális m¶veletet! Ezt iteráljuk! • terminálás: Nincs többletes pont. ♣ • általános lépés: 3.7 Tétel (komplexitás) Az el®folyam algoritmus lépésszáma O(mn2 ) Szintemelést O(n2 ), telítést O(mn2 ), inaktivizálást O(mn2 ) lépésben hajtunk végre Bizonyítás 0 ≤ h(u) ≤ 2n − 1, egyik lépésben sem csökken. h(u) mert csak aktív pont szintjét emeljük. Tehát legfeljebb (n − 2)(2n − 1) szintemelést hajtunk végre. Az (u, v) ∈ Ax megváltozzon, a h(u) + 1 h(v) (v, u) élen kell telítni, vagy inaktivizálni. kell. Mivel az szintjet legalább tehát (u, v) ∈ / Ax . élen való telítés hatására (u, v) 2-vel telítésekor 0 ≤ 2(k − 1) + 1 ≤ 2n − 1.(Az k ≤ n. emelésére). Így (u, v) ∈ / A esetén Legfeljebb Ehhez viszont h(u) = h(v) + 1, megemeljük. k -szor Ha Ahhoz, hogy ez h(v) = ehhez az kell, hogy telítünk (u, v)-n, akkor utolsó, már lehet,

hogy nem vezet 2∗m darab g(u, v) = 0, (u, v) ∈ / A-ra (u, v) ∈ Ax pedig (u, v) és h(v) él van, hiszen (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 tív pontok halmaza. ∆+ − ∆− , jük ∆-val. H -t, rül ahol 0 ≤ k < ∞ hk (A) ≥ 0 H := h(A)-t Tehát ∆− ≤ ∆+ . lépést megtettünk. és kezdetben Legyen A az ak- h0 (A) = 0. hk (A) = h0 (A) + növel®, illetve csökkent® lépések számát jelölMinden inaktivizálás legalább 1-gyel csökkenti hiszen pontos él mentén történik, és a magasabb szinten lév® pont kike- A-ból. emelés Minden szintemelés , és minden telítés nem-csökkenti 1-gyel legfeljebb növel, telítés esetén pedig 2n − 1-et A vagy b®vül emelH értékén, vagy nem változik. ∆+ ≤ rk + ak (2n − 1), ahol s a telítések, r és 1 H -t. Szint-

ponttal, és akkor Tehát sk ≤ ∆− , é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, sk ≤ ∆− ≤ ∆+ ≤ (n − 2)(2n − 1) + 2mn(2n − 1). ♣ 14 3.2 Áramok Probléma A R g(e). Legyen D = (V, A) vektor megengedett, ha minden f ≤ g, Feltehetjük, hogy minden f, g : A R digráf. v∈V e ∈ A kapacitások. Egy élre fennáll, hogy x : f (e) ≤ különben nem létezik megengedett vektor. Ha pontra fennáll a megmaradási feltétel, áramnak nevezzük. Mikor létezik egy %x (v) = δx (v), akkor x-et (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) = ≤ %g (X)

− δf (X), ≥ 0. ♣ 3.9 Tétel (Homan) Vagy létezik egy x ∈ RA 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! Deníció minden az Legyen v ∈V x-többletes szintezés x ∈ RA pontra megengedett vektor, és h(v) ≤ n, és h ∈ NV %x (v) > δx (v) esetén egy szintezés. Ha h(v) = 0, tehát ha pontok a nulla szinten vannak, akkor azt mondjuk, hogy a h x-normált. ♣ Deníció Legyen x ∈ RA megengedett vektor. növelhet® x-segédél, csökkenthet® ha x-segédél. x(e) < g(e), Az ha pedig x-segédélek gráfját (u, v) ∈ A élre − e = (u, v) ← − x(e) > f (e), akkor e = (v, u) Egy Ax -el jelöljük.

♣ Dení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 h(u) ≤ h(v) + 1. ♣ 15 (u, v) ∈ Ax segédélre 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 vektorhoz illeszkedik. Létezik ilyen, például x megengedett 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 P v∈V (%x (v) Létezik k − δx (v)) = 0, üres szint, melyre pontok összessége. X segédél, így minden g(u, v), így az els® rész világos. illetve jó lesz.

Valóban, X -b®l kilép® n. h Legyen h (u, v) X egy ilyen k szint feletti illeszkedése miatt nem lép ki pár szaturált x(v, u) = f (v, u). X -ben létezik benne hiányos, hiszen az 0 < k < n. x által, azaz X -b®l x(u, v) = létezik többletes pont, viszont nem normált, és feltettük, hogy van hiányos pont szinten. Összevetve: %g (X) − δf (X) = %x (X) − δx (X) = X %x (v) − δx (v) < 0 v∈X 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) ∈ Ax 7 Emeljünk! h(u) := h(u) + 1 ! • Van (u, v) ∈ Ax 7 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) 7 Szaturáljunk! x(u, v) := g(u, v), x(v, u) := f (v, u) ! • ε = λx (u) 7 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! ♣ 16 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(n3 ) Szintemelést O(n2 ), szaturálást O(mn), inaktivizálást O(n3 ) lépésben végzünk. Bizonyítás h(u) ≤ n, n-edik Az mert csak az szint alatti, hiányos pontokat nevezzük aktívnak! n-edik szint alatti aktív pontok szintjét emeljük. egyik lépésben sem csökken. Tehát legfeljebb Az (u, v) ∈ Ax élen való szaturálás hatására megváltozzon, a (v, u) h(v) = h(u) + 1 kell. Mivel az az kell, hogy (u, v)-n, h(v) legfeljebb (u, v) ∈ / Ax . szaturálásakor 2-vel 2(k − 1) ≤ n.(Az k ≤ n2 +1. O(mn) (u, v) Legfeljebb Ahhoz, hogy ez Ehhez viszont h(u) = h(v) + 1, megemeljük. Ha k -szor ehhez szaturáltunk utolsó, már lehet, hogy nem vezet 2m darab (u, v) ∈ Ax él van. szaturálást kell elvégeznünk. 17 h(u) szintemelést hajtunk végre. élen kell szaturálni vagy inaktivizálni. szintjét legalább akkor tehát emelésére).

Így n2 0≤ h(v) Összevetve, 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 vakon maximalizáló, u összes szinthalmazt, azaz vizálunk. Legfeljebb végzünk el. h(u) pontok száma csökken, vagy csökken a érték. Tehát legrosszabb esetben végiginaktivizáljuk a 2 V pontjait. Tehát x O(n ) h-t h-ra h által, ♣ 18 a legfeljebb használunk, így legfeljebb h-t, 3 O(n ) az aktí- maximum V -n létesített n-szer inakti- inaktivizálást 4. Matroidok 4.1 Matroidokkal kapcsolatos eredmények Legyen S n egy elem¶ alaphalmaz. módon is megadhatunk. Például az Egy rM CM matroidot S -en több ekvivalens rangfüggvényével, az BM halmazainak rendszerével, a bázisainak például köreinek M FM független összességével, vagy megadhatjuk halmazrendszerével is. Algoritmikus megközelítéssel ezen azt értjük,

hogy adott egy orákulum, aminek egy tetsz®leges tér annak miszerint r(X) X M matroidot és egy X⊆S részhalmazt beadva, vissza- rangjával, vagy visszatér egy kérdésre adott helyes válasszal, 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 (S, r) r objektumot, akkor azt mondjuk, hogy megadtunk egy r matroidot. Ezt azért tehetjük meg, mert konkrétan az S N egy másik elméleten belül, 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 N függvény pontosan akkor egy M matroid rangfüggvénye, ha r(∅) = normalizált, monoton növ®, szubmoduláris és

szubkardinális, tehát ha 0; r(X) ≤ r(Y ) ha X ⊆ Y ; r(X) + r(Y ) ≥ r(X ∪ Y ) + r(X ∩ Y ); illetve r(X) ≤ |X|. Egy F ⊆ 2S halmazrendszer pontosan akkor alkotja egy getlenjeinek halmazát, ha tartalmazásra maximális X halmaztól függ. rangját. Az Egy F -beli F ⊆ X X ⊆ S halmaz részhalmazának az elemszáma csak az független halmaz feszíti az X létezik egy teljes egészében X -ben C ∈ C matroid füg- X halmaz r(X) egyenlet megoldásai pedig a függetleneket. Ennek csak az az oka, hogy egy olyan leszálló, és ha akármelyik Ez a szám adja vissza természetesen az r(F ) = |F | F ∈F ∅ ∈ F, M kör, melyre minden X⊆S F -en fekv® halmazt, ha kívüli x pontjának egyértelm¶en C(F, x) ∈ C -el C − x ⊆ F. A C |F ∩ X| = r(X). jelölt alapköre, azaz 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 19 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 matro- idszervez® 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 al- kalmasan 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 < sorbarendezéséb®l indul ki. Fenntart egy ben üres, majd a sorrend szerint végigszalad megpróbálja kib®víteni F -et S F ⊆ S S halmazt, mely kezdet- pontjain, és minden lépésben 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® Az eljárás végére alaphalmaz egy tetsz®leges F = F< ∈ B, F független halmaz rangja. F, azaz a fenntartott független az algoritmus által bizonyítottan nem b®víthet® már tovább. Egy matroidot többféleképpen is ábrázolhatunk az Például deniálhatjuk a P (r) matroid

poliédert vagy a n-dimenziós B(r) térben. bázispoliédert. P (r) := {y ∈ RS : y ≥ 0, y(X) ≤ r(X)}, B(r) := {y ∈ RS : 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ó lésben nem fogunk különbséget tenni ezek között, tehát egy X ⊆S halmaz karakterisztikus függvényét is Ugyanígy nem teszünk különbséget egy s-el, {s} ⊆ S illetve RS -ben. s∈S X -el Jelö- pont és egy jelöljük majd. szingleton és egy s∈S pont között sem. Ezek az azonosítások egyrészt megtehet®k, hiszen az azonosított 20 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. 21 4.2 Matroid partícionálási probléma Probléma Legyen k , k M = {Mi = (S, ri )}i=1 halmazon. Egy olyan roidokban független, F ⊆S darab matroid, a közös halmazt, mely lefedhet® k H = {Fi ∈ Fi }i=1 k S alap- darab, az egyes mat- halmaz uniójával, partícionálhatónak mondunk! Keressünk egy maximális elemszámú F ⊆ S, partícionálható hal- mazt. Más szóval oldjuk meg a max{|F | : F ⊆ S, és ∃ Fi ∈ Fi , melyre k [ Fi = F } i=1 programot! ♠ Fels® korlát Legyen X ⊆ S tetsz®leges halmaz. Ekkor |S − X| + k X ri (X) ≥ |F |. i=1 u.i: |F | = |F

− X| + |F T X| |F − X| ≤ |S − X| T T Pk T Sk |Fi X| Fi X| ≤ i=1 |F X| = | i=1 T |Fi X| ≤ ri (X) ♣ Könnyen látszik, hogy mikor áll egyenl®ség becsléseinkben. Optimalitási feltétel F = k • {Fi }i=1 részpartíció k • {Fi }i=1 fedi • Fi feszíti S k i=1 Fi optimális, ha: X -ben S − X -et X -et az Mi 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 22 k , k darab mat4.1 Tétel (Edmonds-Fulkerson) Legyen {Mi = (S, ri )}i=1 roid S -en. Ekkor maxFi ∈Fi { | k [ Fi | } = minX⊆S { |S − X| + i=1 Bizonyítás h:SN k H = {Bi ∈ Bi ⊆ Fi }i=1 darab H-beli v ∈ Bi Legyen pontra, ha pott élek Ai nevezzük, és ráfot, a 1≤i≤k fH (s) = 0, Bi Di = (S, Ai )-vel alapkörnek, Tehát S pontjainak egy fH (s) = l, pont. Egy illetve s∈S fH (s) > 1 irányítsunk egy e élt ha pontosan pont

fedetlen, teljesül. u∈ / Bi . v -b®l u-ba. jelöljük. A DH = (S, AH ) := (S, S tartozó segédgráfnak nevezzük. Világos, hogy egy v u Minden Az így ka- teljesül valamelyik 1≤i≤k Deníció h : S N+ indexre. k i=1 Ai ) dig- (u, v) ∈ S 2 a kitüntetett pontja valamelyik pedig egy másik pontja neki. Még másképp, Legyen ♣ bázishoz tartozó, kifelé irányított bázisgráfnak pár pontosan akkor éle a segédgráfnak, ha Ci bázist, és egy x index. Legyen továbbá v ∈ C(u, Bi ), összességét, a H-hoz s∈S bázisban van benne az illetve többszörösen fedett, ha Deníció Fenntartunk majd szintezését, melyre teljesülnek bizonyos illesztési feltételek. Deníció H rétegszámvektorát jelöljük fH -val. l ri (X) }. i=1 Lokálisan javító algoritmust szerkesztünk. minden matroidból egy olyan k X Bi + u − v ∈ Bi ♣ szintezés. Ha minden fedetlen pont a leg- alsó szinten van, és minden segédél

legfeljebb egy szintet lép lefelé, akkor normált, illetve H-illeszked® H- szintezésr®l beszélünk. Más szóval az • fH (u) = 0 =⇒ h(u) = 0 • (u, v) ∈ AH =⇒ h(u) ≤ h(v) + 1. illesztési feltételeket követeljük meg. ♣ k 4.2 Lemma (Terminálás) Legyen H = {Bi ∈ Bi ⊆ Fi }i=1 . Legyen továbbá h : S N+ 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 Sk számítható egy olyan X ⊆ S halmaz, amely kielégíti az i=1 Bi -re vonatkozó optimalitási feltételeket. 23 Bizonyítás Létezik k üres szint, melyre szint¶ pontok halmaza. X -ben nincs fedetlen pont, és nincs 0 < k ≤ n. Legyen X a nincs többszörösen fedett pont, S − X -b®l X -be lép® segédél. k -nál kisebb S − X -ben Ez azt jelenti, hogy H részpartíció X -ben, és lefedi S −X -et, valamint minden 1 ≤ i ≤ k indexre és T minden u ∈ XBi

pontra C(Bi , u) ⊆ X , azaz C(Bi , u) ⊆ Bi X + u, tehát Bi T T feszíti X -et mindegyik matroidban, vagyis r(Bi X) = |Bi 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 Mi Valóban. h≡0 k H = {Bi ∈ Bi }i=1 minden matroidban futtatott mohó algoritmus pedig egy Bi -hoz illeszkedik. Az 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 fH (u) > 1 többszörösen fedett pont, h(u) < n. • Nincs (u, v) ∈ AH , h(u) = h(v) + 1 7 Emeljünk u szintjén! h(u) := h(u) + 1 ! • Van (u, v) ∈ AH , h(u) = h(v) + 1 7 (u, v)-kicserélés! Legyen i olyan, hogy (u, v) ∈ Ai . Bi := Bi − 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 N a kifelé irányított D = (S, AB ) 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 (x, y) ∈ A2 A1 C(B1 , y) B1 = B és egy új segédél! Tehát B2 = B1 − u + v x ∈ C(B2 , y), kör nem is létezik. 24 és jelöléseket! Legyen x∈ / C(B1 , y), vagy a y ∈ B1 , Tegyük fel el®ször, hogy ez a helyzet, tehát x ∈ C(B2 , y) = C(B2 , u) = C(B1 , v), azaz y = u. Ekkor így h(x) ≤ h(v) + 1 = h(u) = h(y) < h(y) + 1. y 6= u, Másodjára vizsgáljuk azt az esetet, amikor kor létezik C(B1 , y). u ∈ C(B1 , y). Belátjuk, hogy C(B2 , y)C(B1 , y), tehát az 1 2 átmenet mentén y Tehát u ∈ C(B1 , y)

C(B1 , v), és y ∈ / C(B1 , v), y ∈ / B1 . Ek- Ez azért igaz, mert x∈ alapköre megváltozik, és ez csak úgy lehet, ha eredetileg tartalmazta a kicserélt T vagyis u pontot. mert y ∈ / B1 , és y = v y∈ / B2 , viszont v ∈ B2 . Az els® köraxióma miatt létezik egy S y ∈ C ⊆ C(B1 , y) C(B1 , v) − u kör. Világos, hogy y ∈ C ⊆ B2 + y , ezért sem lehet, hiszen C = C(B2 , y). Ezért Tehát, mivel x ∈ C(B2 , y)C(B1 , y), x ∈ C(B1 , v). 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 mentén végezzük a cserét. Tehát A H Bi − u + v ∈ Bi , mert csak segédél végig bázisokból áll. 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 A h szintezés H-normalitását. 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 kicserélést hajtottuk végre, tehát Bi0 = Bi − u + v , Ez azt jelenti, hogy h illeszkedik 4.1 Algoritmus (matroid partíció) k • input: {Mi = (S, ri )}i=1 . 25 és az bázison az 0 H -höz. ♣ (u, v)- (s, t) ∈ A0i Ai h(s) ≤ h(t) + 1, új segédél. A kicserélési lemmánk szerint ekkor

h-illeszked®. Bi tehát egy A0i is • output: k , h : S N) illeszked® pár, hogy minden v ∈ S (H = {Bi ∈ Bi }i=1 többszörösen fedett pontra, h(v) = n. k • inicializálás: Legyen h ≡ 0, H = {Bi ∈ Bi }i=1 , ahol Bi =mohó(Mi )! • általános lépés: Vegyünk egy fH (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) : fH(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(n3 ) lokális m¶veletet hajt végre Bizonyítás Legfeljebb n2 letkezik, így legfeljebb szintemelést hajtunk végre. Fedetlen pont nem ke- n-szer csökken a számuk. Az tott csere hatására vagy csökken a kiválasztott u (u, v) segédélen végrehaj- 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 vagy meg kell emelni vetve, legfeljebb 3 u n +n 2 szintjét, vagy megszüntetjük cserét hajtunk végre. Mindent összevetve: durván v n csere után fedetlenségét. Össze- ♣ P n3 lépés alatt, egy minX⊆S { |S−X|+ ki=1 ri (X) }- elemszámú, partícionálható halmazt konstruáltunk. 26 ♣ 4.3 Matroid metszet probléma Probléma Legyen 2 , M = {Mi = (S, ri )}i=1 alaphalmazon. Egy olyan két darab matroid, a közös S 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 programot! és F ∈ F1 F2 } ♠ Fels® korlát Legyen X ⊆ S tetsz®leges halmaz! Ekkor bármely F ⊆S közös független halmazra |F | ≤ r1 (S − X) + r2 (X). u.i: |F | = |F X| + |F T X| |F X| ≤ r1 (S − X) T |F X| ≤ r2 (X) ♣ Könnyen látszik, hogy mikor áll egyenl®ség becsléseinkben. Optimalitási feltétel F • F feszíti S − X -et • F feszíti X -et az optimális, ha: az M2 M1 matroidban matroidban ♣ Megmutatjuk, hogy az optimalitási feltételeket mindig ki lehet elégíteni. 2 4.7 Tétel (Edmonds) Legyen M = {Mi = (S, ri )}i=1 , két darab matroid S -en. Ekkor max{|F | : F ⊆ S és F ∈ F1 F2 } = minX⊆S { r1 (S − X) + r2 (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. 27 F -et B1 Ezért T B2 alakban keressük majd, ahol tartunk tehát mindkét matroidból egy H-hoz illesztjük még az S B1 ∈ B1 H = {Bi ∈ pontjainak egy olyan és B2 ∈ B2 . Fenn- 2 Bi }i=1 bázist. Ezenkívül h : S N szintezését is, melyre teljesülnek bizonyos feltételek. 2 . Fogalmak Legyen H = {Bi ∈ Bi }i=1 Deníció illetve Egy s∈S s ∈ B2 B1 pont teljesül. ¯ -típusú, (1, 2) illetve (2, 1̄)-típusú, ha s ∈ B1 B2 , ♣ Deníció Legyen u, v ∈ S . • Ha u∈ / B1 és v ∈ C(B1 , u), akkor irányítsunk egy e élt u-ból v -be. kapott élek A1 összességét, az S alaphalmazon értelmezett, a tartozó, befelé irányított bázisgráfnak nevezzük, és Az így B1 bázishoz D1 = (S, A1 )-gyel jelöljük. • Ha u ∈ / B2 és v ∈ C(B2 , u), Az így kapott élek B2 a S élt v -b®l u-ba. alaphalmazon

értelmezett, a S A2 ) digráfot, a H-hoz tartozó segédgráfnak, éleit, tartozó segédéleknek nevezzük. Megjegyzés D2 = jelöljük. DH = (S, AH ) := (S, A1 H-hoz összességét, az e bázishoz tartozó, kifelé irányított bázisgráfnak nevezzük, és (S, A2 )-vel A A2 akkor irányítsunk egy Világos, hogy egy ♣ (u, v) ∈ S 2 pár pontosan akkor éle a segéd- gráfnak, • ha u a kitüntetett pontja, C1 vonatkozó • vagy ha v Másképp szólva, B1 pedig egy másik pontja, az egyik C2 B1 -re alapkörnek, a kitüntetett pontja, vonatkozó lyett a v u pedig egy másik pontja, az egyik B2 -re alapkörnek. (u, v) pontosan azért segédél, mert bázisba, vagy mert tulajdonság fenntartásával. u-t kicserélhetjük ♣ 28 u-t v -re a becserélhetjük B2 v he- bázisból, a bázis Deníció Legyen h : S N+ 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 ∈ B1 B2 =⇒ h(u) = 0 • (u, v) ∈ AH =⇒ h(u) ≤ h(v) + 1. illesztési feltételeket követeljük meg. ♣♣ 4.8 Lemma (Terminálás) 2 Legyen H = {Bi ∈ Bi }i=1 . Legyen továbbá h : S N+ 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 T teljesülnek a B1 B2 -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 • S − X -ben • nincs (1̄, 2)-típusú nincs (1, 2̄)-típusú S − X -b®l X -be Ez azt jelenti, hogy minden illetve B1 -re pont, pont lép® segédél. B1 T B2 -n kívüli pontnak létezik alapköre vonatkozólag, attól függ®en, hogy X -nek, vagy B2

-re, S − X -nek eleme. A harmadik tulajdonság miatt ezek az alapkörök teljes egészében az X- S − X -ben fekszenek. T T Összevetve, (B1 B2 ) X nem b®víthet® független X -ben az M2 matroidra T T vonatkozólag, és (B1 B2 ) (S − X) nem b®víthet® független S − X -ben az T M1 matroidra vonatkozólag. Tehát B1 B2 feszíti X -et M2 -ben, és feszíti ben, illetve S − X -et M1 -ben. Ezt kellett igazolni. ♣ 4.9 Lemma (Inicializálás) Konstruálható egy (H, h) illeszked® pár Bizonyítás Mi Valóban. h≡0 minden 2 H = {Bi ∈ Bi }i=1 matroidban futtatott mohó algoritmus pedig egy Bi -hoz illeszkedik. Az 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. 29 4.2 Algoritmus (matroid metszet) 2 • input: M =

{Mi = (S, ri )}i=1 2 • output: (H = {Bi ∈ Bi }i=1 , h : S N) illeszked® pár, hogy minden v ∈ S (1̄, 2)-típusú pontra, h(v) = n. 2 • inicializálás: Legyen h ≡ 0, H = {Bi ∈ Bi }i=1 , ahol Bi =mohó(Mi )! • á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) ∈ AH , h(u) = h(v) + 1 7 Emeljünk u szintjén!  h(u) := h(u) + 1! • Van és (u, v) ∈ AH , h(u) = h(v) + 1 7 (u, v)-becseréljünk (u, v)-kicseréljünk az els®, a második matroidban!  Ha (u, v) ∈ A1 , akkor B1 := B1 + u − v !  Ha (u, v) ∈ A2 , akkor B2 := B2 − 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(n3 ) lokális m¶veletet hajt végre Bizonyítás Kísér® paraméterek változásait fogjuk meggyelni. Ezen meg- gyeléseinket összerakva, egyfajta szemmel már át tudjuk tekinteni az algoritmus lefutásának a struktúráját. 30 Kísér® Paraméterek • h szintfüggvény: kezdetben azonosan 0, sosem csökken, és az n-edik szint fölé nem emelkedik. • |B1 B2 | • h(u), elemszám: kezdetben legfeljebb ahol u n, és sosem n®. 0, a kiválasztott pont: legalább legfeljebb két paraméter nem

változik, akkor ez csökken. Ebb®l már világos az (1, 2̄)-típusú ♣ futásid®becslés. volna a cserélés el®tt, attól függ®en, hogy B2 -n, hajtottuk végre azt, tehát ez a pont nem lehet sem a kiszemelt az és ha a fenti pont nem keletkezik, mert egy ilyen szükségképpen (1̄, 2̄)-típusú letve O((n2 + n)n) n, (1̄, 2)-típusú, sem a másik v (∗, 2̄)-típusú, B1 -en pont, hiszen az a u (1, ¯2̄), il- B1 -en vagy pont, mert B2 -n történ® kicserélés esetén 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 |B1 B2 | elemszám sosem n®. Ha az u kiszemelt pont, szintje nem csökken egy lépésben, (ezen természe- tesen, 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és- ben vagy nem volt egy szinttel alacsonyabban olyan hettük volna, és ilyenkor melhettük ki tehát csak u |B1 B2 | (1̄, 2̄) (1̄, 2)-típusú u-t cserél- v szükségképpen lecsökken eggyel, ahogy állítottuk. (1, 2)-típusú (1, 2̄)-típusú, Valóban, máskülönben csökken, akkor h(u) v pont lehetne cserélés el®tt, de mindkét esetben pont lenne bel®le a cserélés után, hiszen els® esetben csak második esetben csak pont, nem-(1̄, 2)-típusú ponttá vált, és ezért nem sze- helyett. Ilyenkor cserélés el®tt vagy pont, mellyel u szintjét növeljük meg eggyel, vagy volt ilyen v u-val való cserélés után v de az v B1 -en cserélhetünk. Tehát, ha B2 -n, h nem n®, és |B1 B2 | sem 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 B1 + u − v ∈ B1 ,

végezzük a cserét. Tehát H és B2 − u + v ∈ B2 , végig bázisokból áll. 31 mert csak segédél mentén H-normalitást A egy vagy úgy ronthatjuk el, hogy a 0-szint felett keletkezik (1, 2̄)-típusú pont, vagy úgy, hogy megemeljük egy (1, 2̄)-típusú pont szint- jét. A komplexitás vizsgálatánál már láttuk, hogy nem keletkezik pont, és csak tani a A (1̄, 2)-típusú (1, 2̄)-típusú pont szintjét emeljük meg, tehát nem tudjuk elron- H-normalitást. 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 hajtunk végre, akkor egy h-illeszked® h-illeszked® bázison

kicserélést 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 ) matroidban, és a B + u − v ∈ B(M ) bázison (u, v)-becserélést bázis D0 D0 M∗ M befelé irányított bázisgráfjához jutunk, akkor ez ugyanaz a m¶velet, mint amikor a kicserélést hajtunk végre az hajtunk végre az matroidban, és a B ∗ ∈ B(M ∗ ) bázison (u, v)B ∗ − u + v ∈ B(M ∗ ) bázis kifelé irányított bázisgráfjához jutunk, hiszen D(M, B + u − v, be) =: D0 = D(M ∗ , B ∗ − u + v, ki). Tehát, ha a D befelé irányított bázisgráf tott bázisgráf is az. h-illeszked®, akkor D0 befelé irányí- ♣ Mindent összevetve, durván n3 lépés alatt, egy minX⊆S { r1 (S − X) + r2 (X) }- elemszámú, közös független halmazt konstruáltunk. 32 ♣ 4.4 Matroid tagság probléma Probléma m ∈ RS Legyen M = (S, r)

egy matroid az S alaphalmazon, és legyen egy pont az n-dimenziós térben. Döntsük el, hogy a der tartalmazza-e ezt a pontot vagy sem! B(r) bázispolié- ♠ Feltehet® • m(u) ≥ 0 (∀u ∈ S) • m(S) = r(S) ♣ Deníció S pontjait súlyoknak is mondjuk, egy Deníció Legyen y -fedetlen, ha y ∈ RS . Egy u∈S súly u pont súlya y -túlfedett, ha m(u). ♣ y(u) > m(u), és y(u) < m(u). ♣ Eldöntési Feltételek Legyen y ∈ conv{B(M )}! • nincs • van olyan len y -fedetlen súly X⊆S y -túlfedett S -ben =⇒ m ∈ conv{B(M )} halmaz, mely tartalmaz egy súly sincs benne, ezenfelül az y -fedetlen y, súlyt, de egyet- 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 m = y ∈ conv{B(M )}. P P • Legyen y = ki=1 λi Bi , ahol Bi ∈ B(M ), λi ≥ 0 ,

és ki=1 λi = 1. P m(X) > y(X) = ki=1 λi Bi (X) = r(X). Tehát m ∈ / B(r). ♣ ilyenkor 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, 33 azaz B(r) = conv{B(M )}. Bizonyítás • azaz : B(r) bázispoliéder egész pontjai éppen az M mat- 0 ≤ m(u) ≤ r(u) ≤ 1, m(B) ≤ r(B) ≤ |B|, ahol Világos, hogy a roid bázisai, hiszen B := {u ∈ S : m(u) 6= 0}, • ⊇: B(M ) ⊆ B(r), • ⊆: és és B(r) m(S) = r(S). 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= Deníció Pk i=1 Legyen élhalmaza! A Ai ⊆ S 2 , a Bi bázishoz tartozó befelé irányított bázisgráf Dy = (S, Ay ) := (S,

gráfnak, éleit az Deníció λi Bi ∈ conv{B(M )}! y -hoz Legyen Sk i=1 Ai ) tartozó segédéleknek nevezzük. h : S N+ y -hoz digráfot, az tartozó segéd- ♣ szintezés! Ha minden túlfedett súly a legalsó szinten van, és minden segédél legfeljebb egy szintet lép lefelé, akkor illetve y -illeszked® szintezésr®l beszélünk. Más szóval, h-tól y -normált, az • y(u) > m(u) =⇒ h(u) = 0 • (u, v) ∈ Ay =⇒ h(u) ≤ h(v) + 1. illesztési feltételeket követeljük meg. ♣♣ 4.13 Lemma (Terminálás) P Legyen y = ki=1 λi Bi ! Legyen továbbá h : S N+ 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 létezik egy k Ha nincs fedetlen súly, akkor készen vagyunk. üres szint, melyre 0 < k < n. súlyok halmaza! • X -ben nincs túlfedett súly, 34 Legyen X a k -nál Ha van, akkor nagyobb

szint¶ • X -ben • X nincs van fedetlen súly X -b®l S − X -be lép® segédél. utolsó tulajdonsága azt jelenti, hogy semelyik víthet® a függetlenség megtartásával igazolni. X -ben, T X Bi feszíti Bi tehát bázismetszet sem b®- X -et. Ezt kellett ♣ 4.14 Lemma (Inicializálás) Konstruálható egy (y, h) illeszked® pár Bizonyítás M Valóban. h≡0 minden y konvex kombinációhoz illeszkedik. Az matroidban futtatott mohó algoritmus pedig egy amit egytagú konvex kombinációnak tekinthetünk. B1 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.3 Algoritmus (matroid tagság) • input: M = (S, r), m ∈ RS+ , m(S) = r(S). P • output: (y = ki=1 λi Bi , h : S N) illeszked® pár, hogy minden

u ∈ S fedetlen súlyra, h(u) = n. • inicializálás: Legyen h ≡ 0, y = 1B1 , ahol B1 =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) ∈ Ay , h(u) = h(v) + 1 7 Emeljük meg u szintjét!  h(u) := h(u) + 1! • Van y (u, v) ∈ Ay , h(u) = h(v)+1 7 u-n növeljük, értékét valamelyik matroidban! Számítsuk ki ε := min{m(u) − y(u), λi }-t! Válasszuk meg i-t, hogy (u, v) ∈ Ai teljesüljön! 35 v -n csökkentsük  Ha ε = λi , akkor y := P j6=i λj Bj + λi (Bi + u − v)! [az (u, v) élt telít® javító lépés az i-edik matroidban]  Ha ε = m(u) − y(u), akkor y := P j6=i λj Bj

+(λi − ε)Bi + ε(Bi + 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 f edetlen} < 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 mát y konvex felbontásának a tagszá- 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 tehet®, hiszen a bázisok a B(S) = r(S) O(n3 ) hipersíkban fekszenek. lépésben meg- ♣ 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 Bi − u + v ∈ B, lépéseinket. Tehát A H H-normalitást mert csak segédél mentén végezzük a

javító végig bázisokból áll. 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 A h szintezés H-normalitását. 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 tunk végre, egy h-illeszked® h-illeszked® bázison becserélést haj- bázishoz jutunk. Javító lépésünk pedig egy ilyen 36 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(n6 ) lokális m¶veletet hajt végre. Bizonyítás Kísér® paraméterek változásait fogjuk meggyelni. Ezen meg- gyelé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®. • P h(B) λ(B)>0 szintösszeg: Legalább dosítás miatt legfeljebb 0, a Carathéodory tétellel való mó- n2 |{B : λ(B) > 0}| ≤ n3 , paraméter nem változik, akkor ez csökken egyet. Ebb®l már világos az O(n2 nn3 ) és ha a fenti két ♣ futásid®becslés. A szintfüggvény két változása között javító

lépéseket teszünk. Az végrehajtott javítás hatására csak kisebb, mint u v válhat fedetlenné, de ennek (u, v) élen h(v) szintje 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 het, ha az u-t h(u) paraméter csak akkor csökken- 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 csökkenti a szintösszeget. ♣ Mindent összevetve, durván benne van-e a B(r) h(u) − h(v) = 1-gyel n6 lépés alatt eldöntöttük, hogy a bázispoliéderben vagy sem. 37 ♣ m ∈ RS vektor 5. Polimatroidok 5.1 Eredmények polimatroidokkal kapcsolatban Legyen S egy n elem¶ halmaz! Legyen b(X) + b(Y ) ≥ b(X ∪ Y ) + b(X ∩ Y ) b : S R teljesül minden szubmoduláris, azaz X ⊆S halmazfüggvényr®l mindig feltesszük, hogy normalizált, azaz halmazra! Egy 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 ∈ RS : 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 nek nevezzük. Egy nevezünk, ha eleme y illetve y ∈ B(b) B(b)-nek. bázis. X -et a b y -pontosságnak X ⊆ S Egy olyan halmazt, melyhez y(X) = b(X), y -pontos tartozó sor egyenl®séggel teljesül, azaz nevezünk. Az poliédert bázispoliéder- vektort függetlennek vagy szubbázisnak, illetve bázisnak S(b)-nek, Tegyük fel, hogy B(b) halmaznak y feszíti y(X) = b(X). A két tehát deníció szerint az az oka, hogy szubmoduláris függvényre vonatkozólag, azaz 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 bázisról, és hogy ennek az az oka, hogy

y -pontos Az folytán P(y) halmazok összességét X X -pontos feszíti ®t. P(y)-nal zárt a metszetre és az egyesítésre. jelöljük. A szubmodularitás Í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 Py (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ól pedig azt, hogy a matroid egy s∈B esetén PB (s) = {s}, s ∈ /B

B∈B rangfüggvényével egyenl®, y- bázisa, akkor könnyen látható, hogy esetén pedig 38 r PB (s) = C(B, s). Ha b-r®l a szubmodularitáson és normáltságon túl még azt is feltesszük, f -el hogy monoton növ®, akkor polimatroidfüggvénynek nevezzük, és 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 y(s) S(f ) helyett, mert ha például egy y(s)-et negatív komponense, akkor y ∈ S(f ) szubbázisnak 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 léteznie kell, de erre y -pontossága A P (f ) elem y -pontos burkának is y(Py (s)) < y(Py (s) − s) ≤ b(Py (s) − s) ≤ b(Py (s)) ellenére. Speciálisan B(f ) ⊆ P (f ) lenne, is teljesül. polimatroidról világos, hogy van eleme, hiszen ugyanez már nem mondható

el a b s B(f ) bázispoliéderr®l. 0 ∈ P (f ). Ellenben A választ a tetsz®leges szubmoduláris függvényre futtatható mohó algoritmus adja meg. Rögzítsük S egy ≤ lineáris rendezését! Egy elemek halmazát jelöljük s≤ -vel. y ≤ ∈ RS y(s≤ ) = b(s≤ ), vektor, melyre is, hiszen S = s≤ , elemnél nem nagyobb Világos, hogy egyértelm¶en létezik egy olyan minden laritását felhasználva könnyen igazolható, hogy B(b)-nek s∈S ahol s ∈ S, a ≤ s∈S elemre. y ∈ S(b). y szubmodu- valójában eleme lineáris rendezésre nézve legna- gyobb elem. Kaptuk tehát, hogy a bázispoliéder sem üres 39 b 5.2 Polimatroid tagság probléma Probléma legyen Legyen m ∈ RS f : 2S R+ polimatroidfüggvény az S alaphalmazon, és egy pont az n-dimenziós térben. Döntsük el, hogy a P (f ) limatroid tartalmazza-e ezt a pontot vagy sem! Felvethet® ez a kérdés a bázispoliéderre, és az Megjegyzés S(f ) B(f )

♠ szubmoduláris poliéderre is. Nyilván elég eldönteni a kérdést az po- S(f ) szubmoduláris poli- éderre vonatkozólag, hiszen • m ∈ P (f ) ⇐⇒ m ≥ 0 és m ∈ S(f ) • m ∈ B(f ) ⇐⇒ m ∈ P (f ) f és m(S) = f (S). tulajdonságai közül is csak a szubmodularitást fogjuk kihasználni, ezért a ♣ továbbiakban b-vel Megjegyzés Az el®z® megjegyzés valójában nem növeli az általánosságot jelöljük. ugyanis megadható olyan z = zb ∈ RS vektor, hogy m ∈ S(b) ⇐⇒ m + zb ∈ S(fb ), ahol fb = b + zb polimatroidfüggvény. Valóban, az ekvivalencia, a szubmodularitás és a normáltság automatikusan teljesül bármely írhatjuk a az z vektorral való eltolás esetén. A monotonitás követelményét b(X) − b(Y ) + z(X − Y ) ≥ 0 X = Y +u alakba, ahol speciális esetre meghatározni, hiszen ha az egyenl®tlenségeket a X ⊇ Z+u ⊃ Z ⊇ Y rákövetkez® elem, akkor az X⊇Y kapjuk vissza. A speciális

esetnek Elég u ∈ S -ra Z+u a láncban z -t nyert fedésekre összeadjuk, ahol egy nomíthatatlan lánc elemein futtatjuk végig, ahol szubmoduláris. X ⊇ Y. Z -t Z -re párra vonatkozó általános egyenl®tlenséget zb (u) := b(S − u) − b(S) ♣ 5.1 Lemma (eldöntés) Legyen y ∈ B(b) • ha minden u ∈ S -ra: y(u) ≥ m(u), akkor m ∈ S(b). • ha létezik egy X ⊆ S , melyre 1. ∀x ∈ X : y(x) ≤ m(x) 40 megoldása, mert b 2. ∃x ∈ X : y(x) < m(x) 3. y feszíti X -et b-re vonatkozólag, akkor m ∈ / S(b). Bizonyítás • Nyilvánvaló, hiszen bármely y(X), • tehát m(X) ≤ b(X), Nyilvánvaló, hiszen így X ⊆ S vagyis halmazra m(X) ≤ y(X), és b(X) ≥ m ∈ S(b). m(X) > y(X), és b(X) = y(X), tehát m(X) ≤ b(X), 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)! Deníció Legyen y(u) > m(u), hetünk, m(u) u ∈ S! Ha y(u) < m(u), y -túlfedettnek akkor súllyal. hívjuk. Egy akkor u u-t y -fedetlennek, ha pontot súlynak is képzel- ♣ Megjegyzés Ha minden súlyt lefedtünk, készen vagyunk, m ∈ S(b). ♣ Deníció Minden u∈S lönböz® pontjaiba, azaz pontból húzzunk egy élt a u y -pontos éleket segédéleknek nevezzük, és A Dy := (S, Ay ) hívjuk. Py (u) halmaz burkának többi elemébe! Ay -al kü- Az így nyert jelöljük az általuk alkotott összességet. kifelé irányított bázisgráfot az y -hoz tartozó segédgráfnak ♣ Deníció Legyen h : S N+ szintezés! Ha minden túlfedett súly a legalsó szinten van, és minden segédél legfeljebb egy szintet lép lefelé, akkor illetve u-tól y -illeszked® szintezésr®l beszélünk. Más szóval, h-tól y -normált, az • y(u) > m(u) =⇒ h(u) = 0 • (u, v) ∈ Ay =⇒ 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 N+ y -hoz 41 illesztett szintezés! n-edik Tegyük fel, hogy minden fedetlen súly az szinten van! Ekkor készen vagyunk, tehát teljesül valamelyik eldöntési feltétel. Bizonyítás létezik egy Ha nincs fedetlen súly, akkor készen vagyunk. k üres szint, melyre 0 < k < n. Legyen X a k -nál Ha van, akkor nagyobb szint¶ súlyok halmaza! • X -ben nincs túlfedett súly, • X -ben van fedetlen súly, • X nincs X -b®l S − X -be lép® segédél. utolsó tulajdonsága azt jelenti, hogy vagyis y feszíti X -et. X = Ezt kellett igazolni. S u∈X Py (u), X y -pontos, tehát ♣ Megjegyzés Tegyük fel, hogy az (y, h) pár kielégíti példánk feltételeit! Legyen x=m az is, hogy k V y! x ≤ m, Ekkor és x ∈ S(b). Fenti bizonyításunkból világos x(S) = m(S − X) + y(X) = m(S − X) + b(X),

ahol X⊆S az üres szint feletti pontok halmaza. Megfordítva, ha felteszzük, hogy tetsz®leges halmaz, akkor x ≤ m, és x ∈ S(b), ezenkívül X ⊆S egy 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 : 2S R+ szubmoduláris függvény, m ∈ RS n-dimenziós vektor! Ekkor max{x(S) : x ≤ m és x ∈ S(b)} = minX⊆S {m(S − X) + b(X)}. ♣ Megjegyzés Egy m ∈ RS tünk. Vezessük be a vektort moduláris halmazfüggvénynek tekinthe- b1 = m, b2 = b jelöléseket! b1 , b2 : 2S R 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(b1 ) S(b2 )} = minX⊆S {b1 (S − X) + b2 (X)}. ♣ A következ® fejezetben általánosítjuk

eddigi eredményeinket, és kísérletet teszünk az itteni kedvez® tulajdonságokkal rendelkez® ott (y1 , y2 , h) (y, h) párnak megfelel®, hármas képében jelentkez® objektum felkutatására. 42 5.3 Polimatroid metszet probléma Probléma Legyen b1 , b2 : 2S R két darab szubmoduláris függvény, a közös S alaphalmazon. Egy olyan x ∈ RS vektort, mely mindegyik S(bi ) ris függvény által meghatározott bi szubmodulá- szubmoduláris poliéderben benne van, közös független vektornak vagy pontnak nevezünk! Keressünk egy maximális komponensösszeg¶ x ∈ RS , közös független vektort! Más szóval oldjuk meg a max{x(S) : x ∈ RS programot! és x ∈ S(b1 ) S(b2 )} ♠ Fels® korlát Legyen X ⊆ S tetsz®leges halmaz! Ekkor bármely x ∈ RS közös független vektorra x(S) ≤ b1 (S − X) + b2 (X). Bizonyítás Legyen y1 ∈ B(b1 ), y2 ∈ B(b2 ), bázissá terjeszthetjük Ekkor bármely bi -re X⊆S és z := y1

vonatkozólag, léteznek ilyen V y2 ≥ x! Mivel yi ∈ B(bi ) x-et vektorok. halmazra: • x(S) ≤ z(S) = z(SX) + z(X) ≤ y1 (SX) + y2 (X) • y1 (SX) ≤ b1 (S − X) • y2 (X) ≤ b2 (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 = y1 V y2 optimális, ha: • u ∈ S − X =⇒ y1 (u) ≤ y2 (u), • u ∈ X =⇒ y2 (u) ≤ y1 (u), • y1 feszíti S − X -et • y2 feszíti X -et az az S(b1 ) S(b2 ) polimatroidban, polimatroidban. ♣ Megmutatjuk, hogy az optimalitási feltételeket mindig ki lehet elégíteni. 43 5.3 Tétel (Edmonds) Legyen b1 , b2 : 2S R két szubmoduláris függvény S -en! Ekkor max{x(S) : x ∈ S(b1 ) S(b2 )} = minX⊆S { b1 (S − X) + b2 (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 = y1 V y2 alakban keressük majd, ahol Fenntartunk tehát mindkét matroidból egy még (y1 , y2 )-höz S az y1 ∈ B(b1 ) (y1 , y2 ) bázist. pontjainak egy olyan h:S N és y2 ∈ B(b2 ). Ezenkívül illesztjük szintezését is, melyre teljesülnek bizonyos feltételek. Fogalmak Legyen y1 ∈ B(b1 ), y2 ∈ B(b2 ), y := (y1 , y2 ) ! Deníció Egy y1 (u) < y2 (u) Deníció u∈S pont y-aktív, illetve y-passzív, ha teljesül. Minden u∈S y1 -segédéleknek get. Minden u∈S pontjaiból, azaz éleket séget. A Deníció u y1 -pontos nevezzük, és u y2 -pontos hívjuk. Legyen S A2 ) illetve halmaz burkának többi elemébe! A1 -el u-tól kü- Az így nyert jelöljük az általuk alkotott összessé- P1 (u) halmaz A2 -vel u-tól u-ba! különböz® Az így nyert jelöljük az általuk alkotott összes- kifelé, illetve befelé

irányított bázisgráf unióját ♣ h : S N+ alsó szinten van, és minden y -normált, P1 (u) burkának többi eleméb®l nevezzük, és D12 := (S, A1 y -segédgráfnak pontból húzzunk egy élt a pontba húzzunk egy élt a y2 -segédéleknek illetve ♣ lönböz® pontjaiba, azaz éleket y2 (u) < y1 (u), szintezés! y -segédél y -illeszked® Ha minden y -passzív legfeljebb egy szintet lép lefelé, akkor szintezésr®l beszélünk. Más szóval, • y1 (u) < y2 (u) =⇒ h(u) = 0, • (u, v) ∈ Ay =⇒ h(u) ≤ h(v) + 1 illesztési feltételeket követeljük meg. pont a leg- ♣♣ 44 h-tól az 5.4 Lemma (Terminálás) Legyen y1 ∈ B(b1 ), y2 ∈ B(b2 ), y = (y1 , y2 )! Legyen továbbá h : S N+ , 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 • S − X -ben • nincs halmaz y1 nincs u pont, y -aktív S − X -b®l X -be Tehát, ha a y2 (u). y -passzív pont, lép® y -segédél. X -beli, akkor y2 (u) < y1 (u), ha S − X -beli, akkor y1 (u) < S S X = u∈X P2 (u), és S − X = u∈S−X P1 (u). Tehát az X pont Ezenkívül y2 -pontos, pedig feszíti az S−X X -et, b2 halmaz pedig illetve Ezt kellett bizonyítanunk. b1 -re y1 -pontos, azaz y2 feszíti S − X -et, vonatkozólag. ♣ 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 függvénnyel futtatott mohó algoritmus pedig egy yi bi szubmoduláris 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: b1 , b2 : 2S R polimatroid függvények S -en. • output: (y = (y1 , y2 ), h) illeszked® pár, hogy minden u ∈ S y -aktív pontra, h(u) = n. • inicializálás: Legyen h ≡ 0, y1 ∈ B(b1 ), y2 ∈ B(b2 ), ahol yi =mohó(bi )! • á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.) ♣ 45 5.1 Lokális m¶velet (polimatroid metszet) Legyen • (y, h) u ∈ S , y -aktív illeszked® pár! Legyen Nincs olyan (u, v) ∈ Ay , melyre pont, h(u) = h(v) + 1 7 h(u) < n! Emeljünk!:  h(u) := h(u) + 1! • Van olyan  Ha (u, v) ∈ Ay , (u, v) ∈ A1 , melyre h(u) = h(v) + 1 7

Számítsuk ki !: akkor ε1 := min{ε11 + ε12 }, ahol ε11 := max{δ1 : y1 + δ1 (−u + v) ∈ B(b1 )}, ε12 := y1 (u) − y2 (u), és y1 := y1 + ε1 (−u + v)!  Ha (u, v) ∈ A2 , (csökkentés,növelés)-ε1 -el akkor ε2 := min{ε21 + ε22 }, ahol ε21 := max{δ2 : y2 + δ2 (−u + v) ∈ B(b2 )}, ε22 := y1 (u) − y2 (u), és y2 := y2 + ε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 dolgozzunk! ♣ program megoldásával Dení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 zük. v végpontját kiszemelt pontnak nevez- ♣ Deníció Azonosítsuk S -et az képezés segítségével! Minden s∈S amely kezdetben legyen egyenl® nak nevezzük, ha s = u, kurrensnek is mondjuk. {1, ., n} halmazzal egy π : S {1, ., n} pontra jelöljünk ki egy

τ (s) ∈ S le- pontot, 1-gyel! τ (s)-et az s ponthoz tartozó futó pont- tehát abban az esetben, ha s a kiválasztott, akkor ♣ Dení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. 46 ♣ 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) ∈ Ay , vagy ha nem, akkor u = t és (s, v) ∈ Ay , vagy (u, t) ∈ Ay é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 0 (s, t) ∈ A1 ! 0 P1 (t) Vessz®vel jelöljük a m¶velet utáni állapotot! Az állítás ekkor azzal ekvivalens, hogy nem része P1 (t)-nek, m¶velet hatására, ami csak akkor s∈ / Z := P1 (v) speciálisan Az 0 s∈ / P1 (t), 0 (s, t) ∈ A2 S mivel 0 s ∈ P1 (t)P1 (t), u ∈ P1 (t) P1 (t), node Tegyük fel, hogy u ∈ P1 (t), tehát és y(P1 (t)) esetén lehetséges. Ha 0 y1 (Z) = y1 (Z) = b1 (Z), s ∈ P1 (v). lecsökken a s∈ / P1 (v) tehát volna, 0 P1

(t) ⊆ Z , ellentétben feltevésünkkel. 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 y1 ∈ B(b1 ), illetve az y2 ∈ B(b2 ) relációt. Bizonyítás Világos, hogy [y1 +δ1 (−u+v)](S) = b1 (S), és [y2 +δ2 (u−v)](S) = b2 (S), és δ -t úgy választjuk, hogy y1 ∈ S(b1 ) és y2 ∈ S(b2 ) fennmaradjon. y végig két bázisból áll. 47 Tehát Az y -normalitást vagy úgy ronthatjuk el, hogy a 0-szint felett keletkezik egy y -passzív ε-t pont, vagy úgy, hogy megemeljük egy y -passzív pont szintjét. Mivel úgy választjuk meg, hogy se emelésnél, se csökkentésnél ne keletkezzék

passzív pont, és kizárólag csak elrontani az Az pont szintjét emeljük meg, nem tudjuk y -normalitást. y -illeszkedést segédél, azaz olyan h(v) + 1, y -aktív y- csak úgy ronthatjuk el, ha megemeljük eggyel egy pontos (u, v) ∈ Ay pár u talpának a h(u) szintjét, melyre h(u) = vagy ha valamelyik bázison végrehajtott változtatással behozunk a segédgráfba egy olyan új de utána az, és (u, v) ∈ S 2 h(u) > h(v) + 1 párt, mely a csere el®tt még nem segédél, 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 bázisból az h-illeszked® y -illeszkedést h-illeszked® bázishoz jutunk, m¶veletünk alkalmazása során. Tehát 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 h(s) = h(t) + 1 csak úgy fordulhat el®, ha szóló lemma alapján. (u a kiválasztott, h(s) = h(u) és h(t) = h(v). els® sért® pár. Az és akkor (s, v) Az (u, t) az els® ilyen sért® pár. (u, t), (s, v) ∈ Ay , v = τ (u) t≥v az új élekr®l a kiszemelt pont). Ilyenkor él miatt nem lehet él miatt pedig (s, t) nem sértene. (s, t) t < v, hiszen nem lehet, hiszen ekkor (s, t) az τ (s) < v , 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(n3 ) lokális m¶veletet hajt végre. Bizonyítás 0 ≤ h(u) ≤ n, hetjük meg. mert csak az n-edik szint alatti aktív pontok szintjét emel- h(u) egyik lépésben sem csökken. hajtunk végre. 48 Tehát

legfeljebb n2 szintemelést Tegyük fel, hogy egy s inaktívvá válik. s ∈ S ponton megszakítást hajtunk végre. s-et Ahhoz, hogy újra elkezdhessük Ekkor 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(n2 ), összesen pedig legfeljebb O(n3 ) megszakítást tudunk csak végrehajtani. Tegyük fel, hogy egy n s∈S pontra illeszked® élen telítünk! Ekkor legfeljebb ilyen telítés után befejez®dik Tehát s-en legfeljebb csak végrehajtani. O(n2 ), s egy körbejárása, és megemeljük összesen pedig legfeljebb n3 lépés alatt, egy hogy az y1 telítést tudunk minX⊆S { b1 (S − X) + b2 (X) }- elemszámú, közös független halmazt konstruáltunk. ε11 (y1 , u,

v), szintjét. • Mindent összevetve, durván Megjegyzés O(n3 ) s ♣ Bajt okoz, hogy nem világos, hogyan kell kiszámítani az illetve az pontnak az ε21 = ε21 (y2 , u, v) S(b1 ) értékeket. ε11 = Mindenesetre világos, szubmoduláris poliéderben való bentmaradását egyetlen típusú ok gátolja, miközben az y1 + δ1 (−u + v) mégpedig az, hogy fenn kell tartani minden vektorban u∈ / X 3 v -re az δ1 ∞, y1 (X) ≤ b1 (X) egyenl®tlenséget. Magyarán, max{δ1 : y1 + δ1 (−u + v) ∈ B(b1 )} = min{b1 (X) − y1 (X) : u ∈ / X 3 v}. Világos, hogy ez az érték éppen akkor pozitív, ha 0-val u ∈ P1 (v), különben pedig egyenl®. Vegyük észre, hogy a jobb oldalon tulajdonképpen a b1 (Y + v) − y1 (Y + v) X −v ⊆ S−u−v b(Y ) := szubmoduláris függvényt kell minimalizálni az feltétel mellett, tehát az S−u−v Y = 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 : y2 + δ2 (+u − v) ∈ B(b2 )} = min{b2 (X) − y2 (X) : v ∈ / X 3 u}. ♣ 49 5.4 Egy lokálisan javító algoritmikus séma Deníció Legyen S egy ges eleme egy rögzített nevezzük. n-elem¶ alaphalmaz! B y -t halmaznak! Legyen ezenfelül paraméternek, B -t y egy tetsz®le- paramétertérnek ♣ Megjegyzés y -t néha nem tekintjük xnek, 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.♣ Deníció tagú Tegyük fel, hogy minden Fy = {S1 (y), S2 (y), S3 (y)} y S -nek egy három S∗ S S = S1 (y) S2 (y) ∗ S3 (y)! paraméterhez létezik partíciója, tehát

(Megengedjük, hogy némely tagok üresek is lehetnek). aktívnak, vezzük. S2 (y) egy elemét y -semlegesnek, S3 (y) S1 (y) egy elemét egy elemét y -passzívnak ne- ♣ Deníció Tegyük fel, hogy minden nyított élekb®l álló halmaz! Dy = (S, Ay ) Ay y paraméterhez adott egy elemeit irányított gráfot pedig y -segédéleknek, y -segédgráfnak Ay ⊆ S 2 irá- az általuk alkotott nevezzük. ♣ Deníció Legyen y paraméter, és h : S N az alaphalmaz szintezése! K≥n y- Legyen egy adott korlát! Tegyük fel, hogy • h(u) ≤ K , • u ∈ S3 (y) =⇒ h(u) = 0, • (u, v) ∈ Ay =⇒ h(u) ≤ h(v) + 1. Ilyen esetben az (y, h) párt illeszked®nek mondjuk. Az els® pont gát fejezi ki. A második pontra y -illeszkedéseként y -normáltságként, fogunk hivatkozni. Deníció Legyen P : S 2 × B B adott u a harmadikra a korlátossá- h szintezés ♣ leképezés! Tehát minden (u, v) ∈ S 2 párra B -nek egy önmagába

képez® Puv : B B transzformációja. y 0 := Puv (y) a kiválasztott, 1. h v a kiszemelt pont. Tegyük fel, hogy y 0 6= y =⇒ u ∈ S1 (y) és (u, v) ∈ Ay végzünk m¶veletet), 50 (csak aktívra illeszked® segédélen 2. u∈ / S1 (y)0 3. s ∈ S1 (y 0 )S1 (y) =⇒ s = v 4. S3 (y 0 )S3 (y) = ∅ 5. (s, t) ∈ Ay0 Ay =⇒ [(u, t), (s, v), (u, v) ∈ Ay ] Ay ] vagy vagy (u, v) ∈ / Ay 0 (inaktivizáló vagy telít®), (új aktív csak a kiszemelt v lehet), (új passzív nem keletkezik), [s = v; (u, t), (u, v) ∈ Ay ] vagy vagy [u = t; (s, v), (u, v) ∈ [u = t, s = v; (u, v) ∈ Ay ] (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 javító m¶velet! Létezik-e olyan tezés, melyre az van? (Dy , Fy )y∈B Tegyük fel, hogy az (y, h) pár y rendszerhez megadható egy helyi paraméter, melyhez létezik egy olyan

illeszked®, és minden y -aktív pont a K -adik h szin- szinten ♠ A problémára igenl® válasz adható. 5.2 Algoritmus (lokálisan javító algoritmus séma) • input: (Dy , Fy )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 Nincs olyan (u, v) ∈ Ay , melyre u ∈ S , y -aktív pont, h(u) = h(v) + 1 7 h(u) < K ! Emeljünk!:  h(u) := h(u) + 1! • Van olyan (u, v) ∈ Ay , melyre h(u) = h(v) + 1 7 sunk !:  y := Puv (y)! 51 Helyileg javít- 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 dolgozzunk! ♣ program megoldásával Dení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 zük. v végpontját kiszemelt pontnak nevez- ♣ Deníció Azonosítsuk S -et az képezés segítségével! Minden s∈S amely kezdetben legyen egyenl® nak nevezzük; ha is mondjuk. Deníció {1, ., n} halmazzal egy π : S {1, ., n} pontra jelöljünk ki egy τ (s) ∈ S le- pontot, 1-gyel! τ (s)-et az s ponthoz tartozó futó pont- s = u, tehát abban az esetben ha s a kiválasztott, kurrensnek ♣ 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. ♣ 52 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 szintjét. A negyedik tulajdonság miatt nem keletkezik rólag csak y -aktív y -passzív y -passzív pont pont és kizá- pont szintjét emeljük meg, tehát nem tudjuk elrontani az y -normalitást. Az y -illeszkedést segédél, azaz olyan h(v) + 1, csak úgy ronthatjuk el, ha megemeljük eggyel egy pontos (u, v) ∈ Ay pár u talpának a h(u) szintjét, melyre h(u) = vagy ha valamelyik bázison végrehajtott változtatással behozunk a segédgráfba egy olyan új de utána az, és (u, v) ∈ S 2 h(u) > h(v) + 1 párt, mely a csere el®tt még nem segédél, 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 paraméterb®l h-illeszked® h-illeszked® paraméterhez jutunk, helyi javító m¶veletünk alkal- mazá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 h(s) = h(t) + 1 csak úgy fordulhat el®, ha lajdonság alapján. h(s) = h(u) és h(t) = h(v). els® sért® pár. Az és akkor (u a kiválasztott, (s, v) Az (u, t) az els® ilyen sért® pár! (u, t), (s, v) ∈ Ay , v = τ (u) t≥v az ötödik tu- a kiszemelt pont). él miatt nem lehet él miatt pedig (s, t) nem sértene. (s, t) t < v, Ilyenkor hiszen nem lehet, hiszen ekkor (s, t) az τ (s) < v , 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(n2 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 53 0 ≤ h(u) ≤ K , hetjük meg. h(u) mert csak a K -adik szint alatti aktív pontok szintjét emel- egyik lépésben sem csökken. Tehát legfeljebb nK szinteme- lést hajtunk végre. Tegyük fel, hogy egy s inaktívvá válik. s ∈ S ponton megszakítást hajtunk végre! Ahhoz, hogy újra elkezdhessük s-et Ekkor körbejárni, és egy új megszakítást hajthassunk végre rajta, el®ször újra aktívvá kell tenni. Ehhez s azonban kellene hogy legyen egy 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 összesen pedig legfeljebb Tegyük fel, hogy egy O(n2 K) s∈S O(n2 ), s

O(nK), pontra illeszked® élen telítünk! Ekkor a egy körbejárása, és megemeljük összesen pedig legfeljebb Mindent összevetve, durván legfeljebb megszakítást tudunk csak végrehajtani. tulajdonság és a körbejárási lemma miatt, legfeljebb fejez®dik s-en n2 K O(n3 ) s n szintjét. ilyen telítés után beTehát s-en legfeljebb telítést tudunk csak végrehajtani. lépés alatt megtaláljuk a keresett 54 2-es ♣ (y, h) párt. 5.5 Szubmoduláris függvény minimalizálás Probléma Legyen Legyen X⊆S b : 2S R szubmoduláris függvény az b(X) értéket az X tetsz®leges halmaz, a rangjának nevezzük. S halmaz szubmoduláris X ⊆ S Keressünk egy minimális rangú alaphalmazon! halmazt! Más szóval oldjuk meg a min{b(X) : X ⊆ S} ♠ programot! Az el®z® fejezetben kidolgozott modellre fogjuk visszavezetni feladatunkat. Ehhez deniálnunk kell az alaphalmazt, a tartozó Fy Dy partíciót, és javító m¶veletet

ehhez a tott speciális X B paraméterteret, az y paraméterhez segédgráfot. Ezenkívül kell mutatnunk egy (Dy , Fy )y∈B P helyi rendszerhez, majd a séma által kiszámí- (y, h) illeszked® párból meg kell konstruálnunk a problémánk egy megoldását. K := n. Deníció Sn -el jelöljük S összes < továbbiakban mindig egy legfeljebb Megjegyzés I -t Sn azonosíthatunk egy S Az alaphalmaz természetesen lesz. lineáris rendezéseinek a halmazát. n-elem¶ indexhalmazt jelöl. részhalmazának tekintjük majd, tehát egy <i lineáris rendezéssel. I a ♣ i∈I indexet ♣ Deníció • B := {y = P i∈I λi yi : yi = mohó(i) ∈ ext(B(b)), P λi = 1, λi ≥ 0} • S1 (y) := {s ∈ S : y(s) > 0}, S3 (y) := {s ∈ S : y(s) < 0} • Ay := {(s, t) ∈ S 2 : ∃i ∈ I, (s, t]i > 0} ♣ Megjegyzés a fenti B A b-re vonatkozó mohó algoritmus alapján úgy is tekinthetünk paraméterterünkre, hogy egy eleme a inak

egy legfeljebb várható értéke y, delkezésünkre. ♣ n elem¶ és egy yi I B(b) bázispoliéder részhalmazára koncentrált csúcs, az i λ yi csúcsa- eloszlás. Ennek a lineáris rendezés formájában áll a ren- 55 5.15 Lemma (megoldás) Legyen (y, h) illeszked® pár! Tegyük fel, hogy S1 (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 S1 (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. S1 (y)-beli Ha van üres szint, melyre k -nál kisebb szint¶ elemek halmaza! • X -ben nincs S1 (y)-beli • X -ben van minden • X k a Legyen X elem, akkor létezik egy nincs pont, S3 (y)-beli S − X -b®l X -be pont, lép® segédél. utolsó tulajdonsága azt jelenti, hogy vagyis ahol y X -et. feszíti y− = y

V 0. 0 < k < n. X = S t∈X [0, t]i , tehát Tehát készen vagyunk, ugyanis Más halmazra pedig X yi -pontos, b(X) = y(X) = y − (S), b(Y ) ≥ y(Y ) ≥ y − (S). ♣ Deníció Legyen y< ∈ ext(B(b)) a < lineáris rendezésb®l a mohó algoritmus által generált extrém bázis! melyre u < t ≤ v! Legyen továbbá Tegyük a t u, v ∈ S 2 elemet közvetlenül lineáris rendezéshez jutottunk. Az általa generált mutációjának nevezzük. Ezen mutációk jelöljük. yt u két elem, és elé! Ezzel egy új extrém bázist |(u, v]< |-elem¶ t ∈ S halmazát y <t egy (u,v)- My (u, v]-vel ♣ 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 yuv ∈ conv(ext(B(b))) vektor, melyre • yuv = v t=u+1 P v λt yt , ahol (λt )t=u+1 konvex kombinációs együtthatók, és yt ∈

My (u, v], (u, v)-mutációja az y extrém bázisnak, • létezik egy δuv ≥ 0 szám, melyre yuv = y + δuv (−u + v), • yuv kiszámítható O(n2 γ) id®ben, ahol γ a b szubmoduláris függvény kiér- tékeléséhez szükséges id®. 56 5.17 Következmény Deniálható egy P helyi javító m¶velet a (Dy , Fy )y∈B rendszerhez. Bizonyítás [köv.] Legyen y = P i∈I λi yi ∈ B , u ∈ S1 (y) Egy eljárást fogunk megkonstruálni, ami egy olyan O(n2 ) eredményez legfeljebb és (u, v) ∈ Ay ! Puv (y) := y 0 ∈ B lépésben , amely kielégíti a P -t®l vektort megkövetelt öt tulajdonságot. Az eljárás egy lépése el®tti paramétert y 0 -vel y -nal, a lépés után nyert paramétert 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 0 -ként felfogni. Ugyanez érvényes

az összes többi fenntartott objektumra is.) • leállás: Ha |(u, v]i | > 0, (u, v) ∈ / Ay , azaz nem létezik olyan i ∈ I index, melyre akkor álljunk le! • általános lépés: Különben válasszunk egy ilyen i indexet! Vagyis, i -t felbonthatu <i v . Az intervallum redukáló eljárásunk nyomán, yuv i 2 i juk O(n γ) id®ben az y paraméter l darab yj (u, v)-mutációjának λj súlyokkal képzett konvex kombinációjára λi -vel felbontásában a hatókkal súlyozott yji bináció legyen az új 0 y = y+ i (−u λi δuv súlyozott yi (1 ≤ j ≤ l). Cseréljük ki y extrém bázist ezekre a λij λi együtt- extrém bázisokra, és az így nyert új konvex kom- y0 paraméter! A tételb®l azt is leolvashatjuk, hogy + v), tehát √ i y -ból λi δuv 2 egységet léptünk −u + v irányában. Képletben, 0 y := i y +λi (−yi +yuv ) = X λj yj −λi yi + l X i (λij λi )yji = y +λi δuv (−u+v). j=1 j∈I

• megszakítások  Ha az eljárás valamelyik lépésében |I 0 | > n, akkor y0 konvex kom- biná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(n3 ) id®ben megtehet®, mint ismeretes, és folytassuk az eljárást!  Ha az eljárás valamelyik lépésében 0 y (u) ≤ 0. u ∈ / S1 (y 0 )-re Ekkor létezik egyértelm¶en egy νy(u) + (1 − ν)y 0 (u) = 0. Ilyenkor y0 az új paraméternek, és álljunk meg! 57 0≤ν<1 helyett vegyük jutunk, tehát szám, melyre νy + (1 − ν)y 0 -t • választási szabály: Az általános lépésben válasszuk a program egy megoldását! maxi∈I |(u, v]i | ♣ Meg kell vizsgálnunk eljárásunk komplexitását! A választási szabály miatt minden redukálásnál vagy a maxi∈I |(u, v]i |, vagy az |{i ∈ I : i = maxj∈I |(u, v]j }| kísér® paraméter értéke csökken. Így legfeljebb szen bármely

0≤k≤n O(n2 ) érték is a maximum, ez legfeljebb lódhat, mert a Carathéodory tétel alkalmazása miatt, alatt. Tehát legfeljebb redukálást végzünk, hi- O(n4 γ + n5 ) n indexen realizá- |I| ≤ n teljesül az eljárás id® alatt számítjuk az átmenetet. Való- ban, egy redukálást és egy esetleges Carathéodory tételt, O(n2 γ + n3 ) id®ben tudunk lebonyolítani. Világos, hogy y0 ∈ 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 az yi -segédgráf (u, v) t <i s ≤ v éle mentén redukáltunk! az intervallumredukálás el®tt, és után, hiszen szükségképpen s-et helyeztük tervallumban kellett elhelyezkednie. b = c. u (s, t) egy új Ekkor világos, hogy s <i u ≤i t <i v elé, és y 0 -segédél, t-nek a redukálás valahol az Két azonosodás lehetséges u ≤i [u, s)i a = d in- vagy

Attól függ®en, hogy mely azonosodások teljesülnek, kapunk négy ese- tet. Például, ha egyik azonosodás sem teljesül, tehát redukálás el®tt a 6= d c 6= b, akkor (u, t),(u, v) és (s, v)) is yi -segédél, tehát élei a redukálás el®tti y - segédgráfnak is. Világos, hogy ez az eljárás kezdetén meglév® igaz, hiszen az erre vonatkozó valamely (u, v]i Bizonyítás [tétel] Az (S, <) y -segédgráfra (u, v]i intervallumhoz. 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} • e∈U S ♣ lineárisan rendezett halmazt azonosíthatjuk az terjed® természetes számok rendezett halmazával. Vezessük be a jelöléseket. Legyen is intervallumból, bizonyos elemek kiszórásával jutottunk a tekintett redukálásunk el®tti 1-t®l n-ig és a:T ×S R olyan mátrix, melyre A =⇒ a(e) ≤ 0, 58 • e ∈ D

=⇒ a(e) ≥ 0, • e ∈ (T × S) − (U Az t ∈ T -re S A) − D =⇒ a(e) = 0, P • minden a mátrix sorait jelöljök s∈S ats = 0. z1 ,.,zl -lel 5.18 Lemma Létezik egy olyan δ ≥ 0 szám, melyre δ(−u+v) ∈ conv(z1 , , zl ), és a konstruált el®állítás nem triviális, azaz van benne nemnulla konvex együttható is. Bizonyítás a elt¶nik e Ha létezik olyan e∈D diagonális elem, melyre a(e) = 0, akkor sorának többi elemén is, hiszen azokon nempozitív, és a sorösszeg δ -t zérus. Tehát ilyenkor vehetjük nullának. Ellenkez® esetben el®ször határozzunk meg olyan l (ϑt ≥ 0)t=1 nemnegatív számokat, melyekre l X ϑj zt )(s), (−u + v)(s) = ( ha v ≥ s ≥ u + 1. t=1 Ezt mohón megtehetjük az sabb értékei fel®l haladva. a-ra vonatkozó el®jelszabályok alapján s maga- 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 egyenPl 1

P l letet választás kielégíti a lemma t=1 ϑt 6= 0-val. Kapjuk, hogy δ := ϑ t=1 Megmutatjuk, hogyha az teljesül az 2 O(n γ) t ♣ kívánalmait. a-tól a mátrix zt sorát megkövetelt négy tulajdonság. yt − y -nak deniáljuk, akkor A lemma alapján, ezzel az futásid®vel is készen leszünk, hiszen világos, hogy bár az együtthatók kiszámítása O(n2 ) id®ben megy, azonban minden mátrixelem kiszámításához ki kell értékelnünk még a hogy minden b szubmoduláris függvényt is. Azt kell tehát belátni, t ∈ T -re, yt (s) ≤ y(s) ha u ≤ s < t, yt (s) ≥ y(s) ha s = t, yt (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ú. ken® függvénye, mid®n X ⊆ S − s. Ez a szubmodularitás miatt Tegyük fel, hogy 59 X -nek csök- yt (s) = b(X + s) − b(X) és y(s) = b(Y + s) − b(Y ). és X = Y, Tehát az y Ekkor könnyen

ellen®rízhet®, hogy attól függ®en, hogy extrém bázis tulajdonságokat. u ≤ s < t, s = t, (u, v)-mutációiból alkotott illetve a X ⊆Y, Y ⊆X s<u vagy mátrix kielégíti a kívánt ♣ Tehát az átmenetet, azaz a kívánt tulajdonságokkal rendelkez® letet s > t. O(n4 γ + n5 )) P id®ben számíthatjuk. Mivel a modellünk legfeljebb alkalommal hajtja végre P -t, m¶ve- O(n3 ) az eredményül kapott szubmoduláris függvényt minimalizáló algoritmus futásidejére az O(n7 γ + n8 ) 60 fels® korlát adódik. Hivatkozások [1] W.HCunningham, Testing membership in matroid polyhedra, J. Combi- natorial Theory B36 (1984) 161-188. [2] W.HCunningham, On submodular function minimization, Combinato- rica 5 (1985) 185-192. [3] R.EBixby, WHCunningham,DMTopkis, The poset of a polymatroid extreme point Math.OperRes 10 (1985), 367-378 [4] S.Fujishige, XZhang, New Algorithms for the Intersection Problem of Submodular Systems, Japan J.

IndustAppl 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, LFleischer, A push-relabel framework for submodular function minimization and applications to parametric optimization (2004) 61