FKT algoritam

С Википедије, слободне енциклопедије

FKT algoritam, nazvan po Fišeru, Kastelinu i Temperliju, računa broj savršenih uparivanja planarnog grafa u polinomijalnom vremenu. Ovaj isti zadatak je #P-kompletan i za ostale grafove. Računanjem broja uređenjih parova, čak i za planarne grafove takođe je #P-kompletno. Ključna ideja je da konvertuje problem u Pfafijan računanje koc-simetrične matrice izvedene od planarnog ugrađivanja grafa. Pfafian matrica je onda kompjuterizovana efikasno standardnim algoritmima determinante.

Istorija[уреди | уреди извор]

Problem brojanja planarnih savršenih uparivanja ima svoje korene u statici i hemiji, gde je originalno pitanje: Ako se diatomiski molekuli apsorbuju na površini, formirajući jedan sloj, na koliko načina se oni mogu organizovati? [1] Funkcija particionisanja je važan kvantitet koji kodira statističke osobine sistema u ravnotezi i može se koristiti kao odgovor na prethodno pitanje. Međutim izračunavanje funkcije particije direktnom primenom njenom definicije nije praktičano. Tako da bi se precizno rešio fizički sistem, neophodno je pronaći alternativnu formu funkcije particionisanja za taj pojedinačni fizički sistem koja je dovoljno jednostavna za precizno izračunavanje.[2] Ranih 1960-tih, definicija tačno rešivog nije bila rigorozna.[3] Informatika je obezbedila rigoroznu definiciju uvođenjem polinomijalnog vremena, koje datira od 1965. Slično tome, notacija ne baš tačno rešivog treba da odgovara #P-teskoci, koja je definisana 1979.

Druga vrsta fizičkog sistema za razmatranje je sastavljena od dimera, što je polimer sa dva atoma. Dimerni model računa broj dimerski pokrića grafa.[4] Drugi fizički sistem za razmatranje je vezivanje H2O molekula u obliku leda. Ovo može biti modelovano kao usmereni, 3-regularni graf kod koga orijentacije ivica na svakom čvoru ne mogu biti iste. Koliko ivica orijentacije ima ovaj model?

Motivisani fizičkim sistemima koji uključuju dimere, 1961, Kastelin[5] i Temperli-Fišer[6] nezavisno nalaze broj dominskog popločavanja za m-sa-n pravougaonik. Ovo je ekvivalentno broju savršenih uparivanja za m-sa-n rešetkasti graf. 1967. Kastelin je generalizovao ovaj rezultat za sve planarne grafove.[7][8]

Algoritam[уреди | уреди извор]

Objašnjenje[уреди | уреди извор]

Glavni uvid je da svaki ne-nula rok u Pfaffianu od matrice susedstva grafa G odgovara savrsenom uparivanju. Dakle, ako neko moze da pronadje polozaj G da uskladi sve znake termina u Pfaffian (bez obzira na + ili -), onda apsolutna vrednost Pfaffiana je samo broj savrsenih uparivanja u G. FKT algoritam radi takav zadatak za planaran graf G.

Neka G=(V,E) bude neusmeren graf sa matricom susedstva A. Definisi PM(n) da bude skup particija od n elemenata u parove, zatim broj savrsenih uparivanja u G je

U tesnoj vezi sa ovim je Pfaffian za n x n matricu A

Gde je sgn(M) znak permutacije od M. Pfaffian orijentacija od G je usmeren graf H sa (1,-1,0) matricom susedstva B takvom da je pf(b)= PerfMatch(G)[9]. 1967. Kasteleyn je dokazao da su planarni grafovi efikasno podlozni racunanju pfafian orijentacije. Konkretno, za planaran graf G, neka H bude usmerena verzija G gde je neparan broj ivica orijentisano u smeru kazaljke na satu za svako lice u planarnom ugradjivanju G. Onda je H pfafian orijentacija od G.

Na kraju, za bilo koju koc-simetričnu matricu A,

gde det(A) je determinanta od A. Ovaj rezultat je zbog Cayleya.[10] Posto su determinante efektivno podlozne racunanju, onda je i PerfMatch(G).

Opis visokog nivoa[уреди | уреди извор]

An example showing how the FKT algorithm finds a Pfaffian orientation.
  1. Izracuna planarnu ugradnju od G
  2. Izracuna spanning stablo T1 ulaznog grafa G
  3. Daje proizvoljnu orijentaciju svakoj ivici u G koja je takodje u T1.
  4. Koristi planarna ugradjivanja da stvori (neusmeren)graf T2 sa istim skupom cvorova kao dvojni graf od G
  5. Napravi ivicu u T2 izmedju dva cvora ako su odgovarajuca
  6. Za svaki list v u T1(to nije i koren)
    1. Neka je e usamljena ivica od G u lice odgovara v koji jos nema orijentaciju
    2. Daj e orijentaciju takvu da je broj ivica orijentisanih u smeru kazaljke na satu neparan.
    3. Ukloni v od T2.
  7. Vrati apsolutnu vrednost Pfaffian od (1,-1,0) matrice susedstva G, koja je apsolutna vrednost kvadratnog korena determinante.

