Matematika | Felsőoktatás » Pap Júlia - Stabilpárosítások struktúrája és poliéderei

http://www.doksihu Stabil p aros t asok strukt ur aja  es poli ederei SZAKDOLGOZAT K esz tette: Pap J ulia T emavezet} o: Frank Andr as egyetemi tan ar 2005. http://www.doksihu Tartalomjegyz ek 1. Bevezet} o 3 2. Alaptulajdons agok 4 2.1 A stabil parostasok halostrukturaja 5 2.2 Halmazrendszerrel valo reprezentalas 6 3. Rot a i ok 8 3.1 De n io, tuljadonsagok 8 3.2 Reszbenrendezes a rota iokon 10 4. Algoritmusok 4.1 4.2 4.3 4.4 13 Minimalis sulyu stabil parostas keresese . A rota iok megkeresese . Minimalis sulyu stabil parostas keresese rota iok segtsegevel . Minimalis sulyu stabil parostas kotelez}o es kizart elekkel . 5. Poli ederes eredm enyek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 14 14 14 16

5.1 Poliederes lerasok 16 5.2 TDI-sag 17 6. Egy alkalmaz as: Galvin t etele 24 7. Stabil p aros t asok tetsz} oleges gr afban 25 7.1 Stabil parostast keres}o algoritmus 25 7.2 A minimalis sulyu stabil parostas NP-teljes 27 8. Egy eb  altal anos t asok 29 8.1 Stabil b-parostasok 29 8.2 Matroid-kernelek 29 8.3 Graf-kernelek 29 2 http://www.doksihu 1. Bevezet} o A stabil parostas fogalmat Gale es Shapley vezette be [10℄-ben, am stabil parostast keres}o algoritmust mar korabban, 1951 ota hasznaltak az Egyesult A llamokban korhazak es rezidensek osszeparostasara. Gale es Shapley ikke felkeltette a kutatok erdekl}odeset, bar a temat eleinte f}oleg jatekelmeleszek es kozgazdaszok

vizsgaltak. Ebben a dolgozatban tisztan kombinatorikus szemszogb}ol tekintjuk a problemat. A dolgozat f}o eredmenye az 513 tetel illetve annak az 5.21 kovetkezmenye, ami a stabil parostasok poliederenek Rothblum altal adott lerasanak TDI-sagat bizonytja. Ezen kvul Gus eld es Irving 200 oldalas [12℄ konyvenek es mas ikkeknek szamos eredmenyet tartalmazza, egyszer}ustve. Koszonom temavezet}omnek, Frank Andrasnak a sok segtseget es turelmet, Kiraly Tamasnak es Fleiner Tamasnak a sok hasznos tana sot, Kiraly Tamasnak az 5.21 tetel bizonytasahoz az eszreveteleit. 3 http://www.doksihu 2. Alaptula jdons agok Legyen G = (U; V ; E ) egy tetsz}oleges paros graf, es minden v 2 U [ V pontra <v egy teljes rendezes a v-re illeszked}o elek halmazan, D(v)-n. Ezen rendezesek halmazat jeloljuk O-val, a (G; O) part nevezzuk paros preferen iarendszernek. Jeloljuk e 6v f -fel, ha e <v f vagy e = f Ha e <v f ,

akkor azt mondjuk, hogy az e el jobb a v pontban, mint f . e <V f -en azt ertjuk, hogy e-nek es f -nek van egy kozos, V -beli su sa, aminel az e el jobb. Az e el dominalja az f elt a v su snal, ha v kozos vegpontjuk, amire e 6v f . Ha az M elhalmaz egyik eleme sem dominalja az e elt, akkor e blokkolja M -et. Egy M parostast nak nevezunk, ha nin s olyan el, ami blokkolja M -et, vagyis M az osszes elt dominalja. Spe ialisan minden stabil parostas tartalmazasra nezve maximalis parostas. Az abrakban e <v f -et ugy fogjuk jelolni, hogy az f elt}ol egy nyilat rajzolunk az e elhez. stabil p aros t as 2.1 Lemma: Tetsz}oleges paros grafban minden stabil parostas ugyanazt a ponthalmazt fedi. Tegyuk fel, hogy van ket stabil parostas, M es N , amik nem ugyanazt a ponthalmazt fedik. Ekkor az M 4N szimmetrikus di eren iajukban van egy v ; e ; v ; e ; : : : ; ej ; vj ut, mondjuk e 2 M . Az e elt N -b}ol sak az e el tudja

dominalni, ezert e <v2 e Ha ei <v ei , akkor ei -t N es M kozul az }ot nem tartalmazo stabil parostas sak az ei ellel tudja dominalni, ezert ei <v +1 ei . Ezert ej <v ej , de akkor az ej elt az }ot nem tartalmazo stabil parostas nem dominalja, ami ellentmondas.  Bizony t as: 1 1 i 1 2 1 2 2 2 1 +1 1 +1 +1 i 2.2 T etel: (Gale, Shapley, [10℄) j 1 Minden paros grafban barmely preferen iarendszerhez le- tezik stabil parostas. Gale es Shapley egy algoritmust adtak, ami talal egy stabil parostast. Legyen G = (U; V ; E ) paros graf, U a uk, V a lanyok, E pedig a lehetseges hazassagok halmaza. Minden u uhoz rendeljunk egy L(u) listat, amin kezdetben az osszes u-val osszekotott lany szerepel, a 6u szerinti novekv}o sorrendben. Legyen M az aktualis parostas, kezdetben M = ; Legyen u 2 U egy olyan u, aki M -ben nin s parostva , es L(u) 6= ;. Legyen L(u)-ban az els}o lany v. Ha v fedetlen M

-ben, akkor legyen M := M [ f(u; v)g Ha (u0; v) 2 M , es (u; v) <v (u0; v), akkor M := M n f(u0; v)g [ f(u; v)g (vagyis a v lany ,,elutastja" az u0 ut), es L(u0 ) := L(u0 ) nfv g. Ha pedig (u; v ) >v (u0; v ), akkor L(u) := L(u) nfv g, M valtozatlan (vagyis v elutastja u-t). Ha mar nin s parostatlan u, akinek a listajan lenne lany, az algoritmus megall, az output az aktualis M . Figyeljuk meg, hogy ha egy lany az algoritmus soran valamikor van parja M -ben, akkor utana mindig lesz, es szamara egyre jobb tarsa lesz. Az algoritmus veget er, mert minden lepesnel vagy M merete n}o, vagy a listak osszhossza sokken, es M merete nem valtozik. Az algoritmus stabil parostast talal, mert ha (u; v) 2 E n M , akkor vagy v elutastotta u-t, ekkor az v lanynak u-nal jobb tarsa van M -ben, vagy L(u)-ben az algoritmus vegen meg benne van l, ekkor u-nek lett v-nel jobb tarsa, vagyis az (u; v) el mindenkepp dominalva van.  Bizony t

as: 4 http://www.doksihu Be fogjuk latni, hogy a fenti Gale-Shapley algoritmus mindig ugyanazt a stabil parostast adja, fuggetlenul az u 2 U valasztasatol, meghozza egy eleg spe ialis stabil parostast. 2.1 A stabil parostasok halostrukturaja Legyen G = (U; V ; E ) egy paros graf, es O egy preferen iarendszer G-n. Legyen M es N ket stabil parostas. A 21 lemma miatt M es N uniojaban sak kozos elek es (paros hosszu) korok vannak. Legyen v 2 U [ V Jeloljuk maxv (M; N )-nel a v-re illeszked}o M -beli es N -beli elek kozul a 6v rendezes szerinti nagyobbikat, minv (M; N ) pedig a kisebbiket (ha ugyanaz a ket el, akkor mindkett}o ez a kozos el, ha v-t nem fedik a stabil parostasok, akkor legyen mindkett}o ;). Legyen M ^ N := fminu(M; N )ju 2 U g, es M N := fmaxu(M; N )ju 2 U g M N es M ^ N stabil parostasok. 2.3 Lemma: Legyen v ; e ; v ; e ; : : : ; v k ; e k ; v egy kor M 4N -ben, ahol a paratlan index}u elek

az M -beliek, a paros index}uek az N -beliek, a pontok kozul a paratlan index}uek az U beliek, a paros index}uek az V -beliek. Tegyuk fel, hogy e k >v1 e Ekkor e -et N -b}ol sak e tudja dominalni, vagyis e >v2 e , es induk ioval ei >v +1 ei . Emiatt a korb}ol pont az M beliek vannak M ^ N -ben, es az N -beliek vannak M N -ben Ebb}ol latszik, hogy mindkett}o parostas, es hogy v 2 V -re M N -ben az M es N -beli elek kozul a 6v rendezes szerinti kisebbik el van, M ^ N -ben pedig a nagyobbik, fordtva, mint az U -beli su soknal. Most tegyuk fel, hogy van egy (u; v) el, ami bokkolja M ^ N -et, ahol u 2 U , v 2 V . Ekkor u-nal se M , se N nem dominalja az (u; v) elt, mert akkor M ^ N is dominalna. De akkor mindkett}o a v su snal dominalja az (u; v) elt, ami miatt M ^ N is dominalja a v su snal, ez ellentmondas. M N stabilitasat ugyangy be lehet latni, U es L fel serelesevel.  Jeloljuk M-mel a stabil parostasok

halmazat. M a es ^ m}uveletekkel disztributv halot alkot, vagyis barmely M ; M ; M 2 M-re teljesul, hogy: Bizony t as: 1 1 2 2 2 2 1 2 1 2 i 1 1 2 +1 2.4 T etel: (Conway) 1 2      3 M1 M1 = M1 ^ M1 = M1 (idempoten ia); M1 M2 = M2 M1 ; M1 ^ M2 = M2 ^ M1 (kommutativitas); M1 (M2 M3 ) = (M1 M2 ) M3 ; M1 ^ (M2 ^ M3 ) = (M1 ^ M2 ) ^ M3 (asszo iativitas); (M M ) ^ M = (M ^ M ) M = M (elnyelesi tulajdonsag); (M M ) ^ M = (M ^ M ) (M ^ M ); (M ^ M ) M = (M M ) ^ (M M ) (disztributivitas): 1 2 1 1 2 1 1 1 2 3 1 3 1 3 1 2 3 1 3 1 3 Ezek a tulajdonsagok konnyen kovetkeznek abbol, hogy az egy su sra illeszked}o eleken a rendezes szerinti min es max m}uveletekre teljesulnek.  Bizony t as: 5 http://www.doksihu A (M; ; ^) halohoz tartozik egy reszbenrendezes M-en, jeloljuk -vel, amire M  N , M N = N . Ez a stabil parostasok eseteben azt jelenti, hogy M  N pontosan akkor, ha

