Gazdasági Ismeretek | Operációkutatás » Pajkossy Katalin - Grafikus szubmoduláris függvények minimalizálása

http://www.doksihu Eötvös Loránd University Faculty of Science Pajkossy Katalin Grafikus szubmoduláris függvények minimalizálása BSc szakdolgozat Témavezet® : Bérczi Kristóf Operációkutatási Tanszék Budapest, 2008 http://www.doksihu Bevezet® A grakus szubmoduláris függvények olyan, gráfok élhalmazán értelmezett függvények, amelyek a gráf rangfüggvényének és az élek tetsz®leges lineáris függvényének összegeként állnak el®. Az ilyen alakú függvények minimalizálásának problémáját el®ször Cunningham vizsgálta, aki ezt egy hálózat optimális támadásának a feladatára vezette vissza. A szakdolgozat célja, hogy áttekintse a f®bb megoldó algoritmusokat és a grakus szubmoduláris függvényminimalizálás sokoldalú alkalmazásait a kombinatorikus optimalizálás és a zika területér®l. A szakdolgozatban a problémát szinte végig az ekvivalens Optimális Kooperáció Feladat alakban vizsgáljuk. Az els® fejezetben

ismertetjük a dolgozatban alkalmazott jelölésrendszert A második fejezetben az Optimális Kooperáció Feladat ismertetése után röviden áttekintjük az általános szubmoduláris függvények minimalizálását megoldó polinomiális algoritmusokat. A grakus szubmoduláris függvények minimalizálását megoldó algoritmusok egy adott polimatroidon való optimalizáláson alapulnak. Ezért részletes ismertetésük el®tt a harmadik fejezetben áttekintjük a polimatroidokkal kapcsolatos alapvet® fogalmakat és ismertetjük Edmonds 1970-es polimatroid mohó algoritmusát, valamint ennek egy alkalmazását, Frank és Tardos reszelési algoritmusát(1988). Az Optimális Kooperáció Feladatot megoldó algoritmusok implicit módon ez utóbbit használják. A negyedik Cunningham fejezetben bemutatunk három megoldó algoritmusa egy a algoritmust gráf az Optimális élhalmaza által Kooperáció deniált feladatra. polimatroidon optimalizál,míg a

Barahona(1992) és a Seb®-Preissmann(2000)-féle algoritmus a csúcshalmaz által meghatározott polimatroidon. A polimatroid mohó algoritmus futása során egy ponton szükség van egy adott értéket minimalizáló halmazt megtaláló szubrutinra, ez egy hálózati folyamban történ® minimális vágásra vezethet® vissza. A fejezetben ismertetünk két ilyen lehetséges hálózati folyam - modellt is, az egyik Barahona, Baiou és Mahjoub modellje(2002), a másik a Picard és Queyranne(1982) vagy Padberg és Wolsey (1983) -féle modell. Az ötödik fejezetben kombinatorikus optimalizálási problémákat mutatunk, amik az Optimális Kooperáció Feladatra vezethet®k vissza. Ezek közül a hálózat optimális merevítésének, illetve a gráf ellenállóképességének problémáját Cunningham vezette be 1985-ös cikkében, az Optimális Támadás Feladattal összefüggésben. Utóbbira és az Optimális Növelés feladatra az eredeti algoritmusokon kívül ismertetjük Seb®

és Preissmann algoritmusát is. 2 http://www.doksihu BEVEZETŽ 3 A Potts modell egy statisztikus zikai modell, az Ising modell általánosítása, ahol a spinek felvehetik az 1 . q-1 étékeket. A rendszer partíciófüggvénye egy fontos mennyiség, ami meghatározza a statisztikai tulajdonságait. A grakus szubmoduláris függvényminimalizálás egy érdekes alkalmazásaként Juhász, Rieger és Iglói(2001) megmutatták, hogy a Potts nagy qállapotú rendszer esetén a partíciófüggvény nagyságrendjét egy szubmoduláris függvény minimuma határozza meg. Végül a szakdolgozatban bemutatott módszereket illusztrálva megoldunk egy feladatot el®ször a matroid metszet algoritmusra, majd Nash-Williams és Tutte tételein keresztül az Optimális Kooperáció Feladatra visszavezetve. A szakdolgozat alapjában véve az [1] irodalom tárgyalását követi. Ezen kívül a harmadik fejezetben a [4],[6],[7], a negyedik fejezetben a [2],[3],az ötödik

fejezetben az [5],[8] irodalomra támaszkodtunk. Köszönöm témavezet®mnek a segítséget és a bíztatást amivel a munkám során támogatott. http://www.doksihu Tartalomjegyzék 1. Jelölések 5 2. Az Optimális Kooperáció Feladat 6 3. Optimalizálás polimatroidon 8 3.1 Polimatroidok . 8 3.2 A mohó algoritmus . 9 3.3 Reszelés(Dilworth Truncation) . 4. Algoritmusok 11 14 4.1 Cunningham algoritmusa . 14 4.2 Barahona algoritmusa . 15 4.3 A Seb® -Preissmann algoritmus . 17 4.31 17 A megoldás kiterjesztése . 4.32 4.33 Hálózati folyam modell . 19 Az algoritmus . 20 5. Alkalmazások 22 5.1 Optimális Növelés Feladat . 22

5.2 A hálózat ellenállóképessége . 24 5.3 A hálózat optimális merevítése . 25 5.4 A Potts modell . 26 5.5 Feladat . 27 5.51 Matroid metszet algoritmussal . 5.52 Visszavezetése az Optimális Kooperáció Feladatra Bibliography . 27 28 30 4 http://www.doksihu 1. fejezet Jelölések Legyen G=(V,E) irányított vagy irányítatlan gráf . x :E Legyen U⊆E x(U ) = P e∈U x(e) Legyen S⊆ V. P x(E(S)) = e=xy:x∈S,y∈S x(e) P x(δ(S)) = e=xy:x∈S,y∈S / x(e) {V1 . Vp } V egy partíciója, W ⊆ {V1 Vp } P x(δ(W )) = e:x∈Vi ∈W,y∈Vj ∈W,Vi Vj x(e) Legyen 5 R http://www.doksihu 2. fejezet Az Optimális Kooperáció Feladat 2.01 Deníció . Az (szubmoduláris függvény) f : 2E R függvény szubmoduláris, ha minden A,B ⊆ E- re teljesül f (A) + f

(B) ≥ f (A ∪ B) + f (A ∩ B) 2.02 Deníció . Az f szubmoduláris függvény moduláris, ha a fenti (moduláris függvény) egyenl®tlenséget egyenl®séggel teljesíti, és f(∅)=0. Ekkor f(A)= P 2.03 Deníció a∈A f(a). . Az f szubmoduláris függvényt grakusnak nevezzük, ha a (grakus függvény) G=(V,E) gráf élhalmazán értelmezzük, és f = s + rG ahol f,rG ,m:2E R függvények, rG a gráf rangfüggvénye, s pedig tetsz®leges moduláris függvény. A grakus függvényminimalizálási feladat tehát az rG (A) + s(A) értéket minimalizáló A⊆E halmaz megtalálása. Ehelyett a következ® ekvivalens problémát fogjuk vizsgálni : Az Optimális Kooperáció Feladat : X  M ax fG,s = cG (A) + s(e) : A ⊆ E(G) a∈A Az elnevezés eredetéül szolgáló elképzelt szituáció a következ® : Közös a tudományterületen lehet® legnagyobb dolgozó állami együttm¶ködését,illetve kutatókat támogatást egységnyi kell úgy

