Véletlen algoritmus páros gráfok párosítási problémájára

Elõször két rossz algoritmust ismertetünk. Majd ezek tanulságaként adjuk ezen fejezet fõ eredményét.

-1. változat: Vegyük G alsó-felsõ szomszédsági mátrixát, S_G-t, azaz azt a mátrixot, amely sorai az alsó pontokkal, oszlopai a felsõ pontokkal azonosított és egy a alsó pont-f felsõ pont párja által leírt sor-oszlop találkozásban 1 áll, ha af él és 0 áll, ha a és f nem összekötött. Azaz S_G-ben szereplõ 1-esek azonosíthatók G éleivel.

det S_G determináns kifejtésében egy nem 0 kifejtési tag egy n tényezõs szorozatnak felel meg, amely nem 0 volta azt jelenti, hogy minden tényezõ 1. Így n éllel állunk szemben, ami a kifejtési tag tulajdonság miatt egy teljes párosítás. Így ha a determináns nem 0, akkor tudjuk, hogy gráfunkban van teljes párosítás. Talán a determináns 0 voltából tudunk a teljes párosítás nem létére következtetni?

NEM! A determináns 0 voltából azonban nem következtethetünk a teljes párosítás hiányára. A hiány esetén valóban 0 lesz adetemináns, de ez akkor is elófordulat, ha vannak nem 0 kifejtési tagok (és így teljes párosítás G-ben), de azok kiejtik egymást.

det S^_G definiálható az algebrában szokott módon csak a számolás nem számok körében történei, hanem a `betûszámtan' keretében, eredménye egy polinom. Ha det S^_G értéke nem 0 (nem a 0 polinom), akkor gráfunkban van teljes párosítás. De most a kiegészítõ állítás is igaz: ha det S^_G=0, akkor gráfunkban nincs teljes párosítás, ugyanis a teljes párosítás det S^_G-hez egy nem 0 monom. Most ezt más monomok nem tudják kiejteni (szemben a számokkal történõ -1. változattal).

A fenti gondolatmenet természetes módon ad egy algoritmust, ami azonban nem hatékony. Ugyanais a det S^_G polinom kiszámolása nem egyszerû. A számmatrixoknálmegtanult módok (például Gauss-elimináció) nem alkalmazhatók. A determináns-polinom olyan sok monomot tartalmazhat, hogy fel sem írható. Annak ellenére, hogy det S^_G polinom nem egyszerû, azért vagy egy egyszerû oldala: kiértékelései egyszerûen elvégezhetõk.

Az elõzõ két változat tanulsága mellet az újdonság az lesz hogy algoritmusunk egy véletlen számokat használó algoritmus lesz.

Algoritmus:
1. lépés: Írjuk fel az S_G mátrixot.
2. lépés: Írjuk fel az S^_G mátrixot.
3. lépés: S^_G minden betûjéhez rendeljük {1,2,3,...,N-1,N} egy véletlen, uniform, független elemét.
4. lépés: S^_G betûi helyett a számokat írva egy numerikus mátrixot kapunk, amely determinánsát kiszámoljuk
5. lépés: Ha a determináns nem 0, akkor az output G-ben van teljes párosítás. Ha a determináns 0, akkor az output G-ben valószínûleg nincs teljes párosítás.

Az algoritmusunk olyan, hogy tévedhet: a det P^_G polinom lehet, hogy nem 0, de a helyettesíténél számaink választása olyan `szerencsétlen', hogy eltaláljuk egyik gyökét és így jutunk a 0 értékhez. Ez a tévedés teljesen más, mint a -1. változatnál. Itt a tévedés a számaink szerencsétlen genarálásból ered. A -1. változatnál a tévedés abból eredt, hogy lehet, hogy gráfunk, az input, trükkös. Így, ha az inputot egy ``ellenségünk'' adja, akkor az 1. változaton múló algoritmusban nem bízunk meg, míg a valódi algoritmus eredményere fogadhatunk, ha megértjük a következõ analízist.

Az algoritmusunkban szerepel egy N paraméter. Hogyan válasszuk meg? Mennyire bízhatunk algoritmusunk eredményében. Ehhez szükségünk lesz a következõ tétélre.

Tétel: (Schwartz-lemma) Legyen p(x₁, x₂, ... , x_n) egy nem 0 polinom. Legyen r₁, r₂, ... , r_n az {1,2, ..., N} halmaz függetlenül, uniform módon választott véletlen elemei. ekkor Prob(p(r₁, r₂, ... , r_n)=0)< nd/N, ahol d a p polinom fokszáma.

A tételt nem bizonyítjuk (lásd jegyzet). Az algoritmus analízisére vonatkozó következményeit azonben leszûrjük.

Következmény: Az algoritmusunk csak úgy hibázhat, hogy a G-ben valószínûleg nincs teljes párosítás outputot adja és G-ben van teljes párosítás. A N=|V||E| választással a hibázás valószínûsége 1/2.

Bizonyítás: Nyilvánvaló abból, hogy det S^_G polinom változó száma (a felhasznált betûk száma) S_G 1-eseinek szám, ami G éleinek száma, azaz |E|. det S^_G minden monomja n betû szorzata (n=|A|=|F|=|V|/2), azaz foka n=|V|/2. Így a Schwartz-lemma 1/2-del becsüli annak valószínûségét, hogy az algoritmus a 3. lépésben det S^_G egy gyökét generáljuk, feltéve, hogy det S^_G nem 0.

A hibázás valószínûsége csökkenthetõ, ha N értékét nagyobbra választjuk, vagy ha a fenti választással élünk, de algoritmusunkat többször futtatjuk és G-ben valószínûleg nincs teljes párosítás outputot akkor hírdetjük ki, ha minden futás esetén erre jutottunk. A determinisztikus algoritmusokkal szemben a véletlen algoritusok ismételt futásának (ugyanazon inputon) van értelme. Az ismételt futattásokkal nyert algoritmusunk akkor és csak akkor hibázik, ha minden független futása hibázott. Azaz k-szori ismétléssel elérjük, hogy a hibázás valószínûsége (1/2)^k-val legyen felülrõl becsülhetõ.