Generalizacija[уреди | уреди извор]

Zbir opterecenih savrsenih uparivanja se moze izracunati pomocu Tutte matrice za matricu susedstva u poslednjem koraku.

Kuratovski teorema navodi da konačni graf je planaran ako i samo ako ne sadrzi podgraf homeomorfan K5 (potpun graf od pet cvorova) ili K3,3 (potpun bipartidan graf na dve particije velicine tri). Vijay Vazirani generalizovao je FKT algoritam za grafove koji ne sadrze homeomorfan podgraf za K3,3.[11] Od prebrojavanja savrsenih uparivanja u opstem grafu je #P-kompletan (#P-complete), neka ogranicenja ulaznog grafa su potrebna, osim ako FP , funkcijska verzija P , jednaka je #P. Prebrojavanje parova, koja su poznata као Hosoja indeks (Hosoya index), su takodje #P-kompletna cak i za planarne grafove.

Aplikacije[уреди | уреди извор]

FKT algoritam je video siroku primenu u holografskim algoritmima(holographic algorithm) za planarne grafove preko uparivanja(matchgates).[3] Na primer, razmotrite planaranu verziju ledenog modela gore navedenog, koja ima tehnicko ime #PL-3-NAE-SAT (gde NAE znaci "" nisu svi isti""). Valiant je nasao polinomijalno vremenski algoritam za ovaj problem, koji koristi uparivanja.[12]

Reference[уреди | уреди извор]

  1. ^ Hayes, Brian (2008), „Accidental Algorithms”, American Scientist 
  2. ^ Baxter, R. J. (2008) [1982]. Exactly Solved Models in Statistical Mechanics (Third изд.). Dover Publications. стр. 11. ISBN 978-0-486-46271-4. Архивирано из оригинала 20. 03. 2012. г. Приступљено 31. 05. 2013. 
  3. ^ а б Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji (2010). Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP. Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on. Las Vegas, NV, USA: IEEE. arXiv:1008.0683 Слободан приступ. 
  4. ^ Kenyon, Richard; Okounkov, Andrei (2005). „What is a Dimer?” (PDF). AMS. 52 (3): 342—343. 
  5. ^ Kasteleyn, P. W. (1961), „The statistics of dimers on a lattice. I. The number of dimer arrangements on a quadratic lattice”, Physica, 27 (12): 1209—1225, doi:10.1016/0031-8914(61)90063-5 
  6. ^ Temperley, H. N. V.; Fisher, Michael E. (1961). „Dimer problem in statistical mechanics-an exact result”. Philosophical Magazine. 6 (68): 1061—1063. doi:10.1080/14786436108243366. 
  7. ^ Kasteleyn, P. W. (1963). „Dimer Statistics and Phase Transitions”. Journal of Mathematical Physics. 4 (2): 287—293. doi:10.1063/1.1703953. 
  8. ^ Kasteleyn, P. W. (1967), „Graph theory and crystal physics”, Ур.: Harary, F., Graph Theory and Theoretical Physics, New York: Academic Press, стр. 43—110 
  9. ^ Thomas, Robin (2006). A survey of Pfaffian orientations of graphs (PDF). International Congress of Mathematicians. III. Zurich: European Mathematical Society. стр. 963—984. 
  10. ^ Cayley, Arthur (1847). „Sur les determinants gauches” [On skew determinants]. Crelle's Journal. 38: 93—96. 
  11. ^ Vazirani, Vijay V. (1988), „NC algorithms for computing the number of perfect matchings in K3,3-free graphs and related problems”, Proc. 1st Scandinavian Workshop on Algorithm Theory (SWAT '88), Lecture Notes in Computer Science, 318, Springer-Verlag, стр. 233—242, doi:10.1007/3-540-19487-8_27 
  12. ^ Valiant, Leslie G. (2004). „Holographic Algorithms (Extended Abstract)”. Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science. FOCS'04. Rome, Italy: IEEE Computer Society. стр. 306—315. ISBN 978-0-7695-2228-9. doi:10.1109/FOCS.2004.34. Архивирано из оригинала|archive-url= захтева |url= (помоћ) 13. 03. 2012. г. 

Literatura[уреди | уреди извор]

Spoljašnje veze[уреди | уреди извор]

  • Presentation by Ashley Montanaro about the FKT algorithm
  • More history, information, and examples can be found in chapter 2 and section 5.3.2 of Dmitry Kamenetsky's PhD thesis
Преузето из „https://sr.wikipedia.org/w/index.php?title=FKT_algoritam&oldid=26741904”