minden unal az M -beli el a jobb, mint az N -beli. Ekkor azt mondjuk, hogy M dominalja N -et. Ekkor a fentiek alapjan a lanyoknal pedig az N -beli el a jobb Mivel M halot alkot a fenti ket m}uvelettel, ezert a  reszbenrendezes szerint van egy egyertelm}u minimalis es egy egyertelm}u maximalis elem. A minimalis elemet jeloljuk MU val, a maximalisat pedig MV -vel MU -t nevezzuk uoptimalis stabil parostasnak, MV -t pedig lanyoptimalis stabil parostasnak. A fentiekb}ol kovetkezik, hogy MU -ban minden u a szamara legjobb part kapja, akivel egyaltalan ossze lehet parostva stabil parostasban, MV -ben viszont kozuluk a legrosszabbat, a lanyoknak viszont pont fordtva, MU -ban van a lehet}o legrosszabb parjuk, MV -ben a lehet}o legjobb. A Gale-Shapley algoritmus a uoptimalis stabil parostast talalja meg, akarmilyen sorrendben is valasztjuk kozben a parostatlan ukat.  t 2.5 All as: (Gale, Shapley) Legyen M az

algoritmus egy vegrehajtasa altal kapott stabil parostas. Tegyuk fel, hogy van egy M 0 stabil parostas, aminel valamelyik unak jobb partnere van, mint M -ben. Az ilyen ukat az algoritmus soran elutastotta az M 0 -beli partneruk. Legyen v az els}o lany, aki az M 0 -beli partneret, u-et elutastja, es legyen u0, aki miatt elutastotta. Tehat (u; v) 2 M 0 , es (u; v) >v (u0; v). Az v valasztasa miatt u0-t nem utastotta el az M 0 -beli partnere (ha van), vagyis az u0 su snal az (u0; v) elnel jobb elek nem M 0 -beliek. De akkor az (u0; v) el blokkolja M 0 -t, ami ellentmondas.  Persze ha az algoritmusban fel sereljuk a uk es a lanyok szerepet, akkor egy olyan algoritmust kapunk, ami a lanyoptimalis stabil parostast talalja meg. Bizony t as: 2.2 Halmazrendszerrel valo reprezentalas Az alabbiak Gus eld es Irving [12℄ atfogogo konyveben talalhatok. A Stone tetel alapjan a (M; ; ^) disztributv halo izomorf egy

metszet- es uniozart halmazrenszerrel, vagyis egy halmazgy}ur}uvel, amin a ket halom}uvelet a metszet es az unio. Meg is tudunk adni egy ilyen halmazgy}ur}ut a kovetkez}okepp. Legyen a halmazrenszer alaphalmaza a graf elhalmaza, E Minden M stabil parostashoz rendeljuk hozza azon elek halmazat, amik az U -beli vegpontjuknal dominaljak az arra illeszked}o M -beli elt: H (M ) := fe 2 E : 9m 2 M es u 2 U; hogy e 6u mg: Ekkor konny}u latni, hogy H (M N ) = H (M ) [ H (N ) es H (M ^ N ) = H (M ) H (N ), vagyis a H = fH (M ) : M 2 Mg halmazrendszer az [ es m}uveletekkel izomorf a (M; ; ^) haloval. Az H halmaz felel meg MU -nak, [H pedig MV -nek. Az elek kozt ertelmezhetunk egy ekvivalen iarela iot ugy, hogy ket elt ekvivalensnek mondunk, ha ugyanazokban a H-beli halmazokban vannak benne. Az ekvivalen iaosztalyokat a 6 http://www.doksihu H halmazrendszer atomjainak nevezzuk. Jeloljuk A-val az atomok halmazat, kiveve H-t es ([H) -t. Egy

haloban vagy halmazrendszerben vagy reszbenrendezett halmazban nevezzunk ket elemet szomszedosnak, ha nin sen szigoruan koztuk lev}o elem. Egy elhalmaz pontosan akkor van A-ban , ha el}oall ket szomszedos H-beli halmaz kulonbsegekent.  t 2.6 All as: Legyen A 2 A, es H (A) := fH 2 H : A  H g Eleg lenne belatnunk, hogy H (A)nA 2 H. El}oszor lassuk be, hogy ez a fuggveny injektv Ha A ; A 2 A kulonboz}ok, akkor van olyan H 2 H, ami elvalasztja }oket, mondjuk A  H , A  H . Emiatt H (A )  H , vagyis nem tartalmazhatja A -t, tehat H (A ) 6= H (A ). Most legyen A0  H (A) A-tol kulonboz}o atom, ekkor H (A0)  H (A), es H (A0) nem tartalmazhatja A-t, mert akkor H (A)  H (A0) is lenne, de H (A) 6= H (A0). Emiatt H (A) n A = [fH (A0) : A0  H (A)g, ami H-beli  Legyen A  A , ha H (A )  H (A ). Ez azzal ekvivalens, hogy A  H (A ), ami pedig azzal, hogy nin s olyan H 2 H, hogy A  H , de A H = ; Egy reszbenrendezett halmaz reszhalmazat

nevezzuk zartnak, ha barmely elemenel kisebb elemek is benne vannak a reszhalmazban. Bizony t as: 1 1 2 1 2 1 1 2 2 1 2 2 1 2 2 1 A H 7! fA 2 A : A  H g megfeleltetes bijek io a reszbenrendezett halmaz zart reszhalmazai kozt.  t 2.7 All as: H halmazgy}ur}u es az (A; ) El}oszor lassuk be, hogy fA 2 A : A  H g zart. Mivel A  A azzal ekvivalens, hogy nin s olyan H-beli halmaz, ami A -t tartalmazza, de A -et nem, ezert ha A  H es A0  A, akkor A0  H , tehat tenyleg zart a halmaz. A fuggveny nyilvan injektv, tehat mar sak azt kell belatni, hogy szurjektv, vagyis ha A0  A zart halmaz, akkor H = ([fA 2 A0g) [ (H) 2 H. Mivel A0 zart, ezert minden A 2 A0-re H (A)  H , ezert H = [fH (A) : A 2 A0g, ami H-beli.  Bizony t as: 1 2 1 7 2 http://www.doksihu V 8v0 sM (u) U u 1. abra sM (u) de n ioja 3. Rot a i ok Az itt lert eredmenyek szinten megtalalhatok Gus eld es Irving [12℄ konyveben, es

Gus eld; Irving es Leather ilettve harmojuk kozos ikkeben jelentek meg. 3.1 De n io, tuljadonsagok Legyen M 2 M egy stabil parostas, es u 2 U egy fedett pont. Jeloljuk sM (u)-val azt a V -beli v pontot (ha van), amire teljesul, hogy <v szerint az (u; v ) el kisebb (vagyis jobb), mint a v -re illeszked}o M -beli el (ebb}ol kovetkezik, hogy <u szerint az u-ra illeszked}o M -beli el kisebb, mint (u; v)), es ha (v0; u) <u (v; u), akkor v0-t fedi M , es <v szerint a v0-re illeszked}o M -beli el kisebb vagy egyenl}o, mint (u; v0). 0 Ha egy (u; v ) el a <u rendezesben az (u; sM (u) es az u-t fed}o M -beli el kozt van valamely M -re, akkor nin s benne stabil parostasban.  t 3.1 All as: Azert nin s, mert ket M -beli el is dominalja.  Az ilyen eleket nevezzuk u-nal koztes eleknek. Egy  = (v ; u ; v ; u ; : : : vk ; uk ) kort nevezzunk nak, ha van olyan M stabil parostas, amire (vi; ui) 2 M es vi = sM (ui) minden i = 1; 2;

: : : k-ra (ahol vk = v ). Ha egy  rota iora es egy M stabil parostasra teljesulnek ezek, akkor azt mondjuk, hogy  eliminalhato M -ben. Ekkor legyen M= := M nf(vi ; ui) : i = 1; 2; :::kg[f(ui; vi ) : i = 1; 2; :::kg, ezt M -b}ol  eliminalasaval kapjuk. Az (ui; vi ) eleket nevezzuk -n bekerul}o eleknek, a (vi ; ui ) eleket pedig kikerul}o eleknek, tehat a rota io egy U -beli pontjanal a kikerul}o el a jobbik, egy V -beli pontnal pedig a bekerul}o. Bizony t as: 1 1 2 rot a i o 2 +1 +1 1 +1 +1  t 3.2 All as: M= stabil parostas, M  M= es M es M= szomszedosak. Mivel egy alternalo koron sereltunk, ezert M= parostas. A V -beli su sokra legalabb olyan jo elek illeszkednek M=-ban, mint M -ben, ezert eleg megnezni, hogy M= az olyan eleket dominalja-e, amiket M az U -beli vegpontjukban dominal. De sM de n ioja miatt Bizony t as: 8 http://www.doksihu az ilyen elek kozul azokat, amiket M= nem

dominal az U -beli vegpontjukban, M a V -beli vegpontjukban is dominalja, tehat ott M= is, vagyis M= stabil parostas. Nyilvan M  M=. Mivel koztes elek nin senek stabil parostasban, ezert ha lenne a ket stabil parostas kozt egy harmadik a  rendezesben, az sak M [ M=-beli eleket hasznalhatna, de ebben sak egy kor van a kulonallo eleken kvul, ezert nin s harmadik parostas benne, ami ugyanazt a ponthalmazt fedi.  Ha M  M 0 es a v 2 V su sra illeszked}o M es M 0 -beli elek kulonboznek, akkor  t 3.3 All as: 1 ha v1 -b}ol kiindulunk, es felvaltva a soron kovetkez}o pontot fed}o M -beli el masik vegpontjaba (ha V -beli a pont), illetve a pont sM -jebe (ha U -beli a pont) lepunk amg vissza nem erunk egy korabban latogatott vi pontba, akkor a seta vi -ig men}o reszet elhagyva megkapunk egy  rota iot, amire M=  M 0 . Legyen ui a vi M -beli parja es vi = sM (ui). Ahhoz, hogy eljussunk egy rota iohoz, az kell,