kapjanak.Az támogatást kap kutatócsoportokba állam támogatja minden szervezni, egyes kutatócsoport. hogy kutatópárosok Két külön kutatócsoportban lév® kutató nem m¶ködhet együtt. Világos, hogy a feladatot modellezi az Optimális Kooperáció Feladat. Mivel s(e)≤0 esetben e-t törölve, s(e)≥ esetben pedig e-t összehúzva ekvivalens problémát kapunk, így föltehetjük, hogy 0 ≤s(e)≤1.Az ilyen s függvényeket a továbbiakban súlyfüggvénynek nevezzük. 6 http://www.doksihu 7 2.04 Deníció Adott G=(V,E) gráf s súlyfüggvény, és a csúcsok egy P partíciója esetén esetén a gG,s (P ) = |P | + s(E(P )) értéket a partíció értékének nevezzük. 2.01 Állítás Az Optimális Kooperáció Feladat egy optimális F*⊆E megoldása tartalmaz minden olyan élet, amit G(F)indukál.(azaz mindkét végpontját tartalmazza) 2.02 Állítás Egy gG,s (P )-t maximalizáló P* egy osztályába tartozó csúcsok által indukált

részgráf összefügg®. Tehát egyértelm¶en megfeleltethetjük egymásnak az komponenseit és a gG,s -t fG,s -t maximalizáló élhalmaz összefügg® maximalizáló partíció osztályait, így az Optimális Kooperáció Feladat megoldását minden esetben kereshetjük úgy, mint V egy partícióját. A grakus szubmoduláris függvények minimalizálását megoldják az általános grakus szubmoduláris függvények minimalizálását megoldó algoritmusok. Ilyen például Grötschel, Schijver és Lovász az ellipszis módszert használó algoritmusa(1988), vagy Schijver (2000)kombinatorikus algoritmusa. A problémára hatékonyabb megoldást kínálnak azok az algoritmusok, amik kihasználják a grakus tulajdonságot. Az els®, az Optimális Kooperációs Feladatot megoldó és nem az ellipszis módszert használó polinomiális algoritmus Cunningham (1984) algoritmusa, ami Edmonds (1965) matroid partíciós algoritmusának a módosítása.

Cunningham(1985) kidolgozott egy speciális algoritmust az Optimális Kooperáció Feladattal ekvivalens Optimális Támadás Feladatra is, ezt a harmadik fejezetben ismertetjük majd a Barahona és a Seb®-Preissmann -féle megoldó algoritmussal együtt. http://www.doksihu 3. fejezet Optimalizálás polimatroidon 3.1 Polimatroidok A 3. fejezetben ismertetésre kerül® algoritmusok polimatroidon való optimalizáláson alapulnak Szükséges tehát, hogy tisztázzuk a polimatroidokkal kapcsolatos alapvet® fogalmakat, valamint ismertessük Edmonds mohó algoritmusát(1970). Legyen RE + = (y = (yj : j∈E) :y≥ 0). 3.11 Deníció (polimatroid) A polimatroid P⊆ RE+ , ami teljesíti az alábbi tulajdonságokat: 1.0∈P 2.Ha 0≤ y ≤ x∈ P, akkor y∈P 3.Tetsz®leges x∈ RE + vektorra a maximális y∈P, y ≤ x vektorok(ezeket az x P-bázisainak nevezzük) komponenseinek összege megegyezik. A polimatroidokat megadhatjuk úgy is, mint egy poliéder metszete RE + -vel.Ekkor

a poliéder határfüggvénye speciális alakú. 3.12 Deníció (monoton növ® halmazfüggvény) Az S alaphalmazú h halmazfüggvény monoton növ®, ha h(X) < ∞ és X⊆Y⊆S esetén h(x) < h(Y ). Megjegyzés. Véges érték¶ monoton növ® halmazfüggvény nemnegatív( a halmazfüggvényeknél megkövetelt h(∅)=0 miatt.) 3.13 Deníció (polimatroid . Véges érték¶, szubmoduláris,monoton növ® függvény) halmazfüggvényt polimatroidfüggvénynek hívunk. Megjegyzés. A matroid rangfüggvények egyúttal polimatroid függvények is 3.11 Tétel (polimatroid) Legyen b polimatroid függvényEkkor a  P (b) = x ∈ RE : x ≥ 0, x(A) ≤ b(A)∀A ⊆ S halmaz polimatroid. 8 http://www.doksihu 3.2 A mohó algoritmus 9 3.2 A mohó algoritmus Adott c :SR vektorra tekintsük a  max(cx) : x ∈ x ∈ RE : x ≥ 0, x(A) ≤ b(A)∀A ⊆ S optimalizálási feladatot. Ez egy lineáris program, aminek a duálisa a következ® : X  S min yb : y ∈ D(c) =

R2 : y(Z) ≥ 0, haZ 6= S, yZ χZ ≥ c Z⊆S yb = X y(Z)b(Z) Z⊆S Feltehet®, hogy hogy S elemei a c értéke szerinti csökken® sorban vannak rendezve : c(s1 ) ≥ (s2 ) ≥ . ≥ c(sk ) ≥ 0 > c(sk+1 ) ≥ c(sn ) Jelölje Si az els® i elem halmazát. Deniáljuk a x̄ ∈ n , ȳ ∈ R2 n vektorokat a következ®képp : x̄(s1 ) := b(s1 ), x̄(si ) := b(Si − b(Si−1 )), i = 2 . k, x̄(sj ) := 0, j = k + 1 n ȳ(Sn ) := c(sn ), i = 1,2 . n − 1ȳ(Si ) := c(si ) − c(si+1 ), S többi részhalmazára (Z) :=0. 3.21 Állítás ȳ ∈ D(c) 3.21 Lemma x̄ ∈ P(b). Bizonyítás. x̄ ≥ 0 b monotonitása miatt teljesül, így csak azt kell belátnunk, hogy = x̄(Z) ≤ b(Z) teljesül minden Sm(Z) ⊆ Sm(Z)−1 ∪ Z Z⊆S halmazra. Jelölje m(Z) a max{i :si P z∈Z x̄(z) = ∈ Z, c(si ) ≥ 0}-t. Ekkor , és b monotonitása miatt Sm(Z) ) ≤ b(Sm(Z)−1 ∪ Z) Teljes indukciót használva m(Z)-re : m(Z)=0 esetén minden x̄(Z) = X

z ∈ Z -re c(z)≤0, így x̄(z) : z ∈ Z = 0 ≤ b(Z) m(Z)=1 esetén x̄Z = x̄(s1 ) = b(S1 ) = b(Z) Legyen i=m(Z)≥ 2. Alkalmazzuk a teljes indukciót Si−1 ∩ Z -ra . b(Z) + b(Si−1 ) ≥ b(Z ∪ Si−1 ) + b(Z ∩ Si−1 ), b(Z) ≥ b(Z ∪ Si−1 ) + b(Z ∩ Si−1 ) − b(Si−1 ) = http://www.doksihu 3.2 A mohó algoritmus b(Z∪Si−1 ) (Z∩Si−1 ) 10 + x̄(Z ∩ Si−1 ) − b(Si−1 ) ≥ + b(Si ) − b(Si−1 ) = x̄(Z ∩ Si−1 ) + x̄(si ) = x̄(Z ∩ Si ) = x̄(Z) 3.21 Tétel x̄ optimális a primál feladat, ȳ pedig a duál feladatoptimális megoldása. Bizonyítás. cx̄ = ȳb A egyenl®séget kell belátnunk. cx̄ = c(S1 )b(S1 ) + k X i=2 c(S1 )b(S1 ) + k X X c(Si )[b(Si ) − b(Si−1 )] + c(Z)[b(Si ) − b(Si−1 )] = Z:Z6=Si i=1.k c(Si )[b(Si ) − b(Si−1 )] = c(Sk )b(Sk ) + i=2 k−1 X [c(S1 ) − c(Si+1 )]b(Si ) = i=1 X ȳ(Z)b(Z) = ȳb Z⊆S ∀j ≤ kx̄(Sj ) = X x(si ) = j X b(Si ) − b(Si−1 ) = b(Si )

