Problem izomorfizma grafova

Извор: testwiki
Датум измене: 13. април 2024. у 10:15; аутор: imported>MilicevicBot (Бот: Special:Diff/27547949)
(разл) ← Старија измена | Тренутна верзија (разл) | Новија измена → (разл)
Пређи на навигацију Пређи на претрагу

Problem izomorfizma grafova je računarski problem utvrđivanja da li su dva konačna grafa izomorfna.

Pored praktičnog značaja, problem izomorfizma grafova je veoma zanimljiv u računarskoj teoriji kompleksnosti kao jedan od retkih problema koji pripadaju NP, za koji se ne zna da li je rešiv u polinomijalnom vremenu niti da li je NP-kompletan: jedan je od 12 problema koji se nalaze na listi Шаблон:Harvnb, i jedan od samo dva problema čija kompleksnost ostaje nerešiva (drugi je Rastavljanje na faktore)[1]. Od 2008 godine najbolji algoritam za grafove sa n temena (Eugene Luks, 1983) je složenosti 2O(√(n log n)).[2][3]

Poznato je da se problem izomorfizma grafova nalazi na nižem nivou hijerarhije klase NP, što govori da nije NP-kompletan osim ako na lestvici polinomijalnog vremena ne dostiže drugi nivo.[4]

Istovremeno, izomorfizam za neke specijalne grafove može biti rešen u polinomijalnom vremenu, a u praksi izomorfizam grafova se obično efikasno rešava.[5]

Ovaj problem je specijalna vrsta problema izomorfizma podgrafa[6], za koji se zna da je NP-kompletan. Poznat je kao specijalan slučaj problema ne-abelove skrivene podgrupe preko simetričnih grupa.[7]


Istorija

Sadašnji najbolji algoritam je algoritam koji je osmislio Eugene Luks (1983) i baziran je na ranijim radovima Luksa (1981), Babaija i Luksa (1982) kombinovan sa podfaktorijalnim algoritmom Zemljašenka. Algoritam je zasnovan na klasifikaciji konačnih prostih grupa. Bez ove klasifikacije CFSG, dobijena je nesto slabija granica 2O(√n log2 n),prvo za jake regularne grafove Lazlo Bablai , (1980), a zatim su je Babai i Luks (1982) proširili na opšte grafove. Poboljšanje eksponenta √n je glavni otvoreni problem; za jake regularne grafove to je rešio Шаблон:Harvnb (1996). Za hipergrafove ograničenog ranga,gde subeksponencijalna gornja granica odgovara slučaju grafova, rešenje/odgovor su nedavno našli Babai i Cadenotti.

Problem izomorfizma grafova je računski ekvivalentan problemu izračunavanja automorfizma grupe grafa, i slabiji je od problema izomorfizma permutacionih grupa, i od problema preseka permutacionih grupa. Za poslednja dva problema Babai, Kantor i Luks (1983) su dobili granice složenosti slične onima za izomorfizam grafova.[8]

Postoji nekoliko konkurentnih praktičnih algoritama za izomorfizme grafova,koje su postavili McKay (1981), Schmidt & Druffel (1976), Ullman (1976), i tako dalje. Iako deluje da se izvršava dobro na slučajnim grafovima,glavni nedostatak ovih algoritama je njihova eksponencijalna vremenska složenost u najgorem slučaju.[9]

Specijalni slučajevi

Lista specijalnih slučajeva problema izomorfizma grafova, koji imaju efikasno rešenje u polinomijalnom vremenu:

Složena klasa GI

Pošto se za problem izomorfizma grafova ne zna da li je NP-kompletan, niti da li je obradiv, istraživači su nastojali da steknu bolji uvid u ovaj problem definisanjem nove klase GI, kroz niz problema koji su rešivi u polinomijalnom vremenu.[20] U stvari ako bi problem izomorfizma grafova bio rešiv u polinomijalnom vremenu onda bi GI klasa bila jednaka sa P

Kao što je uobičajeno za kompleksne klase koje se rešavaju u polinomijalnom vremenu, problem se naziva GI-težak ako postoji Tjuringova redukcija bilo kog problema GI klase do tog problema u polinomijalnom vremenu, odnosno polinomijalno-vremensko rešenje nekog GI-teškog problema bi se dobilo uz pomoć problema izomorfizma grafova koji se takođe rešava u polinomijalnom vremenu (ovo važi za sve probleme GI klase). Problem X je kompletan za GI, ili je GI-kompletan