hogy az sM minden ui-ben de nialva legyen, mert ha nem akadunk el, akkor el}obb-utobb egy olyan ponthoz erunk, ahol mar jartunk, es ekkor egy rota iot kapunk. El}oszor lassuk be, hogy sM (u ) ertelmezve van. Legyen az u -re illeszked}o M 0 -beli el (u ; v) Mivel (u ; v ) 6u1 (u ; v) es M stabil parostas, ezert v-nel az M -beli el jobb, mint az (u ; v) el. Mivel nin s olyan u rendezeseben (u ; v)-nel jobb el, aminek masik vegpontjat nem fedik a stabil parostasok, ezert az ilyen tulajdonsagu elek kozul a legjobb lesz sM (u ). Masreszt lassuk be, hogy az a tulajdonsag, hogy egy u pontra illeszked}o M es M 0 -beli elek kulonboznek, orokl}odik sM (u) M -beli parjara is. Legyen ez a pont u0 Ha (u0; sM (u) 2 M 0 M lenne, akkor az (u; sM (u)) elt M 0 nem dominalna. Tehat sosem akadunk el Mivel minden olyan u pontra, aminel M es M 0 kulonbozik, az (u; sM (u)) el legalabb olyan jo az u pontnal, mint az M 0 -beli el, ezert M= 

M 0 .  Ha M  M 0 , akkor M -b}ol meg tudjuk kapni M 0 -t nehany rota io eliBizony t as: +1 1 1 1 1 1 1 1 1 1 1 3.4 K ovetkezm eny: minalasaval. Legyen C = fM = M ; M ; : : : ; Mk ; Mk = M 0 g egy nem b}ovthet}o M es M 0 kozti lan M-ben. Ekkor C -n ket egymast kovet}o elem szomszedos M-ben, vagyis az el}obbi alltas miatt minden i = 1; 2; : : : k 1-re van olyan i rota io, hogy Mi  Mi =i  Mi , de mivel Mi es Mi szomszedosak, ezert Mi=i = Mi . Vagyis a  ;  ; : : : k rota iokat sorban eliminalva M -b}ol M 0 -t kapjuk.  Most hozzarendelunk a rota iokhoz egy-egy elhalmazt, es belatjuk, hogy ezek pont a H halmazrendszer atomjai. Legyen tehat egy  = (v ; u ; v ; u ; : : : vk ; uk ) rota iora a() := f(ui; v) 2 E : i = 1; : : : k; (ui; vi ) <u (ui ; v ) 6u (ui ; vi )g. Ez egy bijek io a rota iok es A kozt. Bizony t as: 1 2 1 +1 +1 +1 1 i i 1 1 2 2 1 2 +1  t 3.5 All as: Konnyen latszik, hogy ha

 eliminalhato egy M stabil parostasban, akkor a() = H (M=) n H (M ), ami A-beli, mert M es M= szomszedosak. Bizony t as: 9 http://www.doksihu A a() elhalmazbol meg tudjuk kapni -t: egy u 2 U pontra illeszked}o -beli elek az a()ban a <u szerint legnagyobb el es a legnagyobb olyan, ami a a()-beli elekt}ol kisebb. Tehat a fuggveny injektv. Ha A 2 A, akkor a 2.6 alltas miatt vannak olyan szomszedos M  M 0 stabil parostasok, hogy A = H (M 0 ) n H (M ). A 33 alltas miatt van olyan  rota io, hogy M= = M 0 , vagyis a() = H (M 0 ) n H (M ) = A, tehat a fuggveny szurjektv.  Eliminalasok minden olyan sorozata, ami az M stabil parostasbol M 0 be jut, ugyanazokat a rota iokat tartalmazza. 3.6 K ovetkezm eny: Pontosan azon rota iokat eliminalva jutunk M -b}ol M 0 -be, amikhez rendelt atomok H (M 0) n H (M )-nek reszhalmazai.  Bizony t as: Ha MU -bol kiindulva sorban eliminalunk rota iokat, amg lehet, akkor

MV -t kapjuk meg es minden rota iot eliminaltunk pontosan egyszer. 3.7 K ovetkezm eny: A fentiek miatt MU -bol minden M stabil parostast meg tudunk kapni rota iok egy egyertelm}u halmazanak eliminalasaval. Ha egy  rota io benne van ebben a halmazban, akkor azt mondjuk, hogy  eliminalva van M -ben. Ez tehat azzal ekvivalens, hogy a()  H (M ) 3.2 Reszbenrendezes a rota iokon Jeloljuk R-rel a rota iok halmazat. Az A-n lev}o  reszbenrendezes megad egy rela iot R-en: legyen   0 , a()  a(0 ). A 35 alltas miatt (R; ) is reszbenrendezes, es a 27 alltas kovetkezmenye a kovetkez}o Az r : M ! P (R); r(M ) = a (A 2 A : A  H (M )) lekepezes bijek io M es R 3.8 T etel: 1 zart reszhalmazai kozott. Konnyen latszik, hogy azok a rota iok vannak r(M )-ben, amiknek minden ele az U -beli su saban dominalja az azt fed}o M -beli elt.   0 pontosan akkor, ha nin s olyan stabil parostas, amiben 0 eliminalva van, 

t 3.9 All as: de  nin s. Lattuk, hogy a()  a(0 ) azzal ekvivalens, hogy nin s olyan H 2 H, hogy a(0 )  H , de a() H = ;, ami a rota iokra lefordtva pont az alltast jelenti.  Most megadunk egy D = (R; A) iranytott grafot a rota iokon, es be fogjuk latni, hogy a D tranzitv lezartja a  reszbenrendezes, vagyis egy  rota iobol pontosan akkor lehet eljutni D-ben egy iranytott uton egy 0 rota ioba, ha   0 . Ket fajta elet de nialjuk D-nek: Els}o fajta el: legyen (; 0 ) 2 A, ha van olyan (u; v) 2 E , ami mindket rota ion rajta van, es -n bekerul}o, 0 -n pedig kikerul}o el. Bizony t as: 10 http://www.doksihu V v 0  U u 2. abra els}o fajta el D-ben Masodik fajta el: legyen (; 0) 2 A, ha van olyan (u; v) 2 E , ami <u szerint a ket u-ra illeszked}o 0-beli el kozt van, <v szerint a ket v-re illeszked}o -beli el kozt van.  v u 0 3. abra masodik fajta el D-ben 3.10 T etel: A D graf

tranzitv lezartja a  reszbenrendezes. El}oszor mutassuk meg, hogy ha (; 0 ) 2 A, akkor   0 . Ehhez a 39 alltas miatt azt kell belatni, hogy nin s olyan stabil parostas, amiben 0 eliminalva van, de  nin s. Ha  es 0 kozt els}o fajta el van, es egy M stabil parostasban 0 eliminalva van, akkor (u; v) 2= H (M ), ami miatt M -ben  is eliminalva van. Ha  es 0 kozt masodik fajta el van, es egy M stabil parostasban 0 eliminalva van, akkor M az (u; v) elt az u su snal nem dominalja, tehat v -nel dominalja, vagyis  is eliminalva van M -ben, mert  az egyetlen olyan rota io, aminek eliminalasakor v-nel az (u; v) elt}ol rosszabb el helyett egy jobb kerul a parostasba. Most lassuk be, hogy ha   0 , es  es 0 szomszedosak, akkor megy el D-ben -bol 0 be. Legyen S a  rendezes szerint a 0 -nel kisebb rota iok halmaza Ekkor S n fg, S es S [f0 g is zart halmazok. Legyen az S nfg-nak megfeleltetett stabil

parostas M (vagyis M = r (S nfg)). Ekkor a(M=) = S es a(M==0 ) = S [f0 g, vagyis 0 M=-ban eliminalhato, de mivel S [ f0 g n fg nem zart halmaz, ezert M -ben 0 nem eliminalhato. Probaljunk rota iot keresni M -ben ugy, hogy egy olyan V -beli pontbol indulunk ki, ami rajta van 0-n. Az ilyen pontoknal M es M==0 kulonboznek, ezert a 3.3 alltas miatt nem akadunk el, talalunk egy rota iot. Mivel M -ben 0 nem eliminalhato, ezert nem 0-t talaljuk meg, vagyis van egy els}o olyan lepes, ahol nem a 0 kovetkez}o su sara lepunk. Ha ez egy V -beli su snal tortenik, mondjuk v-nel es 0 kovetkez}o su sa u, akkor (v; u) 2= M , de (v; u) 2 M=, tehat  v-nel a (v; u) el helyett egy v-nel jobb elt hoz be, vagyis (u; v) kozos ele -nak es 0-nek, es v-nel a Bizony t as: 1 11 http://www.doksihu masik -beli el jobb, mint a masik 0-beli, vagyis D-ben els}o fajta el megy -bol 0 -be. Ha pedig egy U -beli su snal

lepunk mast el}oszor, mondjuk u-nal, akkor sM (u) 6= sM= (u). Mivel egy M M=-beli elen leptunk u-ba, es egy eliminalas soran a V -beli su sok jobb elt kapnak, ezert ez sak ugy lehet, hogy a  eliminalasakor sM (u) egy (sM (u); u)-nal jobb elt kap, vagyis ekkor masodik fajta el lep -bol 0 -be.  12 http://www.doksihu 4. Algoritmusok 4.1 Minimalis sulyu stabil parostas keresese Adott a G graf elein egy sulyozas, szeretnenk keresni egy minimalis osszsulyu stabil parostast. Lattuk, hogy a stabil parostasok egyertem}uen megfelelnek a H halmazgy}ur}u tagjainak. Valtoztassuk meg H-t ugy, hogy az ures halmaz es az alaphalmaz is benne legyen a halmazrendszerben, de a ket halo izomorf legyen: legyen az uj alaphalmaz E 0 := E n (H) n ([H) es legyen H 0 (M ) := H (M ) n (H), az uj halmazrendszer E 0 -n pedig H0 := fH 0(M ) : M 2 Mg. Most megadunk E 0-n egy olyan 0 sulyozast, hogy egy M stabil parostasnak megfeleltetett

H0 -beli halmaz 0-osszsulya ugyanannyi legyen, mint (M ). Jeloljuk egy E 0 -beli e el U -beli vegpontjanal az e-nel eggyel jobb elt e -szal, ha van ilyen es }o is E 0-beli. Legyen 0 (e) := (e), ha e nin s ertelmezve es 0(e) := (e) (e ), ha ertelmezve van. Ekkor 0(H (M )) = (M ) Tehat egy minimalis sulyu stabil parostas talalasahoz eleg tudnunk, hogy hogyan kell egy metszet- es uniozart halmazrendszerbeli, minimalis osszsulyu halmazt megtalalni. Ezt pedig vissza lehet vezetni egy folyamproblemara. El}oszor kesztsunk egy iranytott grafot, aminek a ponthalmaza E 0 , es aminek a 0 befoku reszhalmazai pont a H0 halmazrendszer elemei. + + + Legyen D0 az az iranytott graf, aminek ponthalmaza E 0 , es egy (e1 ; e2 ) el akkor van benne, ha nin s olyan M stabil parostas, hogy e2 2 H 0 (M ), de e1 2 = H 0(M ), ekkor a D0 -ben 0 befoku halmazok a H0 -beli halmazok.  t 4.1 All as: de n ioja alpjan vilagos, hogy egy H0 -beli