i=1 si :i≤j A fenti egyenl®séget meggyelve láthatjuk, hogy az algoritmus valóban "mohó" módon m¶ködik : az x=0 vektorral indulva súly szerinti csökken® sorrendben haladva a soron következ® elemnek megfelel® komponens értékét az x∈P feltételt nem sért® legnagyobb értékre növeli. Az algoritmus addig fut, amíg még van nem vizsgált pozitív súlyú elem. 3.21 Deníció (Szubmoduláris poliéder) Legyen S az alaphalmaz, b szubmoduláris halmazfüggvény. Az  S(b) = x ∈ RS : x(A) ≥ b(A)∀A ⊆ S, x(S) = b(S) halmazt szubmoduláris poliédernek nevezzük. A duális poliéder :  S y ∈ R2 : y(Z) ≥ 0, haZ 6= S, X yZ χZ = c Z⊆S 3.22 Tétel Ha b szubmoduláris, b(Z)= max{x(Z) : x ∈ S(b)}∀Z ⊆ S -re Tekintsük a primál - duál optimalizálási feladatot a poliéderen. A dolgozatban bemutatott algoritmusok ismertetéséhez azt az esetet kell csak vizsgálnunk, amikor b véges, a c célfüggvény pedig nemnegatív. 3.22

Állítás Ekkor a primál - duál optimalizálási feladatot megoldja a (31)-ben deniált (x̄, ȳ) pár. http://www.doksihu 3.3 Reszelés(Dilworth Truncation) 11 A mohó algoritmus alábbi változatát akkor is használhatjuk, ha a polimatroid/szubmoduláris poliéder nem a szubmoduláris határfüggvényével van megadva. A célfüggvény által meghatározott csökken® sorrendben végigmegyünk az elemeken, a soron lev® si elemhez tartozó komponens értékét pedig a lehet® legnagyobbra választjuk úgy, hogy létezzék a (x1 . xi yi+1 yn ) ∈ P(b)/S(b), ahol x1 . xk a már kiszámított elemeket jelöli. 3.23 Tétel Az algoritmus el®állítja a max{cxx ∈ P (b)} értéket Bizonyítás. Jelölje Si Jelölje megint x̄ az algoritmus által kiszámolt vektort, legyen x∈ tetsz®leges másik vektor. {s1 . sn }-t Nem nehéz belátni,hogy ekkor x̄(Si) ≥ x(Si ). Emiatt tetsz®leges célfüggvényre teljesül cx̄ − cx = X ((ci − ci+1

)(x̄(Si ) − x(Si )) + cn (x̄(Sn ) − x(Sn ))) > 0 i=1.n Megjegyzés.Az algoritmus implementálásához szükségünk van egy szubrutinra, ami kiszámolja a  α = min b(Z) − x(Z − si ) : si ∈ Z ⊆ S = max{θ : x + θsi ∈ P (b)} értéket. 3.3 Reszelés(Dilworth Truncation) A szakaszban ismertetjük a reszelés nev¶ konstrukciót, ami egy módszert ad a grakus szubmoduláris függvényminimalizálásra. 3.31 Deníció (Alsó reszelt) A b metsz®n szubmoduláris függvény alsó reszeltjén a b̄(Z) = min P (Z):P (Z)3Xi 6=∅,|P |≥1 t X (b(Xi )) i=i halmazfüggvényt értjük. Megjegyzés.b̄(Z) 3.31 Tétel ≤ b(Z)∀Z ⊆ S -re. . Legyen b metsz®n szubmoduláris Ekkor (Lovász 1977) b̄ szubmoduláris. Továbbá S(b)=S(b̄),azaz S(b) szubmoduláris poliéder, melynek határfüggvénye b̄. Bizonyítás. b̄ ≤b miatt Csak a második állítást bizonyítjuk. S(b̄) ⊆ S(b). x∈ S(b) esetén tetsz®leges Z⊆ b̄(Z) = X S -re vegyük azt

a partíciót, amire x(Zi ). Zi ∈Z Ekkor x(Z) = tehát S(b) ⊆ S(b̄). X x(Zi ) ≤ X b(Zi ) = b̄(Z), http://www.doksihu 3.3 Reszelés(Dilworth Truncation) 12 Frank és Tardos (1988) algoritmusa a polimatroid mohó algoritmust használva számítja ki a b metsz®n szubmoduláris függvény alsó reszeltjét. Az S(b) szubmoduláris poliéderen a P x(si) értéket maximalizáló mohó algoritmust alkalmazza.Ehhez szükség van egy szubrutinra, ami megadja az  α = min b(Z) − x(Z − si ) : si ∈ Z ⊆ S értéket és ezen felül a minimalizáló Zi ⊆ S halmazt. Jelölje x̄ azt a vektort, amit a mohó algoritmust számítja ki. Nevezzünk egy Z halmazt pontosnak, ha x̄(Z) = b(Z).Ekkor a Zi halmazok pontosak. 3.31 Állítás Metsz® pontos halmazok uniója pontos Bizonyítás. Legyenek A,B metsz®, pontos halmazok. b metsz® szubmodularitása miatt teljesül x̄(A) ≤ b(A), x̄(B) ≤ b(B) Így b(A) + bB = x̄(A) + x̄(B) = x̄(A ∪ B) + x̄(A ∩

B) ≤ b(A ∪ B) + b(A ∩ B) ≤ b(A) + b(B) A fenti egyenl®ségekb®l adódóan x̄(A ∪ B) = b(A ∪ B) Tekintsük a Zi halmazok által meghatározott hipergráf b̄(S) = , tehát az algoritmus valóban el®állítja a X x̄(Ti ) = b̄(S)-et X Ti komponenseit. Ezekre b(Ti ) megvalósító partíciót. Megmutatjuk, hogy az Optimális Kooperáció Feladatot megoldó partíció el®állíthatjuk a reszelési algoritmus segítségével. Legyen G=(V, E) tetsz®leges összefügg® gráf, S∈ (0,1)E , és F⊆E- re legyen χF (e) 1, ha e ∈ F, egyébként 0.Ekkor Edmonds egy tétele szerint az erd®knek megfelel® incidenciavektorok konvex burka egy polimatroid :  x ∈ RE : x(E(U )) ≤ |U | − cG (U ), c ≥ 0, (U ⊆ V (G)) , ahol E(U) azon élek halmazát jelölik, amelyek mindkét végpontja a U ⊆V halmazban van. 3.32 Tétel (Edmonds) Az  x ∈ RS : x ∈ P (b), x ≤ y rendszer polimatroidot határoz meg. x ≤ s feltételt a P(f ) polimatroidot

  w(U ) ha U = e f (U ) =  |U | − c (U ) egyébként Tehát az el®z® rendszerhez hozzávéve az G kapjuk, ahol http://www.doksihu 3.3 Reszelés(Dilworth Truncation) 13 3.32 Állítás f metsz®n szubmoduláris  Tehát a P(f ) poliéder h szubmoduláris határfüggvénye f alsó reszeltje : h(X) = min P (E) min V (P ) X X f (Ei ) = min V (P ) Ei ∈P {|Vi | − 1 − s(E(Vi )) + Vi ∈P X e∈E  X |Vi | − 1 + Vi ∈P V (P ) X Vi ∈P X s(e) = e6=E(V( i) s(e) = min {n − |P | − −(gG,s (P )) + n + X s(E(Vi ))} + X s(e) = e∈E s(e) e∈E Tehát a reszeltet kiszámító mohó algoritmus a futás végén el®állítja az Optimális Kooperáció Feladatot megoldó partíciót. http://www.doksihu 4. fejezet Algoritmusok 4.1 Cunningham algoritmusa Cunningham (1985) az Optimális Kooperáció Feladatot az ekvivalens Optimális Támadás alakban vizsgálta. Adott egy összefügg® hálózat, egyes éleinek ellenállóképességét az