Problem izomorfizma grafova sadržan je u NP i co-AM. GI je manje isadržan i/u Parity P, a takođe je deo potencijalno mnogo manje klase SPP.[21] To da leži u Parity P znači da problem izomorfizma grafova nije ništa teži od određivanja da li je polinomijalno-vreme uopšte moguće determinisati. Tjuringova mašina ima paran ili neparan broj prihvatanja putanja. GI je takođe sadržan i nizak za ZPPNP.[22]. Ovo suštinski znači da efikasan Las Vegas algoritam sa pristupom NP oraklu može da reši izomofizme grafova tako lako, da čak ne dobija nikakvu moć sticanjem mogućnosti da to uradi u konstantnom vremenu.

GI-kompletni i GI-teški problemi

Problem izomorfizma nekih drugih objekata

Postoji veliki broj klasa matematičkih objekata za koje je problem izomorfizma grafova GI-kompletan. Neki od njih su grafovi sa nekim dodatnim svojstvima ili ograničenjima:[23]

GI-kompletne klase grafova

Klasa grafova se naziva GI-kompletna ako je problem izomorfizma grafova iz ove grupe GI-kompletan. Sledeće klase su GI-kompletne:[23]

Ova lista nije upotpunjena! Dosta klasa digrafova takodje su GI-kompletne.

Ostali GI-kompletni problemi

Postoje i neki drugi netrivijalni GI-kompletni problemi pored problema izomorfizma grafova:

  • Pronalaženje samo-komplementarnih grafova ili digrafova.[26]
  • Problem klike za takozvanu klasu M-grafova. Pokazalo se da je pronalaženje izomorfizma za n-najviše tačke grafova ekvivalentno pronalaženju n-klika u M-grafu veličine n2. Ova činjenica je interesantna jer je problem pronalaženja (n − ε)-klike u M-grafu veličine n2 NP-kompletan za proizvoljno malo ε.[27]
  • Problem homeomorfizma 2-kompleksa.[28]

GI-teški problemi

  • Problem brojanja izomorfizma između dva grafa je polinomijalnog vremena ekvivalentan problemu koji govori da li neki od ta dva grafa uopšte postoji.[29]
  • Problem odlučivanja da li dva konveksna politopa dobijena ili V-opisom ili H-opisom su " projectively or affinely izomorfni", što znači da postoji projective or affine mapa između prostora koji sadrže dva politopa (ne nužno istih dimenzija) koje uključuje bijaiciju između dva politopa.

Provera programa

Blum and Kannan[30] su predstavili program koji proverava izomorfizme grafova. Uzmimo da se za P tvrdi da je polinomijalno-vremenska procedura koja proverava da li su dva grafa izomorfna, ali nije pouzdan. Da bi se proverilo da li su G i H izomorfni:

  • Pitati P da li su G i H izomorfni.
    • Ako je odgovor "da":
      • Pokušati konstruisanje izomorfizma koristeći P kao subrutinu. Označiti teme u G i v u H, I modifikovati grafove kako bi postali različiti (sa malom lokalnom promenom). Pitati P da li su modifikovani grafovi izomorfni. Ako ne, pomeriti v na drugo teme/vertex. Nastaviti sa pretragom.
      • Izomorfizam ili će biti pronađen (i moći će da bude verifikovan) ili će P protivrečiti sam sebi.
    • Ako je odgovor "ne":
      • Izvesti sledeće 100 puta. Izabrati nasumično G ili H, i nasumično permutovati njihova temena(vertices). Pitati P da li je graf izomorfanza G i H. (kao u AM protokolu za neizomorfizam grafova).
      • Ako bilo koji od od testova budu negativni, oceniti P kao neispravan(invalid) program. U suprotnomo dgovor je "ne".

Ova procedura je polinomijalno-vremenska,i daje ispravan odgovor ako je P tačan program za izomorfizme grafova. Ako P nije odgovarajući program ali ispravno odgovori na G i H,kontrola će ili dati tačan odgovor, ili će detektovati nevažeće ponašanje P.Ako P nije odgovarajući program, a netačnoodgovorinaG i H,kontrolaćesavelikomverovatnoćom,detektovatineispravnoponašanjekod P, a sa verovatnoćom 2−100 će odgovoriti pogrešno.

Napomena,P je korišćen samo kao 'blackbox'.

Primene

U heminformatici i matematičkoj hemiji, testiranje izomorfizma grafova koristi se za pronalaženje hemijskog jednjenja u hemijskoj bazi.[31] Takođe, u organskoj matematičkoj hemiji testiranje izomorfizma grafova korisno je za generazicione molekularne grafove i za kompijutersku sintezu.