halmazba nem lep be el. Tegyuk fel, hogy az F  E 0 halmazba nem lep el D0-ben. Ha F ures halmaz vagy E 0, akkor H0-beli Ha nem, akkor minden f 2 F es e 2 E 0 n F parhoz letezik olyan H (e; f ) 2 H0, hogy f 2 H (e; f ), de e 2= H (e; f ). Igy minden f 2 F -re a fH (e; f ) : e 2 E 0 n F g egy f -et tartalmazo H-beli halmaz es resze F -nek. Tehat ezek unioja, vagyis F is H-beli  A D0 grafban a legkisebb sulyu 0 befoku halmazt a kovetkez}okepp tudjuk megkeresni. Vegyunk a grafhoz ket uj pontot, s-et es t-t. Jeloljuk E -szal illetve E -szal az E 0-beli, pozitv illetve negatv 0 -sulyu eleket Minden e 2 E -ra huzzunk egy elt s-b}ol e-be, aminek kapa itasa legyen 0 (e) es minden f 2 E -ra huzzunk egy elt f -b}ol t-be, aminek kapa itasa legyen 0 (f ). Az gy kapott grafban egy folyamalgoritmussal a folyam mellett egy minimalis vagast is kapunk, jeloljuk H -val az E 0 vagason kvuli reszet. H -ba nem lep be el D0-ben, mert akkor a

minimalis vagas erteke vegtelen lenne, de az fsg vagas erteke veges. Emellett egy tetsz}oleges 0 befoku F  E 0 halmazra az s [ F vagasbol kilep}o eleken a kapa itasok osszege az s-b}ol F -be lep}o eleken es az E 0 n F -b}ol t-be lep}o eleken a kapa itasok osszege, vagyis 0 (F E ) 0 (E n F ) = 0 (F E ) + 0 (F E ) 0 (E ) = 0 (F ) 0 (E ), vagyis H a minimalis sulyu 0 befoku halmaz. Bizony t as: D0 + + + + 13 http://www.doksihu 4.2 A rota iok megkeresese El}oszor keressuk meg az MU uoptimalis es az MV lanyoptimalis stabil parostast a 2.2 tetel bizonytasaban lert algoritmussal, ami O(m) idej}u, ahol m az elek szama. Ezutan egy olyan u 2 U pontbol kiindulva, aminel MU es MV kulonbozik, a 3.3 lemmaban lert modon keresunk egy MU -ban eliminalhato rota iot Taroljuk ezt a rota iot es MU helyebe vegyuk azt a stabil parostast, amit a rota io eliminalasaval kapunk MU -bol. Ezt ismeteljuk, ekkor a

37 kovetkezmeny miatt minden rota iot megtalalunk. Ezt az algoritmust lehet ugy implementalni, hogy O(m) ideig fusson, korulbelul ugy, hogy minden su snal, amire nem illeszkedik a talalt rota io, megjegyezzuk, hogy hova leptunk, mert konnyen ellen}orizhet}o, hogy ez nem valtozik az eliminalas utan. Az algoritmus reszletei Gus eld es Irving [12℄ konyveben megtalalhatok Ezzel egyuttal megtalaltuk azokat az eleket, amik szerepelnek stabil parostasban, hiszen ezek pont a rota iokon szerepl}o elek. Ezen elek halmazat jeloljuk Est-vel A D(G; O) grafot megkereshetjuk a kovetkez}okeppen. Mikozben a rota iokat keressuk, minden rota io eleit megjeloljuk a rota io sorszamaval, es ha egy kes}obbi rota ion van egy megjelolt el, akkor behuzunk egy els}o fajta elt D(G; O)-ban a korabbi rota iobol ebbe. A masodik fajta elekhez el}oszor minden lanynal minden ra illeszked}o rota io sorszamat rjuk ra azokra az

elekre, amik a rota io ket ele kozt vannak (szigoruan). Ezutan minden unal ha egy i rota io egy koztes elere j van rva, akkor D(G; O)-ba huzzuk be a (j ; i ) elt masodik fajta elkent. Ez is O(m) idej}u 4.3 Minimalis sulyu stabil parostas keresese rota iok segtsegevel Ezt az algoritmus Irving, Leather es Gus eld [14℄rtak le. Lattuk, hogy a stabil parostasok egyertelm}uen megfelelnek a D(G; O) graf 0 befoku su shalmazainak Ha adott egy sulyfuggveny az eleken, akkor vegyuk a kovetkez}o sulyozast a rota iokon: legyen egy  = (v ; u ; : : : ; vk ; uk ) rota io sulya 0() := (v u ) + (u v ) (v u ) + (u v ) +


+ (uk v ). Ekkor ha  eliminalhato egy M parostasban, akkor (M=) = (M ) + 0 () es gy, ha r(M ) az M -nek megfelel}o rota iohalmaz, vagyis azon rota iok halmaza, amiket eliminalva MU -bol M -et kapjuk, akkor (M ) = (MU )+ 0 (r(M )). Tehat a minimalis sulyu stabil parostasnak a minimalis

sulyu 0 befoku halmaz felel meg. Ezt pedig ugyanugy tudjuk megkeresni, mint a 41 alfejezet vegen 1 1 1 1 2 2 2 2 3 1 1 4.4 Minimalis sulyu stabil parostas kotelez}o es kizart elekkel A feladat az, hogy a paros grafunkban adott az eleknek ket reszhalmaza, E es E , es egy sulyfuggveny az eleken es meg kell mondanunk, hogy van-e olyan stabil parostas, ami E -et tartalmazza, E -t}ol pedig diszjunkt, es ha van, akkor meg is kell adni egy minimalis sulyut. Erre Dias, da Fones a, de Figueiredo es Szwar ter [5℄ adtak egy algoritmust, itt ki sit mas modszert adunk a feladat megoldasara. 1 2 1 2 14 http://www.doksihu Most is a D(G; O) grafban probalunk keresni egy megfelel}o, minimalis 0-sulyu 0 befoku su shalmazt. Vegyunk a grafhoz egy s es egy t pontot, s-et kossuk ossze a pozitv 0-sulyu pontokkal, t-t a negatvakkal, az kapa itas legyen az s-b}ol kilep}o eleken a vegpont 0 -sulya, a t-be lep}o eleken a

kezd}opont sulyanak ellentettje, a tobbi elen pedig vegtelen. Ezen a kapa itasos grafon fogunk meg valtoztatni, meghozza eleket osszehuzni, hogy a veges vagasok az E -et tartalmazo, E -t}ol diszjunkt stabil parostasoknak megfelel}o rota iohalmazok legyenek. Legyen e 2 E . Ha e 2= Est , akkor nin s keresett stabil parostas Ha e 2 Est , akkor annak a rota ionak, amin e bekerul}o el (ha van), benne kell lenni ebben a 0 befoku halmazban, ezert huzzuk ossze s-sel, annak a rota ionak, amiben e kikerul}o el (ha van), nem szabad benne lennie a halmazban, gy ezt t-vel huzzuk ossze. Legyen e 2 E Ha e 2= Est, akkor e nem ad uj feltetelt. Ha e 2 Est, akkor annak a rota ionak, amiben e belep}o el, es amiben kilep}o el, vagy mindkett}onek benne kell lenni a halmazban vagy egyiknek sem, ezert huzzuk ossze a koztuk men}o (els}o fajta) elt. Az gy kapott grafban egy minimalis vagas egy minimalis sulyu E -et tartalmazo, E -t}ol

diszjunkt stabil parostasonak felel meg, ezt egy folyamalgoritmussal meg tudjuk keresni. 1 2 1 1 1 1 1 1 2 2 1 2 2 2 2 15 2 http://www.doksihu 5. Poli ederes eredm enyek 5.1 Poliederes lerasok Legyen (G; O) egy paros preferen iarendszer. A (G; O)-ban lev}o osszes stabil parostas R E -beli in iden iavektoranak konvex burkat, vagyis a stabil parostasok poliederet jeloljuk P (G; O)-val. Vande Vate [16℄ adott el}oszor linearis lerast P (G; O)-ra, am sak arra az esetre, amikor G teljes paros graf: Ha (G; O) egy paros preferen iarendszer, ahol G = (U ; V; E ) teljes paros graf es jU j = jV j, akkor az 5.1 T etel: (Vande Vate) (5.2) (5.3) (5.4) x > 0; x(D(w)) =1; ha w 2 U [ V; x( (e)) 6 1; ha e 2 E egyenl}otlensegrendszer P (G; O)-t rja le, ahol (e) az e el altal dominalt elek halmazat jeloli. Rothblum [15℄ egy hasonlo lerast adott, ami mar tetsz}oleges grafra m}ulodik: Legyen (G; O) egy paros

preferen iarendszer, ahol G = (U; V ; E ), es jeloljuk egy e elt dominalo elek halmazat (e)-vel. Ekkor az (5.6) x > 0; (5.7) x(D(w)) > 1; ha w 2 U [ V; (5.8) x((e)) > 1; ha e 2 E rendszer a P (G; O) poliedert rja le. 5.5 T etel: (Rothblum) Konny}u latni, hogy egy stabil parostas in iden iavektora teljesti ezeket az egyenl}otlensegeket. Legyen most x olyan vektor, ami teljesti az egyenl}otlensegeket Nevezzunk egy e elt pozitvnak, ha x(e) > 0: Vegyunk egy olyan e = (u; v) elt (ahol u 2 U; v 2 V ), ami u-nal a legjobb pozitv el. Ekkor az e-t dominalo pozitv elek mind illeszkednek v -re, amiken az x osszege ezert legfeljebb 1, masreszt legalabb 1, vagyis pont 1, es emiatt e a v su snal a legrosszabb pozitv el. Tehat, ha minden olyan U -beli ponthoz, amire illeszkedik pozitv el, hozzarendeljuk azt a V -beli pontot, ami a legjobb pozitv el masik vegpontja, akkor ez egy injektv fuggveny es minden kepnel a