s : E R0+ függvény határozza meg ( azaz a támadónak s(e) energiát kell befektetni e lerombolásához). Minden a hálózatból kiszakított komponens B érték¶ "jutalmat" kap.Tehát a  min s(A) + BcG (Ā) : A ⊆ E értéket megvalósító élhalmazt fogja lerombolni. A modell abban az esetben sem veszti értelmét, ha a támadónak nem célja a hálózat lerombolása, vagy akár nem is él® (mint például egy vezetéket támadó korrózió). Ugyanis a hálózat sebezhet®ségének vizsgálatához célszer¶ a legrosszabb esetet gyelembe venni, ami megfelel egy intelligens és rosszindulatú támadótól jöv® célzott támadásnak. Ebben a fejezetben csak a B=1 esettel foglalkozunk. Világos, hogy ekkor (az Optimális Kooperáció Feladathoz hasonlóan) feltehetjük, hogy s∈(0,1). Az is látszik, hogy az optimális élhalmaz E P Vi γ(Vi ) alakú,ahol  V1 . Vn V egy partíciója - tehát a feladat valóban ekvivalens az Optimális Kooperáció

Feladattal. A problémát a következ® alakban vizsgálhatjuk :  min s(A) + rG (Ā) . Legyen P (rG ) az a polimatroid, amit a gráf E élhalmaza és a grakus matroid rangfüggvénye deniálnak. 4.11 Állítás   min s(A) + rG (Ā) = max x(E) : x ∈ P (rG ), x ≤ s Bizonyítás. A max≤min irány könnyen látszik : x(E) = x(A) + x(Ā) ≤ s(A) + rG (Ā) 14 http://www.doksihu 4.2 Barahona algoritmusa A min 15 ≤ max irány igazolásához mutatunk egy A ⊆ E halmazt és x vektort,amire az egyenl®ség teljesül. Legyen x P (rG ) Egy A⊆E halmazt egy s-bázisa (azaz egy maximális pontosnak nevezünk, ha P (rG )-beli, x ≤ s feltételt teljesít® vektor). x(A) = rG (A). 4.12 Állítás Pontos halmazok uniója is pontos Bizonyítás. Legyen Ā a pontos halmazok uniója. Ekkor minden e∈E élre x(e)=s(e), vagy x∈ C ⊆E ,ahol C pontos(mivel különben x nem lenne maximális). Tehát x(E) = x(A) + x(Ā) = s(A) + rG (Ā) Tehát a  x ∈

RE : x ≥ 0; x(E) ⊆ rG (E), x(e) ≤ s(e) polimatroidon a P x(E) célfüggvényt optimalizáló algoritmus megoldja a feladatot :az Optimális Támadás Feladatot megoldó élhalmaz a pontos halmazok uniója, az Optimális Kooperációt megoldó élhalmaz pedig ennek komplementere lesz. Az algoritmus : Kezdetben x=0, Ā = ∅. Tetsz®leges sorrendben sorra vesszük az éleket. A j-edik lépés :  := minB⊆E {rG (B) − x(B) : j ∈ B ⊆ E} ha  ≤ s(j) − x(j) egyébként Ā := Ā ∪ Bj (Bj az -t minimalizáló halmaz)  := x(j) − s(j) x :=x+ej Az algoritmus futásideje : |E|, ezenkívül |E|-szer hívja meg a min {rG (B) − x(B) : j ∈ B ⊆ E} B⊆E értéket, és a minimalizáló halmazt megkeres® szubrutint. 4.2 Barahona algoritmusa Barahona (1992) algoritmusa a feladatot a |V | darab minimális vágás problémára vezeti vissza, ez jelent®s el®relépés (az algoritmus futásideje így egy nagyságrenddel kisebb.) Az algoritmus eredeti

változatában a gráf, amin minimális vágást keresünk, |V|+2 csúcsból áll. Barahona, Baoiu és Mahjoub (2002) módosították az algoritmust, ami így szintén |V | minimális vágás problémára vezeti vissza a problémát, de az i. lépésben csak i+2 csúcsú gráfon Itt ezt a javított verziót ismertetjük. Adott g=(V,E) gráfra, s∈(0,1) súlyfüggvény mellett legyen P(f ) az alábbi poliéder : y ∈ R|V | y(U ) ≤ f (U ) http://www.doksihu 4.2 Barahona algoritmusa 16   s(δ(U )) − 2 ha f (U ) =  s(δ(U )) ha r∈ /U r∈U 4.21 Állítás Az f metsz®n szubmoduláris 4.21 Tétel Vegyük a P(f)-en y(V)-t maximalizáló y vektort Az S⊆ V : y(S) = f (S) halmazok által meghatározott hipergráf komponensei adják meg az Optimális Kooperáció Feladatot megoldó partíciót. Bizonyítás. Jelölje f¯ az f alsó reszeltjét, ekkor max{y(V ) : y ∈ P (f )} = f¯(V ) = min X V (P ) min X  V( P ) f (Vi = s(δ(Vi ) − 2 + s(δ(Vj :

r ∈ Vj )) = Vi ∈V (P ):r ∈V / i  min 2(s(δ(V (P ))) − (p − 1)) V (P ) =  minV (P ) 2(x(E) − [2( P x(E(Vi )) + (p − 1)] ] Tehát a P(f )-en futó mohó algoritmus el®állítja a kívánt partíciót. Ezúttal is szükségünk van a α = minS⊆V,vk ∈S f (S) − x(S) értéket kiszámító szubrutinra, ezt egy hálózat minimális vágására vezethet® vissza. A hálózat konstrukciója a következ® : Legyen D=(N,A)irányított gráf, ahol N= V∪z,t, A=(i,j),(j,i)| ij∈ E η(i) := −ȳi i ∈ V-re, η(r) := −¯(r)+2 ha i 6= S V A következ® kapacitásokat deniáljuk : c(z, t) = η(i), c(z, i) = 0 ha c(z, i) = −η(i), c(i, t) = 0 ha η(i) ≥ 0, ik , i ∈ η(i) < 0, i= 6 vk , i∈ V c(z, vk ) = ∞, c(vk , t) = η(vk ) c(i, j) = c(j, i) = x̄(i, j), ij ∈ E -re 4.21 Lemma Legyen z ∪ T (z,t) vágás λ kapacitással Ekkor   λ+P η(v)<0 {η(v)} − 2 har ∈ T s(δ(T )) − ȳ =  λ+P har ∈ /T η(v)<0 {η(v)}

Bizonyítás. (z,i),(i,t)|i∈V. Legyen Legyen r∈T. Ekkor λ= X X {−η(i)} + x̄(δ(T )) + i∈T,η(i)<0 / i∈T,n(i)≥0 λ+ X η(v)<0 η(v) − 2 = η(i)} V http://www.doksihu 4.3 A Seb® -Preissmann algoritmus X 17 X η(i) + x̄(δ(T )) + i∈T,η(i)<0 −2 = i∈T,η(i)≥0 s(δ(T )) − ȳ(T ) β -val jelölve a minimális kapacitású (z,t) vágást α=2−β− X η(v) η(v)<0 4.22 Lemma Ha rendelkezésünkre áll a a G=(V,E) gráfnak megfelel® poliéderre a  max y(E) : y ∈ P (f )y ≤ s feladat megoldása, akkor egy új csúcsot a gráfhoz véve az így kapott G-re a megoldás visszavezethet® egy minimális vágás megkeresésére. A következ® fejezetben ismertetjük egy analóg állítás bizonyítását. A lemma következményeként a megoldás megkonstruálható kis csúcsszámú gráfból kiindulva és a megoldást lépésenként kiterjesztve, az i. lépésben i+2 csúcsból álló hálózati folyamot használva 4.3 A