Pretraga hemijske baze je primer analize podataka pomoću grafova u kojem se pristup kanonizacije grafova često koristi.[32]Jedan broj identifikatora za hemijske supstance kao što su SMILES i InChI, koji su napravljeni da obezbede standardizovani čitljiv način za kodiranje molekularnih informacija kao i da omogući pretragu takvih informacija u bazama podataka na internetu,koriste kanonizacijski korak u svom računanju, što je u suštini kanonizacija grafa koji predstavlja molekul. U automatizaciji elektronskog dizajna, izomorfizam grafova je osnova Layout Versus Schematic (LVS) circuit design step, koji verifikuje da li su električno kolo predstavljena prikladnom shemom i shema integrisanog kola iste.[33]

Референце

Шаблон:Reflist

Literatura

Шаблон:Литература

Ankete i monografije

Softver

Шаблон:Литература крај

Шаблон:Normativna kontrola

  1. ↑ The latest one resolved was minimum-weight triangulation, proved to be NP-complete in 2006. Шаблон:Citation
  2. ↑ Шаблон:Harvnb
  3. ↑ Шаблон:Harvnb
  4. ↑ Uwe Schöning, "Graph isomorphism is in the low hierarchy", Proceedings of the 4th Annual Symposium on Theoretical Aspects of Computer Science, 1987, 114-124; also: Journal of Computer and System Sciences, vol. 37 (1988), 312-323
  5. ↑ Шаблон:Harvnb
  6. ↑ Шаблон:Harvnb
  7. ↑ Шаблон:Cite arXiv
  8. ↑ László Babai, William Kantor, Eugene Luks, Computational complexity and the classification of finite simple groups, Proc. 24th FOCS (1983). стр. 162.–171.
  9. ↑ P. Foggia, C.Sansone, M. Vento, A Performance Comparison of Five Algorithms for Graph Isomorphism Шаблон:Wayback, Proc. 3rd IAPR-TC15 Workshop Graph-Based Representations in Pattern Recognition. (2001). стр. 188–199.
  10. ↑ P.J. Kelly, "A congruence theorem for trees" Pacific J. Math., 7 (1957). стр. 961.–968; Шаблон:Harvnb
  11. ↑ Шаблон:Harvnb
  12. ↑ Шаблон:Cite book
  13. ↑ Шаблон:Harvnb
  14. ↑ Шаблон:Harvnb
  15. ↑ Шаблон:Harvnb
  16. ↑ Шаблон:Harvnb; Шаблон:Harvnb
  17. ↑ Шаблон:Harvnb
  18. ↑ Gary L. Miller: Isomorphism Testing and Canonical Forms for k-Contractable Graphs (A Generalization of Bounded Valence and Bounded Genus). Proc. Int. Conf. on Foundations of Computer Theory, (1983). стр. 310-327 (Lecture Notes in Computer Science, vol. 158, full paper in: Information and Control, 56(1-2):1–20, 1983.)
  19. ↑ Eugene Luks, "Parallel algorithms for permutation groups and graph isomorphism", Proc. IEEE Symp. Foundations of Computer Science. (1986). стр. 292–302.
  20. ↑ Шаблон:Harvnb; Шаблон:Harvnb
  21. ↑ Шаблон:Harvnb; Шаблон:Harvnb
  22. ↑ Шаблон:Harvnb
  23. ↑ 23,00 23,01 23,02 23,03 23,04 23,05 23,06 23,07 23,08 23,09 23,10 23,11 23,12 23,13 23,14 23,15 23,16 23,17 23,18 23,19 23,20 23,21 23,22 Шаблон:Harvnb
  24. ↑ "On the hardness of finding symmetries in Markov decision processes", by SM Narayanamurthy, B Ravindran, Proceedings of the Twenty Fifth International Conference on Machine Learning (ICML 2008). стр. 688-696.
  25. ↑ Шаблон:Cite journal
  26. ↑ Colbourn M.J., Colbourn Ch.J. "Graph isomorphism and self-complementary graphs", SIGACT News, 1978, vol. 10, no. 1, 25-29.
  27. ↑ Шаблон:Harvnb
  28. ↑ J. Shawe-Taylor, T.Pisanski, "Homeomorphism of 2-Complexes is Graph Isomorphism Complete", SIAM Journal on Computing, 23 (1994) 120 - 132 .
  29. ↑ R. Mathon, "A note on the graph isomorphism counting problem", Information Processing Letters, 8 (1979). стр. 131—132; Шаблон:Harvnb
  30. ↑ Designing Programs that Check their Work
  31. ↑ Christophe-André Mario Irniger. Шаблон:Page1
  32. ↑ Шаблон:Cite book
  33. ↑ Шаблон:Cite conference
Преузето из „https://sr.wiki.beta.math.wmflabs.org/w/index.php?title=Problem_izomorfizma_grafova&oldid=6484”