szomszedos eleken 1 az osszeg, de ez sak ugy lehet, hogy minden V -beli pont el}oall kepkent, es minden U [ V -beli pontnal az eleken az x osszege 0 vagy 1. Jeloljuk azon az elek halmazat, amik az U -beli vegpontjuknal a legjobb pozitv elek, M -mel. M egy stabil parostas, mert ha f egy olyan el, amit M nem dominal az U -beli vegpontjanal, akkor a V -beli vegpontjanal f -nel jobb az osszes pozitv el, tehat a legkisebb is, ami a fentiek miatt Bizony t as: 16 http://www.doksihu M -ben van. Legyen a legkisebb x-ertek M -ben Ha = 1, akkor x az M stabil parostas in iden iavektora, ekkor keszen vagyunk. Ha < 1, akkor legyen x0 (e) = (x(e) M ) Lassuk be, hogy x0 is teljesti az egyenl}otlensegeket. Nyilvan x0 > 0 Ha M fedi a w pontot, akkor x0(D(w)) = (x(D(w)) ) > 1, ha M nem fedi w-t, akkor w-re nem illeszkedik pozitv el, tehat (5:7:)-t is teljesti x0. Ha e = (u; v) 2 E , akkor az nem lehet, hogy (e)-ben ket M -beli el

is van, mert ha v -nel egy M -beli el jobb, mint e, akkor v -nel az osszes vele szomszedos pozitv el jobb, mint e, ezeken az osszeg 1, ezert u-nal nem lehet e-t}ol jobb pozitv el, (5:8:) miatt. Tehat x0 ((e)) > (x((e)) ) > 1, tehat (5:8:)-t is teljesti x0 Emellett x el}oall az x0 es a M konvex kombina iojakent es x0 -ben kevesebb pozitv el van, mint x-ben, gy ha ezt folytatjuk, el}obb-utobb elerunk egy stabil parostas in iden iavektorahoz.  Fleiner Tamas [9℄-ben a blokkolo poliederek elmeletet hasznalva a stabil parostasok egy matroidokra valo altalanostasanak poliederere adott lerast, ami a stabil parostasok esetengy hangzik: Legyen (G; O) egy paros preferen iarendszer es legyen A := fA  E : jA M j 6 18M 2 Mg es B := fB  E : jB M j > 18M 2 Mg, ekkor a (5.10) x > 0; (5.11) x(A) 6 1; ha A 2 A; (5.12) x(B ) > 1; ha B 2 B rendszer P (G; O)-t rja le. 1 1 1 1 1 1 5.9 T etel: (Fleiner) 5.2

TDI-sag Legyen A egy m  n-es matrix. Az Ax > b linearis egyenl}otlensegrendszert teljesen dualisan egeszertek}unek (TDI-nak) nevezzuk, ha minden olyan egesz 2 Zn elfuggvenyre, amire f x : x 2 R n ; Ax > bg alulrol korlatos, letezik egesz dualis optimalis megoldas, vagyis olyan y 2 Zm, amire y > 0, yA = es yb = minf x : x 2 R n ; Ax > bg. El}oszor belatjuk egy, a Rothblumehoz hasonlo egyenl}otlensegrendszerr}ol, hogy TDI, amib}ol kovetkezni fog, hogy ez is a stabil parostasok poliederetrja le, majd ebb}ol levezetjuk Rothblum lerasanak TDI voltat. A kovetkez}o rendszer x 2 R E valtozoval teljesen dualisan egeszertek}u: x > 0; (5.14) x(0 (e)) > 1; ha e 2 E n Est ; x(0 (e)) =1; ha e 2 Est ; itt 0 (e) az e elt dominalo Est -beli elek halmazat jeloli. 5.13 T etel: st 17 http://www.doksihu Mivel a stabil parostasok in iden iavektorai elemei ennek a poliedernek, ezert eleg azt megmutatni, hogy minden egesz

2 ZE elfuggvenyhez van olyan y 2 ZE egeszertek}u dualis megoldas, amire (5.15) y (e) > 0; ha e 2 E n Est; (5.16) y ( (e)) 6 (e); ha e 2 Est ; es P y(e) = minf xjx 2 P (G; O)g. e2E Lattuk, hogy a stabil parostasok egyertelm}uen megfelelnek a D(G; O) = (R; A) graf 0 befoku ponthalmazainak, es ha egy  = (v ; u ; : : : ; vk ; uk) rota ionak a 0() := (v u ) + (u v ) (v u ) + (u v ) +


+ (uk v ) sulyt adjuk, akkor minden M stabil parostasra (M ) = (MU ) + 0 (r(M )), ami miatt a minimalis sulyu stabil parostasnak a minimalis sulyu forras halmaz felel meg. A D(G; O) graf forras halmazainak P poliederet a kovetkez}o rendszerrel lehet lerni: x 2 R R 0 6 x 6 1; (5.17) x() x(0 ) > 0; ha (; 0 ) 2 A: Mivel ennek a rendszernek a matrixa teljesen unimodularis (mert minden sorban legfeljebb egy 1-es es legfeljebb egy 1-es van), ezert a rendszer teljesen dualisan egeszertek}u. Tehat spe ialisan a fenti 0 2 ZR-re van olyan z 2 ZR[A,

amire z > 0 ha  2 R; (5.18) z ; > 0; ha (; 0 ) 2 A; z + z (
()) z (
()) 6 0 (); ha  2 R; es P z = minf 0xjx 2 Pg = (Mopt ) (MU ), ahol Mopt egy minimalis sulyu stabil parostas, 2R es
() es
() a D grafban a  pontbol kimen}o, illetve a pontba bemen}o elek halmazat jeloli. Legyen  ; : : : ; r egy topologikus sorrendje a D grafnak, vagyis egy olyan sorrendje a rota ioknak, amilyen sorrendben eliminalni lehet }oket. Minden i rota ion valasszunk ki egy bekerul}o ei elt (vagyis ami az U -beli su sanal rosszabb, mint a masik i -beli el). Ezen kvul, ha (i; j ) 2 A es masodik fajta el van koztuk, akkor legyen eij egy olyan el, ami a V -beli vegpontjanal a ket arra illeszked}o i -beli el kozt van, az U -beli vegpontjanal pedig a ket j -beli el kozt, vagyis egy olyan el, ami miatt masodik fajta el van a ket rota io kozt. Az egyszer}useg kedveert z  ; -t jeloljuk zij -vel, z -t pedig zi-vel. 0 6 t 6

r-re es e 2 Est -re legyen X fzli j l 6 t < i; e 6V el ; (l ; i) 2 Ag: t (e) := (e) A kovetkez}okben rekurzv modon de nialni fogunk olyan y ; y ; : : : ; yr ZE -beli vektorokat ugy, hogy minden 0 6 t 6 r-re teljesuljenek az alabbiak: Bizony t as: st 1 1 2 2 2 2 3 1 1 1 ( 0 ) + + 1 0 ( i j) i 0 0 18 1 1 http://www.doksihu (a) yt (e) > 0, ha e 2 E n Est (b) yt ( (e)) 6 t (e), ha e 2 MU [  [  [


[ t 1 t ( ) P yt(e) = (MU ) P zi e2E 2 i=1 (d) supp(yt )  MU [  [  [


[ t [ feij : i; j 6 tg 1 2 Tehat az yt dualis terbeli egesz vektorok egyre tobb (5:16:)-beli egyenl}otlenseget teljestenek, a elfuggveny erteke kozelt az optimalishoz, es az ei eleknel olyan tobbleteket biztostunk magunknak, amit a kes}obbi yk -knal "felhasznalhatunk". Ha sikerul ilyen yt-ket de nialni, akkor keszen vagyunk, hiszen yr -re mar az osszes (5:16:)-beli egyenl}otlenseg teljesul, vagyis benne van r P P a

dualis poliederben a vektor, es a elfuggveny erteke pedig yr (e) = (MU ) zi = (Mopt). i e2E Legyen 8 > < (e) ha e 2 MU , y (e) := > : 0 egyebkent. Ekkor persze P y (e) = (MU ), es minden MU -beli elre teljesul (b) es a tobbi kovetelmeny is. e2E Az yt-t ugy kapjuk yt -b}ol, hogy sak a t rota io elein es a fenti elt eleken valtoztatunk (l 6 t-re). Szamozzuk most a t rota io su sait fordtott sorrendben wt ; wt ; : : : wt k -val, ahol (wt k ; wt ) = et , a (wit; wit ) elt pedig jeloljuk eti -vel, ekkor tehat eti <w eti es wit V -beli, ha i paros es U -beli, ha i paratlan. Minden et i el vagy szerepel korabbi rota ion vagy MU -beli, ezert teljesul, hogy yt ( (et i )) 6 t (et i ). 0 =1 0 0 1 1 1 2 0 t i +1 2 2 1 2 +1 1 1 2 +1 2 +1 et2k 1 w2t k t et0 w1t et1 2U w2t et2 2V 4. abra t (a vastag elek a kikerul}o elek) Hasznalni fogjuk, hogy mivel a rota iokat egy topologikus sorrend szerint vesszuk

sorba, ezert ha egy e elnek yt -ben nem 0 erteke van es illeszkedik  egy su sara, akkor, ha ez a su s U -beli, mondjuk wt i , akkor e 6w2 +1 e i <w2 +1 e i , ha pedig V -beli, mondjuk wt i, akkor e > w2 e i >w2 e i . El}oszor de nialunk egy yt0 -t, ami teljesti a felteteleket, kiveve, hogy (b)-t t -re teljesti, az et elen pedig nem feltetlenul teljesti. 1 2 +1 t i 2 1 t i t i 2 +1 t i 2 2 2 1 0 19 http://www.doksihu yt0 -hez yt 1 -t sak a t elein valtoztatjuk. Legyen yt0 (et0 ) := zt ; yt0 (et1 ) := yt gy yt0 ( (et )) = yt ( (et )) zt 6 t (et ). Figyeljuk meg, hogy minden j -re (et j ) 1 1 1 1 1 (et ); 1 (et j ) = 2 yt0 (et2 ) := (et2 ) 1 2 1 (et ) = t 1 1 t 1 (et j ) (et ) t 2 t 2 1 1 (et j ). Ezutan legyen 2 1 (et ); 1 ekkor, mivel a (et ) elhalmazban sak olyan eleknek nem 0 az yt erteke, amik w -re illeszkednek, vagyis (et )-ben is benne vannak, ezert 1 1 2 2 yt0 ( (et2 )) = yt

Legyen yt0 (et3 ) := yt Ekkor yt0 ( (et3 )) = yt Legyen 1 1 1 ( (et )) + t 1 (et ) (et ) t 2 1 (et ) 6 2 ( (et )) + (et ) 3 1 1 (et ) 2 3 1 (et ): 2 (et ) + (et ) 2 yt0 (et2 ): (et ) + (et ) 6 1 3 t 1 (et ) + (et ) = yt (et ) 3 yt0 (et4 ) := (et4 ) ekkor et -hoz hasonloan 1 1 t 1 (et ): 3 (et ); 2 1 2 yt0 ( (et4 )) = yt 1 ( (et ))) 3 (et ) + (et ) + 2 t 1 1 (et ) 4 t 1 (et ) + (et ) 3 (et ) 6 2 1 t 1 (et ): 4 A tobbi elre ezt folytatjuk: legyen minden j = 0; 1; : : : k 1-re yt0 (et2j +1 ) := yt y 0 (et t j 2 1 (et j ) + 2 +1 ) := Xj 2 i=1 ( 1)i (eti ); +1 Xj 2 i=1 ( 1)i (eti): Ekkor a (e i ); (1 6 i 6 k 1) elhalmazban sak az e i es az e i elen valtoztattuk meg yt-t, es az egyikb}ol levontunk, a masikhoz hozzaadtunk (e i ) (e i )-t, ezert a (b) egyenl}otlensegek ervenyben maradnak ezeken az eleken yt0 -re is. Hasonloan a korabbi rota iokon szerepelt elekre is teljesul (b). Mivel a wt j su