Seb® -Preissmann algoritmus 4.31 A megoldás kiterjesztése Seb® és Preissmann algoritmusa szintén kis gráfból indul, és lépésenként terjeszti ki a megoldást. A Barahona-féle algoritmushoz hasonlóan egy olyan polimatroidon futó mohó algoritmuson alapul, amit csúcshalmazon értelmezett függvény deniál. Az eddigi algoritmusoktól eltér®en a gráfon végzett elemi lépésekb®l áll, a futásideje a legrosszabb esetben annyi, mint a Barahona -féle (javított) algoritmusé, de általában gyorsabb annál. Ez annak köszönhet®, hogy a futás közben egyes csúcsokat egymással azonosít (összehúzás), és így kisebb gráfon dolgozik tovább. Seb® és Preissmann külön algoritmust dolgozott ki egyes, az Optimális Kooperáció Feladatra visszavezethet® problémákra is, ezeket a következ® fejezetben be fogjuk mutatni, összevetve a problémákat megoldó régebbi algoritmusokkal. Az algoritmus részletes ismertetése el®tt új jelöléseket vezetünk be :

magát az Optimális Kooperáció Feladatot ezentúl (OC)-vel jelöljük.Láttuk, hogy a (OC) optimális megoldása a csúcsok egy partícióját határozza meg, jelölje F⊆E optimális megoldásra a megfelel® partíciót PF . 4.31 Lemma Legyen a G=(V,E) egy gráf, G=(V,E), ahol E⊆E tetsz®leges részhalmaza Enek Legyen F⊆ E(G) optimális megoldása (OC)-nek G-re Ekkor létezik (OC)-nek F minden élét tartalmazó optimális megoldása G-re. http://www.doksihu 4.3 A Seb® -Preissmann algoritmus Bizonyítás. Az fG,s 18 függvény szupermodularitása miatt teljesül fG,s (F ∪ F 0 ) + fG,s (F ∩ F 0 ) ≥ fG,s (F ) + fG,s (F 0 ) Mivel F maximalizálja az 0 F ⊆ E(G0 ), fG,s -et G-ben,és F∪F⊆E(G), illetve F maximalizálja fG,s -et G-ben és teljesülnek : f (F ∪ F 0 ) ≤ f (F ) f (F ∪ F 0 ) ≤ f (F 0 ) tehát a fenti egyenl®tlenségnek egyenl®séggel kell teljesülnie. 4.31 Állítás Legyen P V partíciója, W ⊆ P 0 tetsz®leges,P pedig a

P osztályainak egyesítésével keletkezett gráf (A többi osztály változatlan marad.)Ekkor g( P ) = gG (P 0 ) − (|W | − 1 − s(δ(W ))) valamint ha P optimális, akkor |W |−1−s(δ(W )) > 0, és ha P optimális, akkor |W |−1−s(δ(W )) ≤ ≤0 4.31 Tétel Legyen G=(V,E) gráf s súlyfüggvénnyel, legyen v egy tetsz®leges csúcs, jelölje G azt a gráfot, amit G-b®l kapunk v és a hozzá csatlakozó élek elhagyásával kapunk. Legyen F optimális megoldása (OC)-nek G-re, W* pedig az x∈ W ∈ PF 0 -ek közül az, amelyik minimalizálja az |W | − − 1 − s(δ(W ) értéket. Ekkor F*=F∪W optimális megoldása (OC)-nek G-re. Bizonyítás. éleit, és PF ∗ El®ször belátjuk, hogy létezik olyan F* fG -re elemei közül azok, amik nem tartalmazzák nek olyan részhalmaza, hogy  fG -re. {x}-et, elemei PF 0 -nek is. Legyen W PF 0 - ∪ i ∈ PF ∗ . Ha W nem tartalmazza {x}-et, akkor mivel F optimális fG0 -re, |W | − 1 − s(δ(W ))

≥ 0, F*δ(W ) is optimális optimális megoldás, ami tartalmazza F és mivel F* optimális Tehát a fG -re, |W | − 1 − s(δ(W )) = 0. {W : x ∈ W ⊆ P (F 0 )} halmazok közül a Ekkor viszont |W | − 1 − s(δ(W )) értéket minimalizáló W*-ra F∪δW optimális megoldás. Ezzel beláttuk, hogy a megoldás valóban kiterjeszthet® egy új csúcs hozzávételekor. Ekkor a |W | − 1 − s(δ(W ) érték nem függ attól, hogy a PF 0 osztályai milyen részgráfokat indukálnak, ezeket nem gyelembe véve kisebb gráfon való m¶veletetekkel megkapható a W*-ot megvalósító partíció. Ez adja a következ® deníció motivációját. 4.31 Deníció (gráf összehúzottja) Legyen a P={X1 Xn } a G=(V,E) gráf csúcshalmazának egy partíciója, legyen s egy súlyfüggvény a gráf élein.Ekkor az G gráf Gossz = (Vossz , Eossz ) gráfot értjük: Vossz = (xi . xk ), ahol 1 összehúzottján a következ® . k új csúcsokAz ossz : V ∪ ∪ E x1 .

k ∪ Eossz függvényt a következ®: v∈ Xi esetén össz(v)=xi , csak az olyan éleknek van képe, amelyek a, b végpontjai a partíció különböz® osztályaiba esnek, ezekre ossz(e) = = ossz(a)ossz(b), sossz (e) = s(e). Legyenek adottak a 4.11 Lemma feltételeiLegyenek {x, X1 . Xn }PF 0 osztályai. http://www.doksihu 4.3 A Seb® -Preissmann algoritmus 4.32 Állítás A 19 PF 0 partíció x-et tartalmazó részhalmazai és Gossz csúcsainak x-et tartalmazó részhalmazai között egy az egyhez megfelelés van. |W | − 1 − s(δ(W )) = |Wossz | − 1 − sossz (Eossz ∩ ∩ (Wossz XWossz ) és W akkor és csak akkor optimális, ha Wossz minimalizálja |Wossz | − 1 − − sossz (Eossz ∩ (Wossz XWossz )-t. 4.32 Hálózati folyam modell Adott G=(V,E) gráf és az éleken értelmezett s súlyfüggvény esetén legyen bG,s (H) = |H| − 1 − s(E(H)) . Az eddigiek alapján látszik, hogy az (OC) megoldó algoritmushoz elég egy szubrutint találni, ami megkeresi

a minH⊆V {bG,s (H) : u ∈ H} értéket minimalizáló csúcshalmazt. Erre Picard és Queyranne(1982) és Padberg és Wolsey (1983) direkt megoldást adtak, egy hálózati folyamon történ® minimális vágásra visszavezetve azt. A (D,c) hálózat megkonstruálása : INPUT :(G,s,u)) 1.V(D) :=V(G)∪{s, t} 1 2 2.E(H) minden uv éléhez felveszünk egy uv és egy vu élet,c(u,v)=c(v,u)= s(uv)Minden u∈ V(G)re felveszünk egy (s,u) és egy (v,s) élet 3.u∈V(G)-re legyen X p(u) = c((u, v)) = v∈V (G),uv∈E(G) és így c((s,u)) :=p(u), c((u,t)) :=1.Ekkor P 1 2 X s(uv), v∈V (G),uv∈E(G) u∈V(G)p(u) = s(E(G)). 4.32 Tétel Az S minimális u-t tartalmazó (s,t) vágásra a W*=Shalmaz minimalizálja b(W)-t minden u-t tartalmazó W-re. Bizonyítás. Azt fogjuk belátni, hogy a c(δ((s) ∪ W )) − bG,s érték nem függ W választásától. c(δ({s} ∪ W )) = |W | − s(E(W ))+ = b(W ) + c(δ(s)) + 1 ahol c(δ(s)) = s(E) Legyen el®ször konstans. W0 = ∅,

ekkor teljesül az egyenl®ség. Nézzük, hogy változik c(δ((s) ∪ W )) értéke W csúcsait hozzávéve. Egyrészt minden v csúcsra megjelenik c(v,t)=1 illetve elt¶nik a c(s,v)=p(v) érték.Ez összesen X v∈V 1 − p(v) = |W | − s(E(W )) − 1 2 X x,y∈E=(G),x∈G,y ∈G / s(x, y) http://www.doksihu 4.3 A Seb® -Preissmann algoritmus 20 A c(W, V) érték kezdetben 0, így a megváltozása : c(W, V ) = A c(δ({s} ∪ W )) érték a az eredeti 1 2 X s(x, y) x,y∈E=(G),x∈G,y ∈G / c(δ(s)-nek és c(δ((s) ∪ W )) megváltozásának összege, ami |W|-s(E(W)). Az algoritmust általánosíthatjuk arra az esetre, amikor b+m minimumát keressük, ahol m a csúcshalmaz tetsz®leges moduláris függvénye. Az m(W)=|W| ennek csak egy speciális esete A c(u,t)=m(u) változtatással adódó algoritmus megoldja az általános esetet. 4.33 Az algoritmus Összefoglalva az eddig leírtakat, a Seb®-Preissmann féle algoritmus a következ® lépésekb®l áll :

∅ Az =U⊆V halmazzal indul, erre a partíció P=∅.Az algoritmus a következ® 1-5 lépéseket ismételi n-szer egymás után : 1.Legyen u∈ V tetsz®leges. 2.Legyen H a P∈ G = (U ∪ u) osztályok összehúzásával kapott gráf, sH az ekkor kapott új súlyfüggvény. 3.A hálózati folyam algoritmus meghívása (H, Ez kiszámítja a W ∗ = {x1 , . xk } ⊆ V (H)-t, 4.Legyen R a következ® : sH , ahol u)-val. xi Xi ∈ P -nek felel meg. R := {u} ∪ {X1 ∪ . ∪ Xk 5.Legyenek most U és P a következ®k : := U ∪ {u}, P := (P {X1 . Xk }) ∪ {R}} 4.33 Tétel P* optimális partíció (G,w)-re. Bizonyítás. Kezdetben ∅ optimális megoldás az U=∅ által indukált gráfra. Tegyük fel, hogy az n. lépés kapott P partíció optimális az U által indukált gráfra Belátjuk, hogy az 1-5 lépések elvégzése után is optimális partíciót kapunk. Az u csúcs hozzávátelével (élek nélkül) kapott gráfra az P(U)∪u partíció

optimális. A 3 lépés után kapott tartalmazó részhalmaza, ami minimalizálja P partíció osztályainak a {u, X1 . k } P = (P {X1 . Xk }) ∪ {R}} bG,s -et. W ∗ = {u, x1 . xk } a H csúcsainak u-t Mivel (H,sH )-t (G,s) összehúzásával kaptuk, a részhalmaza minimalizálja a |W | − 1 − s(δ(w)) értéket. Tehát partíció optimális. Két megjegyzés : Az 1. lépésben u választása tetsz®leges, alkalmas megválasztása gyorsíthat az algoritmuson fG,s szupermodularitása miatt létezik egy egyértelm¶ minimális és egy egyértelm¶ maximális optimális megoldás. Ezeket úgy kaphatjuk meg, hogy a hálózati folyam algoritmus által megadott minimális vágások közül mindig a minimálisat (illetve maximálisat) választjuk. http://www.doksihu 4.3 A Seb® -Preissmann algoritmus 21 A Seb®-Preissmann algoritmus tehát |V|-1-szer hívja meg a Picard és Queyranne(1982) és Padberg és Wolsey (1983)-féle hálózati algoritmust, ezen kívül

