Javító út keresés páros gráfokban, magyar módszer

  Páros gráfok esetén a javító út keresés (és így a maximális elemszámú párosítás keresés) algoritmusát Kőnig Dénes és Egerváry Jenő dolgozták ki. Mindkettejüket megemlíti a Természet Világa matematikáról szóló különszámában megjelent, Császár Ákos által írt cikk. A Budapesti Műszaki Egyetemen Egerváry Jenő tiszteletére szobrot emeltek. Az eljárást tiszteletükre magyar módszernek nevezik. Az eljárás történetéről és az elnevezés Frank András írt cikket.

A magyar módszer tulajdonképpen a már ismertetett javító út kezdemények növelésére szolgáló algoritmus páros gráfokban történő futtatása egy észrevétellel megtoldva. Páros gráfokban minden javító út egyik végpontja alsó, másik végpontja felső pont. Így javító út keresésünket/javító út kezdemények növelését kezdhetjük az alsó párosítatlan pontokból. Tehát a korábbi eljárásunkat futtassuk úgy, hogy R az alsó párosítatlan pontok halmaza legyen.

Tétel: A fenti algoritmus outputja helyes.

Bizonyítás: Sikeres keresés esetén az állítás nem kétséges. Sikertelen keresés esetén azt kell belátnunk, hogy nincs is javító út, azaz az aktuális párosítás optimális. Az alsó címkézett pontok egy Kőnig-akadályt adnak, amely bizonyítja, hogy minden párosítás kihagy annyi pontot az alsó csúcsok közül amennyit M is kihagy.

A javító utak keresésére vonatkozó eljárást használhatjuk a maximális párosítás keresésére szolgáló sémában. Az így kapott algoritmust (ami a teljes magyar módszer) egy példán keresztül érthetjük meg.

A javító útkezdemények növelése páros gráfokban másképpen is megvalósítható. Az eredeti címkézési eljárásban a címkéket párossával osztjuk ki. Ez fontos. Elképzelhető, hogy ha több olyan pontot is megcímkézünk, amelyek külső pontok szomszédai, akkor elképzelhető, hogy egy párosított csúcspár egyszerre kap ``belső'' címkét. így a hozzájuk talált javító út kezdeményeknek párosított élen kell tovább haladni, de ők ``blokkolják'' egymás folytatását. Páros gráfok esetén ez nem lehetséges. A kiinduló külső pontok az alsó párosítatlan pontok, így az eljárás folyamán mindig igaz lesz, hogy a külső pontok a címkézett alsó pontok, míg a belső pontok a címkézett felső pontok lesznek. így külső pontok címkézetlen szomszédai felső pontok lesznek, nem lehetnek párosítottak. A párhuzamos belső címkék kiosztása után ezek a legutoljára címkét kapott csúcsok címkéje mögötti javító út kezdemények párhuzamosan folytathatók a megfelelő alsó párok címkézésével. Az alábbiakban a magyar módszer címkézési eljárásának ezen változatát is ismertetjük.

Egy címkézési eljárás keretében a javító út kezdeménnyel elért csúcsoknak egy címkét adunk, amely az odavezető megtalált javító út kezdemény hosszát tartalmazza. Legyen C(i) az i címkét kapott csúcsok halmaza. Az egyes címkéket fázisokban osztjuk ki az i-edik fázisban osztjuk ki az i címkéket, a következő fázisban az eddig talált i hosszú javító út kezdeményeket próbáljuk meg eggyel megnövelni, azaz az i+1 címkéket kiosztani. újracímkézest elkerüljük. Páros gráfban a javító út egyik végpontja alsó, másik végpontja felső csúcs. így elég a keresést az alsó párosítatlan csúcsokból elindítani. A korábbi külső-belső címkék az új címkék paritása alapján határozhatók meg.

Ezekután az első néhány fázis leírása:

0. fázis: C(0)=az alsó párosítatlan pontok halmaza.

1. fázis: C(1)=N(C(0)). Azaz 1 címkét a 0 címkét kapott pontok szomszédai kapják. Ezek felső csúcsok lesznek. Ha C(1) üres, akkor a keresés sikertelen. Ha C(1) nem üres és valamelyik eleme párosítatlan csúcs, akkor találtunk egy javító utat. Ha C(1) nem üres és mindegyik eleme párosított, akkor a 2. fázissal folytatjuk eljárásunkat.

2. fázis: C(2)=C(1)-beli csúcsok párosított szomszédja. újracímkézéstől nem kell félni, mert (a továbbiakban is) a párosított pontpárak ``együtt'' kapnak címkét, így egy éppen címkét kapott felső pont párja automatikusan címkézetlen.

3. fázis: C(3)=N(C(2))-C. Azaz 3 címkét a 2 címkét kapott pontok eddig nem címkézett szomszédai kapják. Ezek felső csúcsok lesznek. Ha C(3) üres, akkor a keresés sikertelen. Ha C(3) nem üres és valamelyik eleme párosítatlan csúcs, akkor találtunk egy javító utat. Ha C(3) nem üres és mindegyik eleme párosított, akkor a 4. fázissal folytatjuk eljárásunkat.

A fázisok a fenti alternálás rendjében folytatódnak.

Ha keresésünk sikeres, akkor a legrövidebb javító utat találjuk meg.

Az érdeklődő hallgatók számára megemlítjük Frank András egy magyar cikkét a magyar módszerről és általánosításairól.