snal az et j el legfeljebb olyan jo, mint azok az elek, amiknek eddig nem 0 erteket adtunk, a wt j -nel pedig ugyanez igaz et j -re, amik miatt yt ( (et j )) = 2 +1 2 +1 2 2 2 1 2 2 +1 1 2 +1 2 +1 20 1 2 http://www.doksihu yt 1 ( (et j )), amit felhasznalva, j = 1; 2; : : : k 1-re: 2 1 yt0 ( (et2j )) = yt0 (et2j ) + yt = Xj 2 i=1 1 ( (et j )) + yt0 (et j ) 2 ( 1) ( ) + yt ( ( i eti et 1 j 2 1 1 j X 2 )) + 2 yt 1 1 (et j ) = 2 1 2 i=1 ( 1)i (eti ) = +1 = yt ( (et j )) t (et j ) + t (et j ) 6 6 t (et j ) t (et j ) + t (et j ) = t (et j ); 1 1 2 2 1 1 1 1 2 2 1 1 1 1 2 1 2 2 vagyis yt0 is teljesti (b)-t t 1-re az (et j ) eleken, ha j 2 f1; 2; : : : k 1g. Ezen kvul X0 X Xt yt (e) = yt (e) zt = (MU ) zi : 2 e2E 1 e2E i=1 A kovetkez}o valtoztatasokat minden olyan l-re vegrehajtva, amire (l ; t ) 2 A, kapjuk yt0 -b}ol yt -t. Legyen (l ; t) 2 A. Ha els}o fajta el megy koztuk, akkor van egy kozos

eluk, ami l -ben paros index}u, t -ben pedig paratlan index}u, mondjuk el i = et j . Ekkor minden 0 6 x 6 i 1-re az el x elen noveljunk zlt -vel, az el x elen sokkentsunk zlt -vel, es minden j + 1 6 y 6 k 1-re az et y elen noveljunk zlt -vel, es az et y elen sokkentsunk zlt -vel. 2 2 2 +1 2 +1 2 2 +1 + + t el2i + = et2j +1 l et0 zlt el0 lt +z 5. abra ha (l ; t) els}o fajta el Ha l -b}ol t -be masodik fajta el megy, akkor az elt el egyik vegpontja l -en egy paros index}u pont, mondjuk wl i, a masik pedig t -n egy paratlan index}u pont, mondjuk wl j . Ilyenkor noveljunk zlt -vel az el x elen 0 6 x 6 i 1-re, az et y elen j + 1 6 y 6 k 1-re es az elt elen, valamint sokkentsunk zlt -vel az el x elen 0 6 x 6 i 1-re es az et y elen j 6 y 6 k 1-re. Az elt eleken noveltunk zlt -vel, ami nemnegatv, ezert az (a) feltetel teljesul. Mivel ugyanannyi elen noveltunk zlt -vel, mint ahanyon sokkentettunk, ezert 2 2 +1 2

2 2 +1 X e2E yt (e) = 2 +1 X e2E yt0 (e) = (MU ) 21 Xt i=1 zi : http://www.doksihu + + + el0 l t + + et0 elt 6. abra ha (l ; t ) masodik fajta el Mivel ha egy e 2 MU [  [  [


[ t n fe 2 l [ l [


[ t : 9v 2 V; e 6v el g elre (e)-ben valamelyik elen noveltunk zlt -vel, akkor egy masikon sokkentettunk is, ezert az egyenl}otlensegek ugyanakkora tobblettel teljesulnek, mit eddig. Ha e 2 fe 2 l [ l [


[ t : 9v 2 V; e 6v el g, akkor yt0 (e) n}o zlt -vel, vagyis teljesul (b). Legyen := Pfzlt j l < t; et 6V el ; (l ; t ) 2 Ag. Ekkor t (et ) = t (et )+ z(
(t )), gy az et elre: yt ( (et )) = yt0 ( (et )) z (
(t )) + = = yt0 (et ) + yt ( (et k )) + yt0 (et k ) yt (et k ) z(
(t )) + = 1 2 +1 0 +1 0 0 0 1 0 + 0 0 0 0 1 0 = zt 2 1 2 z (
(t )) + yt 6 0(t ) z(
(t )) + 1 ( ( et k 2 1 1 )) + 1 k X 2 2 1 2 i=1 ( 1)i (eti) + 6 +1 (et k ) 0(t ) t (et k ) + t (et ) + = = t (et ) z(


(t)) + = t (et ); vagyis yt az et elen teljesti a (b) feltetelt, es mivel fe 2 t : 9v 2 V; e <v et g = ;, ezert minden feltetelt ellen}oriztunk, tehat az alltast belattuk.  Edmonds es Giles tetele alapjan egy leras TDI-sagabol (ha a korlatozo vektor egesz,) kovetkezik, hogy egesz a polieder, vagyis egyuttal a kovetkez}ot is belattuk: + 1 0 + t 1 2 1 1 2 1 0 0 0 5.19 K ovetkezm eny: 1 0 Az alabbi rendszer a stabil parostasok poliederet rja le az R E terben: st x > 0; (5.20) x(0 (e)) > 1; ha e 2 E n Est ; x(0 (e)) =1; ha e 2 Est : Azt kell belatnunk, hogy a rendszer egesz pontjai stabil parostasok in iden iavektorai. Legyen egy w 2 U [ V pontnal a legrosszabb Est-beli el e, ekkor D(w) Est  0(e), ezert x(0(e)) = 1 miatt D(w)-ben az osszeg legfeljebb 1, vagyis egy egesz pont egy parostas in iden iavektora. Masreszt minden e 2 E -re x(0 (e)) > 1, ezert a parostas stabil  Bizony t as:

22 http://www.doksihu A Rothblum altal lert 5.21 T etel: (5.22) (5.23) (5.24) x > 0; x(D(w)) > 1; ha w 2 U x((e)) > 1; [ V; ha e 2 E rendszer teljesen dualisan egeszertek}u. Az 5.13 tetelbeli leras TDI-sagara vezetjuk vissza Egy tetsz}oleges egesz 2 ZE sulyfuggvenyhez kell keresni egesz optimalis dualis megoldast, vagyis olyan  2 ZU [V -t es y 2 ZE -t, amire Bizony t as: (5.25) (5.26) (5.27) y (e) > 0;  (w) > 0;  (u)  (v ) + y ( (e)) 6 (e); ha e = (u; v) 2 E; es Pw2U [V (w) + Pe2E y(e) = (Mopt). Legyen y a sulyfuggveny Est -re valo megszortasahoz egy egesz dualis optimalis megoldasa az 5.13 tetelbeli rendszernek es legyen  a nullvektor U [V -n O} k tehat teljestik az (5:25:)-beli egyenl}otlensegek kozul az e 2 E n Est-re vonatkozokat, (5:26:)-et es (5:27:)-et, ha e 2 Est . Ha egy dualis egesz vektorhoz egy M stabil parostas elein es az U -beli fedett su sokon hozzaadunk tetsz}oleges

pozitv egesz k-t, akkor olyan egesz vektort kapunk, aminek elfuggvenyerteke ugyanannyi, az (5:27:)-beli egyenl}otlensegek baloldalai pedig nem n}ottek, mert nin s olyan e el, amire (e)-ben ket olyan el is van, amin noveltunk, mert az blokkolna M -et, ha pedig e olyan el, amire (e)-ben noveltunk egy elen, akkor e U -beli vegpontja fedett kell legyen, kulonben szinten blokkolna M -et. Ilyen valtoztatasokat vegrehajtva (y ;  )-on el tudjuk erni, hogy (5:25:) minden elre teljesuljon, a tobbi egyenl}otlenseg se seruljon. Jeloljuk az gy kapott vektort (y ;  )-gyel. Ha e 2 E n Est, akkor a e (vagyis e-n -1, E n feg-n 0) elfuggvenyre a primal polieder optimuma 0, ezert ha veszunk egy ra ionalis dualis optimalis megoldast es megszorozzuk a nevez}ok legkisebb kozos tobbszorosevel, akkor egy egesz dualis optimalis megoldast kapunk, jeloljuk ezt (ye; e)-vel. Ha az e elen (5:27:) nem teljesul (y ;  )-re, akkor adjuk hozza (ye;

e) megfelel}o tobbszoroset, akkor mar teljesulni fog ez az egyenl}otlenseg is, mg a elfuggvenyertek nem valtozik es a tobbi egyenl}otlenseg sem serul. Ezt minden sert}o elre vegrehajtva egy egesz optimalis dualis megoldast kapunk.  0 0 0 1 1 1 23 1 0 http://www.doksihu 6. Egy alkalmaz as: Galvin t etele Azt mondjuk, hogy egy graf listasznezhet}o n hosszu listakkal, ha barhogy is rendelunk a su saihoz n elem}u halmazokat (a sznek listait), ki lehet ugy sznezni a su sokat, hogy szomszedos su sok sznei kulonboz}ok legyenek es minden su s szne a listajanak eleme. Egy graf listasznezesi szama a legkisebb olyan n, amilyen hosszu listakkal ki lehet sznezni. A hres listasznezesi sejtes azt alltja, hogy minden graf elgrafjanak listasznezesi szama megegyezik a kromatikus szamaval. Galvin paros grafok elgrafjaira oldotta meg ezt [11℄-ben, a stabil parostas letezeset felhasznalva. 6.1

T etel: (Galvin) Minden paros graf elei listasznezhet}ok a graf maximalis foka hosszu listakkal. Legyen a G = (U; V ) paros grafban a maximalis fokszam d. Ekkor K}onig elsznezesi tetele alapjan ki lehet sznezni az eleket d sznnel, jeloljuk a szneket 1; 2; : : : dvel. Vegyuk azt a preferen iarendszert, hogy minden U -beli su snal ket el kozul a kisebb szamu legyen a jobb, a V -beli su soknal pedig a nagyobb szamu legyen a jobb. Ekkor ha e egy tetsz}oleges el, es k a szama, akkor e az U -beli vegpontjanal sajatmagan kvul legfeljebb k 1 el dominalja, a V -beli su sanal pedig legfeljebb d k, gy osszesen sajatmagaval egyutt k 1 + d k + 1 = d el dominalja e-t. Ezert a tetel rogton kovetkezik az alabbi lemmabol: Bizony t as: Ha G paros graf, G; O tetsz}oleges preferen iarendszer es minden elhez adott egy sznlista, ami legalabb annyi elem}u, mint ahany el dominalja azt az elt, akkor van jo