|V|-1-szer hajt végre összehúzást a gráfon. Részben ez utóbbiank, részben a megoldás iterjesztésének köszönhet®en a hálózati folyam algoritmust kis csúcsszámú gráfokra hívja meg : az i. lépésben maximum i+2 csúcsból áll,a gráf a legtöbb esetben viszont kisebb ennél. http://www.doksihu 5. fejezet Alkalmazások 5.1 Optimális Növelés Feladat Az Optimális Kooperáció Feladat névadójaként bemutatott szituációt felidézve, tegyük fel, hogy egy kutatóintézet vezet®sége támogatni szeretné a kutatócsoport együttmaradását. Ezért hajlandóak egyes kutatópárosok együttm¶ködését külön honorálni.Az egyes együttm¶ködések egységnyi támogatásának költségét a k : E R+ függvény határozza meg, az u [s,1] függvény pedig fels® korlát az össztámogatás értékére. Egy(G,s) párt er®snek nevezünk, ha V optimális partíció (OC)-re. A feladat ekkor egy olyan s ≤ s0 ≤ u új súlyfüggvény találása,amire (G,s)

er®s, és ami minimalizálja a X k(e)(s(e) − s0 (e)) e∈E értéket. 5.11 Állítás V akkor és csak akkor optimális partíció (G,s)-re, ha a  polimatroidon a P e∈E x ∈ RE : x(E(U ) ≤ |U | − cG (U )) : ∀U ⊆ V, x ≤ s0 x(e) célfüggvényre az optimum értéke |V | − 1. Tekintsük a következ® segédgráfot : G minden élét cseréljük ki e és e* párhuzamos élekre. Legyen k(e0 ) := 0, s(e0 ) := s(e), k(e∗) := = k(e), s(e∗) := u(e) − s(e). Vegyük a segédgráfnak megfelel® polimatroidot :  x ∈ RE : x(U ) ≤ |U | − cG x ≤ s Alkalmazzuka mohó algoritmust a − X k(e)x(e) e∈E 22 http://www.doksihu 5.1 Optimális Növelés Feladat célfüggvény maximalizálására 23 ezen a polimatroidon. Mivel a E célfüggvény optimumának keresésekor tetsz®leges sorrendben haladhatunk az éleken, ez megoldja az utóbbi feladatot is. Ha az algoritmus futása végén a komponensek összege |V|-1, akkor legyen s(e) :=x(e*)

∀e ∈ E -re, ez megoldja az Optimális Növelés Feladatot. Ha a komponensek összege nem éri el a |V|-1-et, akkor a feladat nem megoldható. Bemutatjuk Seb® és Preissmann algoritmusát a problémára. Ez szubrutinként hsználja a 4.3 szakaszban ismertetett, az Optimális Kooperációt megoldó algoritmust, illetve a Picard és Queyranne(1982) és Padberg és Wolsey (1983)- féle hálózati folyam algoritmust. 0.Legyen el®ször s=s Legyen P optimális partíció P = {V } esetén készen vagyunk. P 6= V fG,s -re (az (OC) algortmus meghívása). 0 esetén készítsük el a (H, sH ) gráfot P osztályainak összehúzásával. Rögzítsük a P osztályain belül lév® éleket A már rögzített élek halmazát jelölje R 1.Legyen e H-nak a k(e) = minf ∈E(G),f ∈R / k(f ) értéket megvalósító éle. 2. Legyen s(e) értéke u(e) Legyen Se ⊆ V a bH,s0 = |W | − 1 − s0 (W ) értéket minimalizáló halmaz(a hálózati folyam algoritmus meghívása).Legyen

R=R∪{u} Se = {x} esetén : -ha minden él rögzített a G gráfban, akkor az algoritmus leáll. Ekkor s=u mellett nem V(H) az optimális partíció, így a feladat nem megoldható. -ha van nem rögzitett él, akkor ismételjük az algoritmust az 1.lépést®l Se 6= {x} esetén legyen -ha Se = V (H), -ha Se 6= V (H), s0 (e) = u(e) + bH,s0 készen vagyunk, a feladatot megoldja s. készítsük el az új H-t Se összehúzásával, rögzítsük a Se -n belüli éleket.Ismételjük meg az algoritmust az 1 lépést®l 5.11 Lemma Legyen G=(V,E) egy gráf, legyen ennek e tetsz®leges éleLegyenek s, s súlyfüggvények, amelyekre s(e)>s(e) és s(f)=s(f) ∀f 6= e-re.Legyen F⊆ E(G) optimális fG,s -re Ha e∈ F, akkor F fG,s0 -re is optimális. Ha e∈/ F , akkor a PF 0 partíció osztályainak részhalmazai közül vegyük azokat, amelyek tartalmazzák az x-et vagy az y-t tartalmazó osztályok közül legalább az egyiket. Az ilyen W részhalmazok közül a |W | − 1

