Javító és majdnem javító utak A deficites Hall-tétel alapján elméletileg meghatározhatjuk, hogy egy G = (A, B; E) páros gráfban mekkora a legnagyobb párosítás mérete. Ehhez azonban első ránézésre az összes X ⊂ A részhalmaz deficitjét meg kéne határozni, ami már |A| = 20 csúcs esetén is 220 ≈ 1000000 részhalmaz vizsgálatát jelentené. Ráadásul még ekkor sem volna konkrétan a kezünkben egy maximális párosítás. Ennél azonban ügyesebben is nekifoghatunk egy egyszerű, de hasznos észrevétel segítségével, amely ráadásul nem csak páros gráfokban használható. Definíció. Legyen G = (V ; E) egy tetszőleges gráf és P ⊂ E egy párosítás. Egy út javító út P -re nézve, ha két P által fedetlen csúcsot köt össze, és minden második éle P -ben van. ♦ Megjegyzés. A „minden második éle P -ben van” helyett azt is mondhattuk volna, hogy az élei felváltva P -n kívüliek, illetve P -beliek. Ugyanis ha minden második éle P -ben van, a köztes élek nem lehetnek P -ben, hiszen P párosítás. ♦ Állítás. Legyen G = (V ; E) egy tetszőleges gráf és P ⊂ E egy párosítás. Ha van javító út P -re nézve, akkor van P -nél nagyobb párosítás. Bizonyítás. Módosítsuk P -t úgy, hogy a javító út P -beli elemeit kivesszük belőle, a P -n kívüli éleit pedig bevesszük P -be. Az így kapott P ′ élhalmaz párosítás lesz, hiszen egyik csúcsnál sem lehet két éle: a javító úton kívül nyilván nem, mert ott P és P ′ megegyezik; a javító út két végpontját P nem fedte le, így nem romolhattak el; a javító út belső pontjaira pedig mind P -nek, mind P ′ -nek egy-egy éle illeszkedik. Mivel a javító út P -n kívüli éllel indul és végződik, |P ′ | = |P | + 1. Párosítás növelése javító úttal egy páros gráfban.
1
A
1
A
1
A
2
B
2
B
2
B
3
C
3
C
3
C
4
D
4
D
4
D
5
E
5
E
5
E
6
F
6
F
6
F
Egy párosítás páros gráfban, egy javító út (1-C-4-E-3-A) és a javítás eredménye.
Hamarosan látunk módszert arra, hogy hogyan lehet javító utakat keresni, és ezáltal növelni a párosításunk méretét. De vajon így biztosan találunk egy lehető legnagyobb párosítást? Vagy kifulladhat a módszer hamarabb is? A következő tétel adja a megnyugtató választ. 1
2
Tétel. Legyen G = (V ; E) egy tetszőleges gráf és P ⊂ E egy párosítás. Ha nincs javító út P -re nézve, akkor P egy legnagyobb párosítás. Bizonyítás. Legyen P ′ egy tetszőleges párosítás. Jelölje S a P és P ′ élhalmazok (súlyozott) unióját, melyben P ∩ P ′ éleit kétszer vesszük be (mint párhuzamos éleket). Azt fogjuk belátni, hogy P -nek legalább annyi éle van S-ben, mint P ′ -nek, vagyis |P | ≥ |P ′ |; ez igazolja, hogy nincs P -nél nagyobb párosítás. Az S élei által alkotott GS = (V ; S) gráfban minden csúcs foka legfeljebb kettő (miért is?), és a kettő fokú csúcsok egyik éle P -beli, a másik P ′ -beli. GS összefüggőségi komponensei tehát párhuzamos élek, körök vagy utak (az esetleges izolált csúcsokat nulla hosszúságú utaknak tekintjük). A körökben a P -beli és P ′ -beli élek száma megegyezik, hiszen azok felváltva követik egymást; ugyanez fennáll a párhuzamos élek alkotta komponensekre is. Az utakban nem lehet több P ′ -beli él, mint P -beli, hiszen egy ilyen út javító út volna P -re nézve, ami a feltevésünk szerint lehetetlen. Ezzel az állítást beláttuk.
P ∩ P ′ élei
körök
utak
1. ábra. P és P ′ élei,
Megjegyzés. Minden, amit eddig javító utakról mondtunk, páros és nem páros gráfokra egyaránt igaz. Innentől viszont csak páros gráfokkal foglalkozunk, mert az alább ismertetendő eljárásban kihasználjuk a gráf páros voltát. Nem páros gráfokban is lehet hatékonyan legnagyobb párosítást keresésni, ezt azonban mi nem tárgyaljuk. Javító utak keresése páros gráfokban szélességi kereséssel Adott a G = (A, B; E) páros gráf, ebben kell keresnünk egy legnagyobb párosítást. Ezt úgy tesszük, hogy mohón keresünk egy P kiindulási párosítást, amit majd addig növelünk, amíg egy legnagyobb párosítást nem kapunk. Az alább részletezett eljárást először szemléletesen, kis példákon „kézzel” alkalmazható módon tárgyaljuk, a fejezet végén vázoljuk, hogy nagyobb példákon hogyan lehet kivitelezni az eljárást számítógép segítségével. Előkészületek: Az eljárásnál az elején el kell dönteni, melyik osztály felől indulunk. Most például a párosítást B felől fogjuk keresni. Az eljárás során fontos, hogy B-ből A-ba csak párosításon kívüli, A-ból B-be pedig csak párosításbeli élen léphetünk. Ezt úgy biztosítjuk, hogy megirányítjuk G éleit: a párosítás élei mindig A-ból B-be mutassanak, a többi B-ből A-ba. Amíg nincs párosításunk (P = ∅), minden él B-ből A-ba mutat. (Természetesen, ha A felől keresnénk párosítást, fordítva irányítottuk volna G éleit.) Az eljárás során az aktuális párosítást az élek irányítása jelzi, melyet időnként változtatni fogunk. Az aktuális párosítást mindig P -nek fogjuk hívni. Kis példákon persze az irányítás helyett az élek vékony / vastag rajzolásával is jelezhetjük, hogy mely élek vannak a párosításban.
3
Első lépés: mohón keresünk egy párosítást. Sorra vesszük B csúcsait, és megvizsgáljuk az éppen aktuális v csúcs szomszédait. Ha van közöttük olyan u csúcs, ami még nem szerepel a párosításban (azaz u-nak nincs szomszédja A-ban (az irányítást figyelembe véve!)), belevesszük; magyarán a vu él irányítását megfordítjuk. Ha az utolsó csúcsot is megvizsgáltuk B-ben, egy új él bevételével nem bővíthető (de nem feltétlenül egy lehető legnagyobb) párosítást kaptunk (az A-ból B-be irányított élek ezek). Második lépés: Javító utakat keresünk. Az irányítás miatt minden út felváltva lép P -n kívüli és P -beli éleken, így nekünk egy b ∈ B fedetlen csúcsot egy a ∈ A fedetlen csúccsal összekötő utat kell keresnünk; az automatikusan javító út lesz. Javító út keresésének lépései: Készítünk egy kétsoros táblázatot. A fölső sor az elérési lista, az alsó a honnan lista. (1) Felírjuk az elérési listába B fedetlen csúcsait (az összeset). Az elérési listában szereplő csúcsokat listázottnak hívjuk; ezeket fogjuk sorban átvizsgálni. Alattuk üres a honnan lista. (2) Legyen v az elérési lista első nem átvizsgált eleme. Írjuk az elérési lista végére v eddig nem listázott szomszédait (innentől ezek is listázottak), és mindegyik alá (a honnan listába) írjuk föl v nevét. A v csúcsot ezután átvizsgáltnak hívjuk. Ezt a folyamatot nevezzük a v csúcs átvizsgálásának. (3) Ismételjük az előző lépést addig, míg 1) fedetlen A-beli csúcsot veszünk föl az elérési listába, vagy 2) az elérési lista összes csúcsát át nem vizsgáljuk. 1)-es eset: fedetlen A-beli csúcsot vettünk az elérési listába. Hívjuk ezt a csúcsot v1 -nek. A honnan lista alapján tudjuk, hogy v1 -et melyik csúcsból értük el; legyen ez v2 . Persze v2 szerepel v1 előtt az elérési listában, a honnan listából látjuk, hogy őt v3 -ból értük el stb., így a feljegyzések alapján visszaérünk egy B-beli fedetlen csúcsba. Ezen csúcsok sorozata egy irányított út, mely két fedetlen csúcsot köt össze, azaz a fenti megjegyzés szerint javító út P -re nézve. A javító út éleinek irányítását megfordítva (azaz felcserélve a P -beli és az azon kívüli éleit) kapunk egy P -nél nagyobb párosítást; ezután a fenti eljárással újra kereshetünk javító utat az új, nagyobb párosításra nézve. Mivel a fedetlen csúcsok száma minden lépésben csökken, előbb-utóbb véget ér az eljárás azzal, hogy előáll a 2)-es eset. 2)-es eset: az elérési lista összes elemét átvizsgáltuk, de nem értünk el fedetlen csúcsba. Ekkor az alábbi tétel szerint megtaláltuk a lehető legnagyobb párosítást, ráadásul bizonyítékot is kapunk erre: Tétel. Tegyük föl, hogy a fenti eljárás során előáll a 2)-es eset. Legyen rendre X, illetve Y az elérési listában szereplő B-beli, illetve A-beli csúcsok halmaza. Ekkor N (X) = Y , és X deficite éppen |B| − |P |, azaz nincs a P -nél nagyobb párosítás. Bizonyítás. Legyen F ⊂ X a B-beli fedetlen csúcsok halmaza. Ekkor persze P pontosan |F | csúcs híján fedi B-t, azaz |B| − |P | = |F |. Legyen v ∈ X egy tetszőleges csúcs, u pedig a v egy tetszőleges szomszédja G-ben (tehát az eredeti, irányítatlan gráfban). N (X) = Y igazolásához be kell látnunk, hogy u ∈ Y . Ha vu ∈ P , akkor v nem fedetlen, tehát a honnan listában szerepel alatta egy csúcs. Mivel B felé csak P -beli élen léphettünk és v-t csak egy P -beli él fedheti, ez a csúcs az u; emiatt u is szerepel az elérési listában, tehát u ∈ Y . Ha vu ∈ / P , akkor v
4
átvizsgálása során u-t bevettük az elérési listába (vagy már eleve ott volt), tehát ismét u ∈ Y . Ezzel azt láttuk be, hogy N (X) ⊂ Y . Mivel minden Y -beli csúcsot egy X-beli csúcs (nevezetesen a honnan listában alatta szereplő) szomszédjaként vettünk az elérési listába, N (X) = Y . Már csak azt kell megmutatni, hogy X deficite éppen |F |, vagyis hogy |X| − |N (X)| = |X| − |Y | = |F |. Ehhez azt gondoljuk meg, hogy P egy teljes párosítás Y és X \ F között. Először lássuk be, hogy Y minden elemének van P -beli párja X \ F -ben. Legyen u ∈ Y . A 2)-es eset szerint P lefedi u-t; legyen tehát v az u P -beli szomszédja. Ekkor v az u átvizsgálása során bekerült az elérési listába1, tehát v ∈ X \ F . Másodszor lássuk be, hogy X \ F minden elemének van P -beli párja Y -ban. Ha v ∈ X \ F , akkor v-nek persze van P -beli párja, és N (X) = Y miatt az Y -beli. Példa: Lássuk az eljárás megvalósítását az alábbi képen látható gráffal illusztrálva. A
A
B
C
D
E
F
G
H
1
2
3
4
5
6
7
8
A
B
C
D
E
F
G
H
1
2
3
4
5
6
7
8
B
A
B
2. ábra. Fölül látjuk a gráfot magát; alatta a mohón talált párosítással és az annak megfelelő irányítással. Végezzük el ezen a gráfon és a kiindulási párosításon az eljárás lépéseit! Elérési lista: 6 7 8 D B E 4 2 5 Honnan: 6 6 7 D B E
F 2
A lépéseket | jelek választják el egymástól. A 4. lépésben a 8 nevű csúcsot vizsgáljuk át, ahonnan azonban egy új csúcsot sem érünk el, ezért az elért csúcsok listája nem bővül. Hasonló a helyzet a 8. lépésben.
Mivel F fedetlen A-beli csúcs, a táblázatból kiolvasható F − 2 − B − 6 út javító út lesz. Elvégezve a javítást az alábbi párosítást kapjuk:
1Vagy
esetleg már u átvizsgálása előtt is ott volt. Előfordulhat ez?
5
A
A
B
C
D
E
F
G
H
1
2
3
4
5
6
7
8
B
3. ábra. A növelt párosítás. Erre újra elvégezve az eljárás lépéseit, a következő táblázat adódik: Elérési lista: 7 8 D E Honnan: 7 7
4 5 D E
Az eljárás úgy ér véget, hogy átvizsgáltuk az összes listázott csúcsot, és nem tudunk több csúcsot listázni. Ekkor a Tétel szerint az X = {7; 8; 4; 5} = {4; 5; 7; 8} ⊂ B csúcshalmaz szomszédsága N (X) = Y = {D; E} (ezt ellenőrizhetjük is az eredeti gráfon). Az X halmaz deficite tehát kettő, és az aktuális párosításunk kettő híján minden csúcsot fed B-ben; összevetve kapjuk, hogy ő egy legnagyobb párosítás. Számítógépes implementálás Kis gráfok esetében még át tudjuk tekinteni a fenti eljáráshoz szükséges információkat a táblázat és a gráf ábrája segítségével. Azonban nagy gráfok esetében, melyeknél már a vizuális megjelenítés sem célszerű, természetes a kérdés, hogy számítógéppel hogyan lehet a fenti eljárást kivitelezni, a szükséges adatokat tárolni. A gráfokat többféleképpen lehet és szokás kezelni, a legalkalmasabb adattárolási struktúra kiválasztása függ a gráf és a feladat jellegétől is. Mi most csak egy változatot mutatunk be. Gráf tárolása: A csúcsokat sorszámozzuk 1-től n-ig (n a gráf csúcsszáma); majd készítünk egy listát, melyben minden sorszámhoz (azaz csúcshoz) egy újabb listát rendelünk, amely az ő szomszédjait tartalmazza (az aktuális irányítást figyelembe véve). Ez a SZOMSZ lista; egy v csúcsra tehát SZOMSZ(v) egy, a v szomszédait tartalmazó lista. Érdemes bevezetni egy FEDETT listát, ami minden csúcsról eltárolja, hogy fedi-e P . Például ha az uv irányított él, u ∈ A, v ∈ B, szerepel a gráfban, de nem szerepel a párosításban, akkor ő B-ből A felé van irányítva, tehát SZOMSZ(v) tartalmazza u-t, de SZOMSZ(u) nem tartalmazza v-t. Ha ezt az élt bevesszük a párosításba, azt úgy adminisztráljuk, hogy a v szomszédai közül kivesszük u-t, és az u szomszédai közé bevesszük v-t, valamint alkalmasan módosítjuk a FEDETT értékeket is. Elérési lista (ELERESI): Az eljárás szerinti sorrendben írjuk bele az elért csúcsokat (azok sorszámát). Honnan lista (HONNAN): Az eljárás szerinti sorrendben írjuk bele a honnan értéket (a megfelelő csúcs sorszámát); az elérési lista elején szereplő, fedetlen B-beli csúcsoknál üres értéket (vagy megfelelő jelölőt) használunk. Csúcsok állapotlistája (ALLAPOT): készítünk egy n elemű tömböt, és minden elem háromféle lehet a csúcsok háromféle állapotának megfelelően, amit most számokkal
6
jelölünk: 0: még nem listázott csúcsok; 1: listázott, de még nem átvizsgált csúcsok; 2: átvizsgált csúcsok. Kezdetben minden 1 ≤ i ≤ n számra ALLAPOT(i) = 0. A csúcsok állapotát az eljárás lépéseinek megfelelően módosítjuk: amikor listába kerül, 1-re, amikor átvizsgáljuk, 2-re. Az eljárás során az ELERESI lista soron következő i elémenek szomszédait kell áttekinteni, azaz végig kell mennünk a SZOMSZ(i) elemein. Ezek közül azon j csúcsokat, melyeknél ALLAPOT(j) = 0, beteszzük az ELERESI lista végére, ALLAPOT(j)-t 1re változtatjuk, a HONNAN lista megfelelő elemét i-re módosítjuk, majd ha végigvettük SZOMSZ(i) elemeit, ALLAPOT(i)-t 2-re állítjuk. A csúcsok listázásánál a FEDETT lista segítségével ellenőrizzük, hogy P fedi-e az adott csúcsot. A fenti példa tárolása és az eljárás első lépése valahogy így néz ki. A számítógép persze a betűvel jelölt csúcsokat is sorszámként tárolná (9, 10, . . . , 16). A gráf tárolása (csúcsok és szomszédaik; helytakarékossági okokból a csúcsok alá írjuk azok szomszédait): Csúcs: 1 2 3 4 5 6 7 8 A B C D E F G H Szomszédok B F G D D E 1 2 3 4 5 listája: B E Állapotlista csúcsai: 1. lépés: 2. lépés: 3. lépés: 4. lépés: 5. lépés: 6. lépés: 7. lépés: 8. lépés: 9. lépés:
1 0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 1 1 1 2
3 0 0 0 0 0 0 0 0 0
4 0 0 0 0 1 1 1 2 2
5 0 0 0 0 0 0 1 1 1
6 1 2 2 2 2 2 2 2 2
7 1 1 2 2 2 2 2 2 2
8 1 1 1 2 2 2 2 2 2
A 0 0 0 0 0 0 0 0 0
B 0 1 1 1 1 2 2 2 2
C 0 0 0 0 0 0 0 0 0
D 0 1 1 1 2 2 2 2 2
E 0 0 1 1 1 1 2 2 2
2 0 0 0 0 0 0 0 0 1
G 0 0 0 0 0 0 0 0 0
H 0 0 0 0 0 0 0 0 0