listasznezes. 6.2 Lemma: A listakon el}ofordulo sznek szama szerinti induk ioval bizonytunk. Ha ez a szam 1, akkor a feltetel miatt minden elt sak sajatmaga dominal, es a listajaban benne van a szn, vagyis pontdiszjunkt elekb}ol all a graf, amit ki lehet sznezni azzal a sznnel. Tegyuk fel, hogy a G grafban el}ofordulo sznek szamatol kevesebb sznre mar tudjuk az alltast. Legyen a az egyik szn es legyen Ga azon elek alkotta reszgraf, amiknek listajan szerepel az a szn, Oa pedig legyen az O megszortasa Ga -ra. Vegyunk (Ga ; Oa)-ban egy stabil parostast, ami a 2.2 tetel miatt letezik Sznezzuk a stabil parostas eleit a-ra es hagyjuk el }oket a grafbol, es a tobbi Ga-beli el listajabol vegyuk ki a-t. Azgy keletkezett preferen iarendszerre es listakra teljesul a feltetel, mert ha egy elnek sokkent a listaja, akkor legalabb egy }ot dominalo elt kihagytunk a grafbol. Az el}ofordulo sznek szama

is sokkent, gy az induk io miatt a maradek grafot ki lehet sznezni, ami az a szn}u elekkel egyutt G egy jo listasznezeset adja.   Bizony t as: 24 http://www.doksihu 7. Stabil p aros t asok tetsz} oleges gr afban A stabil parostas problema ertelmezhet}o tetsz}oleges grafban is, ugyanugy, mint paros grafban. Adott tehat egy G = (V; E ) graf, amiben parhuzamos elek is lehetnek, es minden v su sahoz egy <v rendezes D(v)-n, amik halmazat O-val jeloljuk. A (G; O) part preferen iarendszernek nevezzuk. A 2.1 lemma bizonytasaban nem hasznaltuk fel, hogy a graf paros, gy kimondhatjuk az alabbit: 7.1 Lemma:  Tetsz}oleges grafban minden stabil parostas ugyanazt a ponthalmazt fedi. Viszont a Gale-Shapley algoritmus mar nem m}ukodik nem paros grafban, s}ot nem is feltetlenul van stabil parostas, peldaul egy haromszogben, ha a harom el "korbeveri" egymast, akkor nin s. De igaz a Gale-Shapley

tetel kovetkez}o megfordtasa: Egy G grafban pontosan akkor van barmilyen preferen iarendszerhez stabil parostas, ha G paros graf. 7.2 T etel: (Abeledo, Isaak) A Gale-Shapley tetel miatt sak azt kell belatni, hogy ha G nem paros, akkor van olyan preferen iarendszer, amihez nin s stabil parostas. Legyen G-ben v ; e ; v ; e ; : : : ; v k ; e k ; v egy paratlan kor, es vegyunk egy olyan preferen iarendszert, amiben a 6v rendezesben az ei el a legkisebb, az ei el pedig a masodik legkisebb (itt az indexek mod 2k + 1 ertjuk). Barmely M parostasnal e paratlan sok el kozul van ket egymast kovet}o, mondjuk ei es ei , amik nin senek M -ben. De akkor az ei elt nem dominalja M -beli el, vagyis nin s stabil parostas.  Bizony t as: 1 2 +1 2 +1 1 1 2 2 i 1 +1 7.1 Stabil parostast keres}o algoritmus Irving adott egy algoritmust [13℄-ben, ami eldonti, hogy egy grafban van-e stabil parostas, es ha van, akkor talal egyet.

Az algoritmus ket fazisbol all Az els}o fazisa eleket hagy el a grafbol ugy, hogy a stabil parostasok halmaza ne valtozzon, emellett nehany elt megiranyt (oda-vissza eleket is megengedve) ugy, hogy bizonyos tulajdonsagu legyen a kapott vegyes graf. A masodik fazis e tulajdonsagok megtartasa mellett ugy redukalja a grafot, hogy ne valtozzon, hogy van-e benne stabil parostas. Amg van olyan x 2 V , amib}ol nem lep ki iranytott el, az x-nel legjobb fx; yg elt iranytsuk meg x-b}ol y-ba es hagyjuk el az y-nal az fx; yg elnel rosszabb eleket, a <v rendezesek pedig legyenek az el}oz}o megszortasai. Els} o f azis: Az gy kapott preferen iarendszerben ugyanaz a stabil parostasok halmaza, mint az eredeti grafban.  t 7.3 All as: 25 http://www.doksihu Eleg latni, hogy egy lepes alatt ugyanaz marad a stabil parostasok halmaza. Amikor egy fx; yg elt megiranytunk, akkor x-nel fx; yg a legjobb el, ezert az fx;

yg-t dominalo elek mind illeszkedek y-ra. Tehat minden stabil parostas fx; yg-t y-nal dominalja, vagyis a kihagyott elek nin senek benne stabil parostasban. Ugyanemiatt a kisebb grafban minden stabil parostas a kihagyott eleket is dominalja, tehat az el}oz}o grafban is stabil parostas.  Az els}o fazis soran nem keletkezhet ket olyan iranytott el, amiknek ugyanaz a vegpontja, mert a vegpontnal a nagyobbikat toroltuk volna, amikor a kisebbik iranytotta valt. Tehat a fazis vegen az iranytott elek pontdiszjunk (iranytott) koroket es oda-vissza eleket alkotnak, amik minden nem izolalt pontot lefednek, es minden pontnal a kimen}o el a legjobb es a bemen}o el a legrosszabb. Ha a kapott graf sak oda-vissza iranytott elekb}ol all, akkor ez az egyetlen stabil parostas az eredeti grafban is. Ha pedig van egy nem egy pontu paratlan komponens, akkor nin s stabil parostas, mert minden parostas kihagy legalabb

egy pontot bel}ole, de az abba bemen}o iranytott elt sak abban a pontban tudna dominalni, vagyis ez blokkolja a parostast. Olyan lepeseket fogunk tenni, hogy megmaradjon az a tulajdonsag, hogy minden nem izolalt pontba egy el lep be es egy el lep ki bel}ole es az iranytott elek a kezd}opontjuknal a legjobbak, a vegpontjuknal pedig a legrosszabbak. Rota ionak most egy olyan (y ; e ; x ; f ; y ; e ; x ; f ; : : : yk ; ek ; xk ; fk ) korsetat nevezunk, amiben az ei = (xi; yi) el iranytott el xi -b}ol yi-be, az fi el pedig az xi pontnal a masodik legjobb el, es az xi pontok kulonboz}oek (emiatt az yi pontok is, de az lehet, hogy xi = yj ). Bizony t as: M asodik f azis: 1  t 7.4 All as: 1 1 1 2 2 2 2 Ha van olyan su s, amire legalabb ket el illeszkedik, akkor van rota io. Induljunk ki egy su sbol, es lepjunk felvaltva a legrosszabb es a masodik legjobb elen, addig amg egy rota iot nem kapunk. Nem tudunk

elakadni, mert ha egy su s foka egy, akkor a ra illeszked}o el oda-vissza iranytott, ezert a szomszedja is les}ofoku.  A (y ; e ; x ; f ; y ; e ; x ; f ; : : : yk ; ek ; xk ; fk ) rota io eliminalasan most azt ertjuk, hogy minden yi pontnal kihagyjuk az fi -nel rosszabb eleket, az fi elt pedig megiranytjuk xi -b}ol yi -be. Sikertelen elimina ion azt ertjuk, amikor ezt nem tudjuk megtenni, vagyis ha egy fi elt toroltunk. Ez sak akkor lehet, ha az xi pont egyuttal egy yj pont is, es mivel fi xi -nel a masodik legjobb el, ezert fi -t az ei el miatt toroltuk, vagyis ei = fj es yi = xj . Mivel xj -nel az ei = fj el a legrosszabb es egyuttal a masodik legjobb, ezert fi = ej es xi = yj . Igy induk ioval azt kapjuk, hogy ha sikertelen az elimina io, akkor a rota io egy olyan paratlan hosszu iranytott koron halad vegig ketszer fordtott iranyban, aminek a su saira nem illeszkedik tobb el. Ebben az esetben nin s stabil

parostas Ha az elimina io sikeres, akkor konnyen lathato, hogy a fenti tulajdonsagok ervenyben maradnak a kapott grafra. Bizony t as: 1 1 1 1 2 2 2 2 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 2 1 1 Egy rota io sikeres eliminalasaval kapott preferen iarendszerben pontosan akkor van stabil parostas, ha az eredetiben.  t 7.5 All as: 26 http://www.doksihu Ha a redukalt grafban van stabil parostas, akkor az az eredetiben is stabil parostas, mert a redukalt grafban az fi elt sak az yi su snal lehet dominalni, ezert az }ot dominalo el dominalja az yi-nel kihagyott eleket is. Ha az eredeti grafban van stabil parostas es nem hasznal torolt eleket, akkor ez stabil parostas a redukalt grafban is. Ha az M stabil parostas tartalmaz egy elt, amit az yi pontnal toroltunk, akkor az fi elt sak az ei el tudja dominalni, vagyis ei 2 M . Emiatt az fi elt sak az ei el tudja dominalni, vagyis ei 2 M

, es gy induk ioval ej 2 M minden j = 1; 2; : : : k-ra. Igy a redukalt gafban az M n fei : i = 1; : : : kg [ ffi : i = 1; : : : kg egy stabil parostas.  A fentiek alapjan ha sorban keresunk es eliminalunk rota iokat, akkor el}obb-utobb vagy sak diszjunkt elek maradnak, amik egy stabil parostast alkotnak az eredeti grafban is, vagy egy sikertelen elimina iohoz erunk, amikor nin s stabil parostas az eredeti grafban sem. Bizony t as: 1 1 2 1 1 2 2 Az itteni es a paros preferen iarendszereknel ertelmezett rota ioknak nem veletlenul ugyanaz az elnevezese. Egy paros grafnal az els}o fazis a Gale-Shapley algoritmusra hasonlt, a vegen az iranytott elek halmaza a uoptimalis es a lanyoptimalis stabil parostas unioja lesz. A masodik pedig a rota iok eliminalasara hasonlt, a vegyes grafban a rota iok kozt mindig ott lesznek a paros grafoknal ertelmezett rota iok, amik eliminalasa ugyanazt jelenti, mint

korabban. Emellett viszont lesznek mas rota iok is, meghozza amiket ugy de nialhatunk, hogy a korabbi de n ioban az U -t es V -t fel sereljuk (ez alapjan paros preferen iarendszereknel megkulonboztethetnenk urota iokat es lanyrota iokat). Akarhogy is eliminalunk paros grafoknal, az iranytott elek mindig ket stabil parostas uniojat alkotjak, az egyiket az U -bol V -be iranytott elek, a masikat a V -b}ol U -ba iranytott elek. 7.6 Megjegyz es: 7.2 A minimalis sulyu stabil parostas NP-teljes Feder [6℄-ben bizonytas nelkul kimondja, hogy a 2-SAT problema polinomialisan visszavezethet}o a stabil parostas problemara, s}ot ugy, hogy a 2-SAT-ot kielegt}o, legtobb 0-t tartalmazo megoldas keresese a minimalis sulyu stabil parostasra vezet vissza. A legtobb 0-t tartalmazo megoldas keresese pedig NP-teljes, mert erre visszavezethet}o a maximalis stabil halmaz keresese. Tehat ebb}ol kovetkezik az