− s0 (δ(W )) értéket minimalizáló W*-ra az F∪δ(W ∗) optimális fG,s0 -re. http://www.doksihu 5.2 A hálózat ellenállóképessége Bizonyítás. 24 Mivel a partíció értéke a súlyfüggvény változtatása után s(e)-s(e)- nél nagyobb értékkel nem változhat , az els® állítás teljesül.Az e∈ / F esetre az állítás következik a 4.31 tételb®l Tehát az e∈F élek az optimális megoldásnak megfelel® élhalmazban maradnak. 5.11 Következmény Az Se osztályainak összehúzása után kapott H gráfra a  {v} : v ∈ V (H) partíció optimális marad, miután egy él értékét u(e)-s(e)-el növeljük. 5.12 Következmény Az algoritmus futása során az 1 lépés megkezdésekor a triviális  {v} : : v ∈ V (H) partíció optimális a az aktuális (H,s) által meghatározott (OC) feladatra, és G ennek megfelel® partíciója is optimális az (G,s) által meghatározott (OC) feladatra. Tehát amennyiben a feladat megoldható, az algoritmus

megtalálja azt az s ≤ s0 ≤ u értéket, ami minimalizálja a k T (s0 − s) értéket. 5.2 A hálózat ellenállóképessége Cunningham(1985) vezette be a a gráf ellenállóképességének a fogalmát. Legyen G=(V,E) összefügg® gráf, élein adott egy s R függvény. Legyen megint adott egy intelligens támadó, akinek minden kiszakított komponens B érték¶ nyereséget jelent. Az e élet s(e) költséggel tudja lerombolni. 5.21 Deníció A hálózat ellenállóképességének ekkor a σ(G, s) = minA⊆G  s(A) cG (Ā) − 1 értéket nevezzük. Tehát a hálózat ellenállóképessége az a maximális B érték, ami mellett a támadó számára optimális magartartás, ha egyáltalán nem rombol le élt. 5.21 Állítás σ(G, s) ≤ B akkor és csak akkor, ha  minA⊆E s(A) − (B(cG (Ā) − 1)) = 0 Tegyük fel, hogy B ≥ σ .Ekkor ha min{(s(A) − B(cG − 1)(A)) : A ⊆ S}=0 készen vagyunk. Ha pedig A a (negatív) minimum, akkor a helyettesítve

ismételjük tovább az el®z® lépést, amíg nem kapunk. Ekkor σ ≤ s(A) cG (U )−1(A) akkor B ≤σ 0 b-t b-vel = b < b, min{(s(B) − b ∗ (cG − 1)(B)) : B ⊆ B}=0 σ = B∗. 5.22 Állítás Az algoritmus két egymás utáni lépésében a minimalizáló A halmazokra cG (Ai ) > cG (Ai+1 ) és -t http://www.doksihu 5.3 A hálózat optimális merevítése 25 Bizonyítás. 0 > (Ai+1 − bi+1 ((cG )(Ai+1 ) − 1) = s(Ai+1 ) − bi ((cG )(Ai+1 ) − 1) + bi ((cG (Ai+1 ) − 1) − bi+1 ((cG )(Ai+1 ) − 1) ≥ s(Ai ) − bi ((cG )(Ai ) − 1) + bi ((cG )(Ai+1 ) − 1) − bi+1 ((cG )(Ai+1 ) − 1) = cG (Ai+1 ) − cG (Ai )(bi+1 − bi ) Tehát az algoritmus legfeljebb |V| lépés után véget ér.Az egyes lépésekben egy általánosított Optimális Kooperáció Feladatot old meg. Seb® és Preissmann erre a problémára is kifejlesztettek egy algoritmust. Ez Cunninghaméhoz nagyon hasonlóan m¶ködik,szintén n Optimális Kooperáció Feladatot old

meg, viszont egyre kisebb gráfokon (az összehúzás m¶veletének köszönhet®en). 5.23 Állítás σ(G, s)=max{λ : (G, λs )er®s} 0. Legyen G=(V,E) gráf, optimális fG, σs -ra, így teljesül σ ellenállóképességgel , s súlyfüggvénnyel. az fG, n−1 s -et s(E) kapott gráf, σ= deníciója miatt V s(E) s(E) n−1 .Tehát ha a súlyok értékeit n−1 -el s(E) s(E) n−1 és készen vagyunk. Ellenkez® esetben σ = n−1 Jelöljük fG, σs (E) ≥ fG, σs (0), leosztva V optimális marad, akkor σ és σ≤ maximalizáló élhalmazt A-val. A6=E Legyen G a PA osztályainak összehúzásával σ (G)=σ (G). A 511Lemma miatt az el®z® lépést ismételve, A élei mindig az optimális megoldásban maradnak, így addig ismételjük az eljárást, amíg E nem lesz optimális. < |V (G)| |V (G0 )| < miatt az eljárás legfeljebb n Optimális Kooperáció Feladat megoldása után véget ér. A B6= 1 esetben az egyes lépések során az

általánosított Optimális Kooperáció Feladatot kell megoldanunk : X  max fG,w,B = BgG (A) + w(e), A ⊆ E(G) e∈A Ezt megoldhatjuk egyszer¶en azzal, hogy az éleket leosztjuk B-vel.Egy másik lehet®ség, hogy a hálózati folyam algoritmus általánosítását használjuk, az m(W ) = B|W | választással. 5.3 A hálózat optimális merevítése Az alapszituáció ugyanaz, mint az el®z® szakaszban. Adott továbbá egy c :E l :E R R, illetve függvény. c(e) az él s(e) ellenállóképességének egységnyi növelésével járó költség, l(e) pedig fels® korlát s(e)-re. Minimális költséggel szeretnénk elérni, hogy a σ (G,s) legalább σ0 legyen. Vegyük a következ® Optimális Növelés Feladatot : legyen G=(V,E), a súlyfüggvényt jelölje most w. w= s σ0 A költségfüggvény legyen c, a fels® korlát pedig σ0 . 5.31 Állítás A fenti Optimális Növelés Problémát megoldó w súlyfüggvényre s= wσ0 megoldja az eredeti feladatot.

http://www.doksihu 5.4 A Potts modell 26 5.4 A Potts modell A Potts modell szilártestek mágneses tulajdonságainak számítására alkalmazott statisztikus zikai modell. Az egyes spineket egy n dimenziós rács rácspontjaihoz rendeli, és az egyes rácspontokon lév® σ1 . σn spinek egy adott Zq := 0 . q − 1, q ∈ halmazból vehetik fel az értékeiket. A szomszédos rácspontok között van kölcsönhatás, ezt kötéseknek nevezzükA spinek számát jelölje n, a kötésekét m. A rendszer energiája (az ún Hamiltin függvénye) (σ1 ; σn )(n∈ ∈ N) állapot esetén E(σ) = X Ki, jδσi ,σj i,j ahol a kötésekre összegzünk, (1, ha a=b és 0, ha a6= σi ∈ Zq , a Kij ∈ R+ a kötés er®ssége , és δab a Kronecker- szimbólum b). A rendszer partíciós függvénye egy fontos mennyiség, amely meghatározza a termodinamikai egyensúlyban lév® rendszer statisztikai tulajdonságait.A függvénnyel vagy deriváltjaival kifejezhet®

