Ugrás a tartalomhoz

Diszkrét matematika

dr. Hajnal Péter (2013)

Szegedi Tudományegyetem

Véletlen módszer

Véletlen módszer

A (3) problémát vizsgáljuk, azaz csak tesztelni szeretnénk,hogy gráfunkban van-e teljes párosítás. Módszerünk általános gráfok vizsgálatát is megengedi, mégis csak egy egyszerűb esetet vizsgálunk: Adott G egyszerű, páros gráf, |A|=|F|=n. Van-e G-ben teljes párosítás?

Az egyszerűség és a két színosztály azonos mérete természetes módon, az általánosság megszorítása nélkül feltehető.

Definíció. Legyen G egy A˙F színosztályokkal rendelkező egyszerű páros gráf. G páros szomszédsági mátrixa BG, az a mátrix, amely sorai A-val, oszlopai F-fel vannak azonosítva, továbbá egy aA-nak megfelelő sor és egy fF-nek megfelelő oszlop találkozásában 1 szerepel, ha szomszédosak, 0 különben.

Megjegyzés. G (teljes) AG szomszédsági mátrixában a sorok és oszlopok is a V(G) csúcshalmazzal azonosított. Ha a sorok/oszlopok felsorolásában A elemei megelőzik F elemeit, akkor az A-A, illetve F-F élek hiánya miatt a mátrix bal felső és jobb alsó sarkában 0-k egy nagy blokkja található, míg a jobb felső sarokban BG szerepel, a bal alsó sarokban pedig BGT, a páros szomszédsági mátrix transzponáltja.

Azaz a páros szomszédsági mátrix csak a szokásos szomszédsági mátrix tömörítése.

A mátrix leírja a G páros gráfot. A G páros gráfra vonatkozó fogalmak átfogalmazhatóak a mátrixok nyelvére. Az alábbiakban egy ''szótárat'' ismertetünk.

pozíciói A × F 1-esei E ( G ) | A | = | F | négyzetes mátrix M párosítás sorban és oszlopban max egy db 1-es van M teljes párosítás sorban és oszlopban pontosan egy db 1-es van a megfelelő 1-esek egy kifejtési tag tényezői

A fentiek alapján, ha G-ben van teljes párosítás, akkor detBG kifejtésében létezik egy nem 0 tag. Ezt az egyszerű észrevételt a következő állítás foglalja össze.

10.3.1. Következmény. det B G 0 esetén detBG kifejtésében létezik nem 0 tag, ami ekvivalens azzal, hogy létezik teljes párosítás G-ben.

A fordított irány nem igaz. Ehhez vegyünk egy olyan páros gráfot, amelyben két alsó pontnak ugyanaz a szomsédsága és ezzel együtt van teljes párosítás a gráfban (például egy teljes páros gráf, Kn,n megfelel). Ekkor BG-ben lesz két azonos sor, azaz a determináns értéke 0.

Definíció. Az Mpermanense

Észrevétel.

    (i) perBG0 esetén G-ben létezik teljes párosítás.

    (ii) perBG a teljes párosítások száma G-ben.

Sajnos ez az észrevétel nem segít algoritmikus problémánk megoldásában: perBG kiszámítása reménytelen, úgynevezett #P-nehéz.

Definíció. X G R [ x e : e E ( G ) ] n × n : eE(G) esetén BGe-nek megfelelő 1-esét xe-vel helyettesítjük.

10.3.2. Tétel. d e t ( X G ) nem az azonosan 0 polinom akkor és csak akkor, ha létezik G-ben teljes párosítás.

Észrevétel.

    (i) G-beli teljes párosítások száma megegyezik a det(XG)-ben szereplő különböző monomok számával.

    (ii) det(XG)-nek túl hosszú lehet a standard leírása, de hatékonyan kiértékelhető, ha xe=αe, ahol αeR, (lásd numerikus analízis vagy algebra előadás).

Az előző észrevételen alapul az alábbi algoritmus.

Véletlen algoritmus.

Véletlen helyettesítés: Minden e élre vegyünk egy re{1,...,N}-t,

ahol re uniform eloszlású valószínűségi változó.

DET számolás: Számítsuk ki det(XG)|xe=re-t.

Kiértékelés: Ha ez nem 0, akkor az output legyen ''Létezik teljes párosítás''. Ha ez 0, akkor az output legyen ''Valószínűleg nem létezik teljes párosítás''.

Az algoritmus analízise

Az algoritmusunk tévedhet. De hogyan?

      ''Létezik teljes párosítás'': biztosan jó a válasz.

      ''Valószínűleg nem létezik teljes párosítás'':

         ha det(XG) az azonosan 0 polinom, akkor jó a válasz;

         ha det(XG) nem az azonosan 0 polinom, akkor szerencsétlen re-ket választottunk, épp det(XG) gyökeit: az algoritmus téved.

Célunk, hogy a hibázás lehetőségét minél kisebbé tegyük. Érezhető, hogy minél nagyobb az N, annál kisebb a hibázás valószínűsége. Az alábbi lemmára van szükségünk, hogy ezt az érzésünket matematikailag is pontossá tegyük.

10.3.1.1. Tétel (Schwartz-lemma). Legyen p(x1,...,xk)R[x1,...,xk] egy nem azonos 0 polinom, és legyenek ri{1,...,N}-k uniform eloszlású független valószínűségi változók, (1ik). Ekkor

Bizonyítás. k -ra vonatkozó teljes inducióval bizonyítunk.

k = 1 esetén pR[x]. Ekkor |{rR:p(r)=0}|degp, így annak a valószínűsége, hogy egy adott r{1,...,N} épp gyöke a p-nek felülről becsülhető degpN-nel (r uniform eloszlású).

Tegyük fel, hogy k-1 határozatlan esetén teljesül az állítás. Írjuk fel a k-változós p polinomot a következő alakban:

ahol pα(x1,...,xk-1) egy nem azonosan 0 polinom. A felírásból következik, hogy degpdegpα+α.

Legyen Rk={(r1,...,rk):p(r1,...,rk)=0}, Rk-1={(r1,...,rk):pα(r1,...,rk-1)=0} és Q={(r1,...,rk):(r1,...,rk)Rk-1,de(r1,...,rk)Rk}. Könnyen látható, hogy RkRk-1Q. Az indukciós feltevésből Rk-1 valószínűsége becsülhető. Az egy határozatlanú polinomok esete alapján Q valószínúsége becsülhető. Összegezve kapjuk, hogy

Ezzel beláttuk a tétel állítását.

A lemmát alkalmazva a véletlen algoritmusra (p=det(XG), degp=n(=|A|=|F|)) kapjuk, hogy az N=2n választással élve a hibázás valószínűsége legfeljebb 12. A hibázás valószínűsége tovább csökkenthető N értékének növelésével, vagy a fenti paraméterválasztáson alapuló változat többszöri, független ismétlésével.