alabbi. 7.7 T etel: A minimalis sulyu stabil parostas keresese NP-teljes. Adott egy 2-SAT problema, olyan preferen iarendszert fogunk megadni, amiben pontosan akkor van ki si sulyu stabil parostas valamilyen elsulyozasra, ha a 2-SAT-nak van megoldasa es ekkor a minimalis sulyu stabil parostas a legtobb 0-t tartalmazo megoldasnak felel meg. Legyenek a 2-SAT valtozoi x ; x ; : : : xn . Minden valtozonak feleltessunk meg egy negy pontu kort a keszul}o grafban, az xi valtozonak a (vi ; ei ; vi ; ei ; vi ; ei ; vi ; ei ; vi ) kort. Legyen Bizony t as: 1 2 1 27 1 2 2 3 3 4 4 1 http://www.doksihu e1i <v2 e2i <v3 e3i <v4 e4i <v1 e1i . Az xi valtozo 1 erteke annak fog megfelelni, hogy a stabil parostasban benne vannak az e1i es e3i elek, az 0 pedig annak, hogy az e2i es e4i elek vannak benne. Ha xi xj egy kloz, akkor huzzuk be a grafba a (vi2 ; vj2) elt, es ez <v szerint legyen az e1i es e2i

elek kozott, <v szerint pedig az e1j es e2j elek kozott. Ha pedig egy klozban xi negaltja van, akkor az uj el vegpontja vi1 legyen, es <v1 szerint e1i es e4i kozt legyen. Egy su snal i i i i i j kulonboz}o klozokhoz tartozo elek mindegy, milyen sorrendben vannak a su s rendezeseben. Ekkor konnyen ellen}orizhet}o, hogy ha egy stabil parostas sak a valtozoknak megfeleltetett eleket tartalmaz, akkor ez megad egy megoldast a 2-SAT-ra, es fordtva. Most vegyuk azt az elsulyozast, hogy az ei eleknek 1 legyen a sulya, a klozokhoz rendelt eleknek n + 1, a tobbi elnek pedig 0. Ekkor pontosan akkor van legfeljebb n sulyu stabil parostas, ha van megoldasa a 2-SAT-nak es ekkor a minimalis sulyu stabil parostasnak a legtobb 0-t tartalmazo megoldas felel meg. i 1 vi1 vi4 vj1 vi2 vj2 vi3 vj4 vj3 7. abra az xi es xj valtozokhoz es az xi xj klozhoz konstrualt elek  28 http://www.doksihu 8. Egy eb 

altal anos t asok Kedv sinalonak megemltjuk nehany altalanostasat a stabil parostasoknak. 8.1 Stabil b-parostasok Mind paros, mind tetsz}oleges prefern iarendszerben ertelmezhetjuk a stabil parostasok egy altalanostasat, ahol egy v pontnak nem sak egy parja lehet, hanem legfeljebb egy adott b(v) nemnegatv egesz kvota. Tehat egy (G; O) preferen iarendszerben egy M elhalmazt akkor nevezunk stabil b-parostasnak, ha egyreszt b-parostas, vagyis minden v su sra legfeljebb b(v) darab M -beli el illeszkedik, masreszt minden e 2 E n M elnek van egy olyan v vegpontja, amire illeszkedik b(v) M -beli el es ezek mind jobbak v-nel mint e. Paros preferen iarendszer stabil b-parostasainak tulajdonsagairol olvashatunk Baou es Balinski [1℄ ikkeben, a poliederenek egy lerasarol pedig Fleiner Tamas [7℄ ikkeben. Tetsz}oleges preferen iarendszerben Irving algoritmusanak altalanostasat talalhatjuk Ce hlarova

es Fleiner Tamas [3℄-ben. 8.2 Matroid-kernelek A matroid-kernel foglmat Fleiner Tamas vezette be [8℄-ben, ez a paros preferen iarendszerben lev}o stabil parostasoknak, s}ot stabil b-parostasoknak is altalanostasa. Adott ket matroid, M es M egy kozos S alaphalmazon, es ket sulyfuggveny, ; : S ! R . S egy K reszhalmazat M M -kernelnek nevezzuk, ha K kozos fuggetlen halmaza M -nek es M -nek es minden x 2 S n K elemhez van olyan i 2 f1; 2g es egy Cx  K , hogy x [ Cx egy kor Mi -ben es i(y) 6 i(x) minden y 2 Cx-re. 1 2 1 1 2 2 1 2 8.1 T etel: (Fleiner) van M M -kernel. 1 Minden M 1 es M 2 matroidparhoz es 1 ; 2 :S!R sulyfuggvenyhez 2 Ha adott egy (G = (U; V ; E ); O) paros preferen iarendszer es egy b : U [ V ! N fels}o korlat a pontokon, akkor ha M az a part ios matroid E -n, hogy az egy U -beli pontra illeszked}o elek vannak egy osztalyban es b adja a fels}o korlatot, M pedig hasonloan V -re, (e) illetve

(e) pedig az e helyezese az U illetve V -beli vegpontjanal, akkor az M M -kernelek pont a stabil b-parostasoknak felelnek meg. 1 2 1 1 2 2 8.3 Graf-kernelek A tetsz}oleges grafban ertelmezett stabil parostasnak is altalanostasa a kovetkez}o fogalom. Egy iranytott grafban egy ponthalmazt kernelnek nevezunk, ha egyreszt stabil, masreszt min29 http://www.doksihu den rajta kvul lev}o pontbol vezet el a halmazba. Egy adott preferen iarendszerhez ha a graf elgrafjat megiranytjuk ugy, hogy a rosszabbik elb}ol mutasson a jobbikba el, akkor az iranytott graf kerneljei pont a preferen iarendszer stabil parostasai lesznek. Igy persze kernel nem feltetlenul letezik. Boros es Gurvi h [2℄ bizonytottak egy tetelt kernel letezeser}ol perfekt grafok bizonyos iranytasaiban, jatekelmeleti modszereket hasznalva (S hrijver Combinatorial optimization m}u konyveben van egy rovidebb bizonytas). Egy D = (V; A)

iranytott grafot egy G = (V; E ) egyszer}u iranytatlan graf szuperiranytasanak nevezunk, ha D minden ele G egy elenek megiranytasa (D-ben lehetnek oda-vissza elek is) Egy iranytott grafot nevezzunk normalisnak, ha minden fesztett klikkjeben van kernel (vagyis egy pont, amibe a klikk tobbi pontjabol vezet el). Egy G = (V; E ) iranytatlan grafot kernel-megoldhatonak nevezunk, ha minden normalis szuperiranytasaban van kernel. 8.2 T etel: (Boros, Gurvi h) Minden perfekt graf kernel-megoldhato. Ennek a tetelnek a megfordtasa kovetkezik az er}os perfekt graf tetelb}ol, amit Berge sejtett es Chudnovsky, Robertson, Seymour es Thomas bizonytottak be 2002-ben [4℄. Egy graf pontosan akkor perk > 2-re. 8.3 T etel: (Chudnovsky, Robertson, Seymour, Thomas) fekt, ha nin s benne fesztett reszgrafkent C2k+1 es C2k+1 A C k graf nem kernel-megoldhato, mert ha korbe iranytjuk az eleket, az egy normalis iranytas es

nin s benne kernel. A komplementere, C k sem kernel-megoldhato, mert ha egy korre rajzoljuk a pontokat ugy, hogy a koron szomszedosak kozt ne fusson el, es azt az iranytast vesszuk, hogy a koron masodszomszedos pontok kozt men}o eleket orajaras szerint iranytjuk, a tobbi elt pedig mindket iranyba, az normalis iranytas, amiben nin s kernel. Emellett, ha egy graf tartalmaz fesztett reszgrafkent egy olyan grafot, ami nem kernel-megoldhato, akkor }o maga sem az, mert a reszgraf egy normalis, de kernel nelkuli iranytasat kiegesztve ugy, hogy a reszgrafbol kimen}o eleket kifele iranytjuk, a tobbi elt pedig mindket iranyba, egy normalis iranytast kapunk, amiben nin s kernel, mert ha lenne, akkor a reszgrafba es}o resze abban kernel lenne. Tehat a fenti ket tetel kovetkezmenye az alabbi 2 +1 2 +1 8.4 T etel: Egy graf pontosan akkor kernel-megoldhato, ha perfekt. Hivatkoz asok [1℄ M. Baou, M Balinski:

Many-to-many mat hing: stable polyandrous polygamy (or polygamous polyandry) Dis rete Applied Mathemati s, 101 (2000) 1-12 [2℄ E. Boros, V Gurvi h: Perfe t graphs are kernel solvable Dis rete Math, 159(1-3): 35-55, 1996. 30 http://www.doksihu [3℄ K. Ce hlarova, T Fleiner: On a generalization of the stable roommates problem EGRES Te hni al Report No. 2003-03 [4℄ M. Chudnovsky, N Robertson, PD Seymour, R Thomas: The strong perfe t graph theorem Kezirat [5℄ V.MF Dias, GD da Fones a, CMH de Figeiredo, JL Szwar ter: The stable marriage problem with restri ted pairs. Theoreti al Computer S ien e, 306 (2003) 391-405 [6℄ T. Feder: A new xed point approa h for stable networks and stable marriages J Comput System S i., 45(2): 233-284, 1992 [7℄ T. Fleiner: On the stable b-mat hing polytope EGRES Te hni al Report No 2002-3 [8℄ T. Fleiner: A xed-point approa h to stable mat hings and some appli ations Math Oper Res. 28(1): 103-126, 2003 [9℄ T. Fleiner: A matroid generalization

of the stable mat hing polytope In Pro IPCO VIII (B. Gerards, K Aardal, eds), Springer-Verlag Berlin 2001, 105-114 [10℄ D. Gale, LS Shapley: College admissions and stability of marriage Amer Math Monthly, 69(1): 9-15, 1962. [11℄ F. Galvin: The list hromati index of a bipartite multigraph J Combin Theory Ser B, 63(1): 153-158, 1995. [12℄ D. Gus eld, RW Irving: The stable marriage problem: stru ture and algorithms MIT Press, Cambridge, MA, 1989. [13℄ R.W Irving: An eÆ ient algorithm for the "stable roommates" problem J Algorithms, 6(4): 577-595, 1985. [14℄ R.W Irving, P Leather, D Gus eld: An eÆ ient algorithm for the "optimal" stable marriage. Journal of the ACM, 34: 532-543, 1987 [15℄ U.G Rothblum: Chara terization of stable mat hings as extreme points of a polytope Math. Programming, 54(1, Ser A): 57-67, 1992 [16℄ J.H Vande Vate: Linear programming brings marital bliss Oper Res Lett, 8(3): 147-153, 1989. 31