például a rendszer nyomása, entrópiája vagy szabadenergiája -utóbbiról megmutatjuk, hogy egy szubmoduláris függvény. A partíciós függvényt Z-vel jelölve Z= X exp(Eσ) = XY σ σ e Kijδσ i σj ij , ahol a kötések szerint összegzünk, a szorzat tényez®it pedig a lehetséges (σ1 határozzák meg. δ ∈ 0,1-ekre Y Kδ = 1 + (eK − 1)δ eKij δσi σj = ij vi,j = eKi,j − 1 A . σn) jelölést bevezetve : Y XY (1 + (eKij −1)δσi σj )) = vij δσi σj ij L ij∈L ahol a lehetséges kötések halmazaira összegzünk. Tehát Z= XX Y σ vij δσi σj = XX Y L ij∈L L vij δσi σj = σ ij∈L L ,ahol c(L) L összefügg® komponenseinek a számát jelöli. Vezessük be az αij új változókat, legyen vij = g αij Ekkor Z= X P q c(L)+ ij∈L αij L Vezessük be az f függvényt, melyre f (L) = c(L) + X ij∈L X αij q c(L) Y ij∈L vij tényez®k http://www.doksihu 5.5 Feladat 27 Így Z= X q f (L) L

q∞ esetén (ekkor ferromágneses nagy q-állapotú rendszerr®l beszélünk) Z nagyságrendjét az F0 = maxU ⊆E F (U ) érték határozza meg. A rendszer szabadenergiája pedig konstansszor ennek -1 -szerese, ami a kötési energiából és az összefügg® komponensek száma által meghatározott h®energiából áll össze. A rendszer tehát megfeleltethet® egy olyan Optimális Kooperáció Feladatnak, ahol az egyedek a párkölcsönhatásból és a h®mérsékletb®l adódó bevételek maximalizálásával igyekeznek megtalálni a számukra optimális kongurációt. 5.5 Feladat Végül a dolgozatban bemutatott módszerek segítségével kétféleképp bizonyítjuk az alábbi állítást : 5.51 Állítás Legyen G=(V,E) tetsz®leges gráf Ekkor minden k-ra létezik a csúcsoknak egy olyan P1 . Pn partíciója, hogy az osztályokon belül létezik k diszjunkt feszít®fa és az osztályok összehúzásával keletkezett gráf fedhet® k erd®vel. 5.51 Matroid metszet

algoritmussal A matroidokkal kapcsolatos alapvet® fogalmakat ismertnek vesszük. 5.51 Tétel Legyenek M1 . Mk az S közös alaphalmazok adott matroidok Ekkor összegük is matroidot alkot, az ∪Mi rangja X minX⊆S { ri + |X − S|} Edmonds partíciós algoritmusa konstruktív bizonyítást nyújt a tételre : a futás végén megad F1 , . Fk halmazokat úgy, hogy E = X ∪ (∪Fi ) és Fi ∩ X Fi feszíti X-et független Mi -ben , valamint egy X halmazt úgy, hogy Mi -ben. 5.52 Tétel Adott egy S alaphalmazon két matroid A független halmazok összességét jelölje I1 és 2 . Ekkor max{|J| : J ∈ I1 ∩ I2 } = minX⊆S (r1 (X) + r2 (S − X)) Az M1 és M2 maximális elemszámú közös független halmazának keresése az M1 és M2 ∗(ahol M2 ∗M2 duálisa) olyan bázisának a keresésével ekvivalens, amelyek egyesítése maximális elemszámú. A partíciós algoritmus tehát kiszámítja a két matroidban maximális közös független halmazt.

http://www.doksihu 5.5 Feladat 28 (Emlékeztet®ül : A partíciós algoritmus általánosításának tekinthet® Cunningham-féle algoritmus a max{x(E) = minA⊆E s(A) + rG (Ā)} egyenl®ségen alapult. Térjünk vissza a feladatra. Legyen az alaphalmaz az élek halmaza, vegyük ezen k darab körmatroid unióját. A matroid metszet algoritmus megad egy X és mindegyik Fi feszíti Fi halmazokat, utóbbiak függetlenek egy körmatroidban, és X ∩ Fi -t. Ez pont annak felel meg, hogy X minden összefügg® komponensében van k diszjunkt feszít®fa. Az E halmaz pedig el®áll a k darab, egyenként egy körmatroidban független halmaz uniójaként,tehát fedhet® k darab erd®vel. Még be kell látnunk, hogy a gráf összehúzottja is fedhet® k erd®vel. 5.51 Deníció . Legyen az S alaphalmazon adott egy matroid, aminek (Matroid összehúzottja) a rangfüggvénye r, legyen Z ennek valódi, nemüres részhalmaza. M 0 az M-b®l Z összehúzásával összehúzásával

keletkezett matroid, ha alaphalmaza S , rangfüggvénye pedig r0 = r(X ∪ Z) − r(Z). 5.53 Tétel A következ®k ekvivalensek: 1.F⊆S független M-ben 2.Létezik Z-nek egy I maximális M-ben független részhalmaza, amire I ∪ F független M-ben Tekintsük az M=M matroidot (ahol M=∪(Mi )). Azt kell belátnunk, hogy F(ahol F=∪Fi ) független M-ben, ez pedig teljesül a fenti tétel miatt (az I =X ∩F választással.) Tehát az összehúzás után a gráf valóban fedhet® k erd®vel. 5.52 Visszavezetése az Optimális Kooperáció Feladatra 5.54 Tétel . Egy G=(V,E) irányítatlan gráf akkor és csak akkor fedhet® k (Nash- Williams) erd®vel, ha minden ∅ 6= X ⊆ V részhalmazra e(X) ≤ k(|X| − 1) 5.55 Tétel . Egy G=(V,E) irányítatlan gráfban akkor és csak akkor van k élidegen (Tutte) feszít®fa, ha V minden 1 . Vi partíciójára (P)≥ k(t − 1)ahol e(P) a partíció osztályai között men® élek számát jelöli. Nézzük az Optimális

Kooperáció Feladatot a G gráfra, s= 1 k súlyfüggvény mellett. Ekkor egy optimális partíciót véve mindkét tétel feltétele teljesül. (Láttuk, a Nash-Willams tétel feltételének teljesülése esetén a gráf összehúzottja is fedhet® k erd®vel). Nézzük a G-b®l a partíció osztályainak http://www.doksihu 5.5 Feladat 29 összehúzásával kapott gráfot. Tegyük fel, hogy létezik olyan 0 X ⊆ Vossz csúcshalmaz, hogy e|X| > > k(|X| − 1).Ekkor |X| − 1 − s(δ(X)) > |X| − 1 − 1 k(|X| − 1) > 0 k miatt nem teljesül az optimalitási feltétel a partícióra, ellentmondást kapunk. A Tutte- tétel feltételének igazolásához tegyük fel, hogy létezik az optimális partíciónak olyan osztálya, amelyet tudunk úgy tovább partícionálni, hogy − e(X) k1 > t − 1 − t − 1 > 0 jutunk.  e(X) < k(t − 1). Ekkor viszont t−1− miatt a partíció nem lehet opimális, így megint ellentmondáshoz

http://www.doksihu Irodalomjegyzék [1] Seb®,A.,Preissmann,M, Applications Graphic Submodular Function Minimization:a Graphic Approach and Research Trends in Combinatorial Optimization.Springer, Berlin 2009 Optmal [2] William H.Cunningham, Attack and reinforcement of a network J.AssocComputhMath32(3),549-561(1985) [3] Baiou, M., Barahona,F Mahjoub,A.R Separation of partition inequalities, Math.OperRes25(2),243-254(2000) Generalized polymatroids and submodular ows, [4] Frank,A., Tardos, É, Math.Program42, 489- 563(1988) [5] Juhász,R.,Rieger,H,Iglói,F The random bond Potts model in the large-q limit,Phys.RevE 64,56122(2001) [6] Edmonds,J. : [7] A. Frank, Matroids and the greedy algorithm, Math. Program 1,127-136(1971) Poliéderes kombinatorika, egyetemi jegyzet [8] A.Frank, 30