Javító út kezdemények növelése

V'egig egy tetszőleges G gráfban dolgozunk, amelyben adott egy M pároítás.

Legyen v0, e1, v1, e2, v2, ..., vk-2, ek-1, vk-1, ek, vk egy (M-re vonatkozó) javító út. Ennek a sorozatnak egy csúccsal befejeződő v0, e1, v1, e2, v2, ..., vi-1, ei, vi kezdőszelete is egy út, amelynek megvannak a következő tulajdonságai:

Az ilyen tulajdonságú utakat javító út kezdeményeknek nevezzük. Ezek nem szükségszerűen egy javító út kezdetei, csupán a megfelelő tulajdonságok meglétét kívánjuk. Azt mondhatjuk, hogy a javító út kezdemény egy olyan út, amelyről el tudjuk képzelni (gráfunkról és a benne lévő párosításról a fentieken túl nem tudva semmit), hogy kiterjeszthetők egy javító úttá.

Egy párosítatlan csúcs által alkotott egy hosszú sorozat egy 0 hosszú javító út kezdemény. Egy legalább 1 hosszú javító út kezdemény akkor és csak akkor javító út, ha utolsó pontja egy párosítatlan csúcs.

Algoritmusunk javító út kezdeményeket növel annak reményében, hogy egy párosítatlan csúcsot is elér a növelés, amikor is egy javító utat találunk. Több javító út kezdeményünk lesz, amelyeket párhuzamosan próbálunk növelni. Egy javító út kezdeménynek több alternatív folytatása/meghosszabítása/növelése is számon lehet tartva. Növelésünknek azonban lesz egy mohó vonatkozása: ha egy v csúcshoz találtunk odavezető P javító út kezdeményt, akkor ez a v csúcs más javító út kezdemények növeléséhez már nem használható. Tehát algoritmusunk által megtalált v-n átmenő javító út kezdemények mind P meghosszabbításai lesznek.

A fentieknek a következő következménye van. A megtalált javító út kezdemények pontjai és élei egy erdőt alkotnak. A javító út kezdemények első pontjai (ezek párosítatlan pontok) a fenti erdő egy-egy komponensének speciális/azonosító pontjai, a komponens gyökere. Minden csúcsba egyetlen javító út kezdeményünk lesz, amely első csúcsa leírja melyik komponenshez tartozik és az út maga megadja a komponensének gyökere és a pont közti egyetlen erdőbeli utat. Megfordítva az erdő bármely v pontjához tartozik egyetlen út, amely összeköti v-t a komponensének gyökerével. Ez az út a gyökérből v-hez vezető javító út kezdemény. Ezt az erdőt (M-re vonatkozó) kereső erdőnek nevezzük. Az alábbi tulajdonságok összegzik mit várunk el a kereső erdőtől, amennyiben nem ér el (a gyökerektől különböző) párosítatlan csúcsot:

A gyökerektől páros távolságra lévő csúcsokat külső csúcsoknak, a páratlan távolságra lévő csúcsokat belső csúcsoknak nevezzük. így a gyökerek külső csúcsok. Egy gyökértől elindulva az erdőben egy belső csúcshoz jutva annak egyetlen további szomszédja lesz az erdőben, az M által kijelölt párja. Külső ponthoz jutva erdőnk megfelelő komponense szétágazhat. A fenti tulajdonságok alapján az erdő nem-gyökér pontjait M élei párosítják. Minden párban egy külső és egy belső pont lesz.

Algoritmusunk egy kereső erdőből indul ki (ennek pontjaira mint címkézett csúcsokra hivatkozunk) és azt próbálja meg növelni. A korábban már említett mohó tulajdonság alapján az erdő növelése: címkézetlen pontokat címkézünk meg.

Mohó javító útkezdemény növelő algoritmus:


A fenti algoritmus egy naív algoritmus. A sikertelen futás nem jelenti azt, hogy nincs javító út a gráfban. A mohó jelleg miatt bizonyos javító út kezdeményeket nem veszünk figyelembe. Lehetséges, hogy a keresés egy v csúcsot belső pontként ér el. Ekkor a keresés következő lépése előírt, v párja felé halad tovább és v más szomszédja felé nem megy el. Egy esetleg kihagyott javíto út kezdemény v-t külső pontként éri el. Ennek a lehetőségnek a kihagyása eredményezheti a sikertelenséget. Páros gráfokban a színosztályok és a külső-belső kategóriák között egy szinkronizáltság van. Ezért a fenti algoritmus elég a javító út kereséshez.