Изворни код странице Problem izomorfizma grafova

'''Problem izomorfizma grafova''' je [[računarski problem]] utvrđivanja da li su dva konačna [[Графови|grafa]] [[Izomorfizam grafova|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|Garey|Johnson|1979}}, i jedan od samo dva problema čija kompleksnost ostaje nerešiva (drugi je [[Rastavljanje na faktore]])<ref>The latest one resolved was [[minimum-weight triangulation]], proved to be NP-complete in 2006. {{citation|first1=Wolfgang|last1=Mulzer|first2=Günter|last2=Rote|title=Minimum-weight triangulation is NP-hard|journal=Journal of the ACM|volume=55|issue=2|doi=10.1145/1346330.1346336|year=2008|arxiv=cs.CG/0601002|pages=1|s2cid=1658062 }}</ref>. Od 2008 godine najbolji algoritam za grafove sa n temena ([[Eugene Luks]], 1983) je složenosti 2<sup>O(√(''n'' log ''n''))</sup>.<ref name="Johnson 2005">{{harvnb|Johnson|2005}}</ref><ref>{{harvnb|Babai|Codenotti|2008}}</ref> 

Poznato je da se problem izomorfizma grafova nalazi na [[niži nivo hijerarhije|nižem nivou hijerarhije]] [[Класа НП|klase NP]], što govori da nije NP-kompletan osim ako na [[lestvica polinomijalnog vremena|lestvici polinomijalnog vremena]] ne dostiže drugi nivo.<ref>[[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</ref>

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.<ref>{{harvnb|McKay|1981}}</ref> 

Ovaj problem je specijalna vrsta [[Проблем изоморфизма графа|problema izomorfizma podgrafa]]<ref>{{harvnb|Ullman|1976}}</ref>, za koji se zna da je [[НП комплетни проблеми|NP-kompletan]]. Poznat je kao specijalan slučaj problema ne-abelove skrivene podgrupe preko simetričnih grupa.<ref>{{cite arXiv|eprint=quant-ph/0501056v3|author1=[[Cris Moore|Cristopher Moore]]|last2=Russell|first2=Alexander|last3=Schulman| first3=Leonard J.|title=The Symmetric Group Defies Strong Fourier Sampling: Part I|class=quant-ph|year=2005}}</ref>


== 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 2<sup>O(√''n'' log<sup>2</sup> ''n'')</sup>,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|Spielman|1996}} (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.<ref>László Babai, [[William Kantor]], Eugene Luks, [http://portal.acm.org/citation.cfm?id=1382437.1382817 Computational complexity and the classification of finite simple groups], Proc. 24th FOCS (1983). стр. 162.–171.</ref> 

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.<ref>P. Foggia, C.Sansone, M. Vento, [http://www.engr.uconn.edu/~vkk06001/GraphIsomorphism/Papers/VF_SD_NAUTY_Ullman_Experiments.pdf A Performance Comparison of Five Algorithms for Graph Isomorphism] {{Wayback|url=http://www.engr.uconn.edu/~vkk06001/GraphIsomorphism/Papers/VF_SD_NAUTY_Ullman_Experiments.pdf |date=20150924000927 }}, Proc. 3rd IAPR-TC15 Workshop Graph-Based Representations in Pattern Recognition. (2001). стр. 188–199.</ref>

== Specijalni slučajevi ==
Lista specijalnih slučajeva problema izomorfizma grafova, koji imaju efikasno rešenje u polinomijalnom vremenu:
* [[Стабло (теорија графова)|Стабла]]<ref>P.J. Kelly, "A congruence theorem for trees" Pacific J. Math., 7 (1957). стр. 961.–968; {{harvnb|Aho|Hopcroft|Ullman|1974}}</ref>
* [[Планарни граф|Planarni grafovi]]<ref>{{harvnb|Hopcroft|Wong|1974}}</ref> (U stvari, izomorfizam planarnih grafova se rešava u logaritamskom vremenu,<ref>{{cite book|doi=10.1109/CCC.2009.16 |chapter=Planar Graph Isomorphism is in Log-Space |title=2009 24th Annual IEEE Conference on Computational Complexity |year=2009 |last1=Datta |first1=Samir |last2=Limaye |first2=Nutan |last3=Nimbhorkar |first3=Prajakta |last4=Thierauf |first4=Thomas |last5=Wagner |first5=Fabian |pages=203–214 |isbn=978-0-7695-3717-7 |url=https://pure.itu.dk/portal/da/publications/f73e611b-6bcc-40e5-8ede-12f8e2b754e1 }}</ref> klasa koja je se nalazi u P)
* [[Težinski graf]]ovi<ref>{{harvnb|Booth|Lueker|1979}}</ref>
* [[Permutacioni grafovi]]<ref>{{harvnb|Colbourn|1981}}</ref>
* [[Delimična k stabla|Delimična k-stabla]]<ref>{{harvnb|Bodlaender|1990}}</ref>
* Grafovi sa ograničenom vrednošću nekih parametara
** Grafovi ograničenog [[rod]]a<ref>{{harvnb|Miller|1980}}; {{harvnb|Filotti|Mayer|1980}}</ref>(Planarni grafovi su grafovi roda 0)
** Grafovi ograničenog [[stepen]]a<ref>{{harvnb|Luks|1982}}</ref>
** k-kontraktibilni grafovi(uopšteni grafovi ograničenog roda i stepena)<ref>[[Gary L. Miller (mathematician)|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.)</ref>
** Izomorfizam obojivih grafova sa ograničenom vrednošću boja (većina čvorova imaće istu boju za fiksiranu vrednost boja k) je klase NC, koja je podklasa klase P.<ref>[[Eugene Luks]], "[[Parallel algorithm]]s for [[permutation group]]s and graph isomorphism", Proc. IEEE Symp. Foundations of Computer Science. (1986). стр. 292–302.</ref>

== 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]].<ref>{{harvnb|Booth|Colbourn|1977}}; {{harvnb|Köbler|Schöning|Torán|1993}}</ref> U stvari ako bi problem izomorfizma grafova bio rešiv u polinomijalnom vremenu onda bi '''GI''' klasa bila jednaka sa '''[[P-kompletan|P]]'''

Kao što je uobičajeno za [[kompleksna klasa|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 <math>X</math> je kompletan za '''GI''', ili je '''GI-kompletan'''

Problem izomorfizma grafova sadržan je u '''NP''' i co-'''[[AM (complexity)|AM]]'''. GI je manje isadržan i/u [[Parity P]], a takođe je deo potencijalno mnogo manje klase [https://web.archive.org/web/20100727044756/http://qwiki.stanford.edu/wiki/Complexity_Zoo:S#spp SPP].<ref>{{harvnb|Köbler|Schöning|Torán|1992}}; {{harvnb|Arvind|Kurur|2006}}</ref> 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 [[ZPP (complexity)|ZPP]]<sup>NP</sup>.<ref>{{harvnb|Arvind|Köbler|2000}}</ref>. 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:<ref name="zkt">{{harvnb|Zemlyachenko|Korneenko|Tyshkevich|1985}}</ref>
* [[direktni grafovi]]i<ref name="zkt"/>
* [[etiketirani grafovi]], pod uslovom da izomorfizam ne treba da pamti sve etikete,<ref name="zkt"/> već samo one koje pripadaju temenima sa istim etiketama
* "polarizovani grafovi" (koji se sastoje od [[Комплетни графови|kompletnih grafova]] K<sub>m</sub> i [[prazni graf|praznih grafova]] i od još nekih grana koje povezuju ta dva grafa; njihov izomorfizam mora da čuva podelu)<ref name="zkt"/>
* 2-[[obojivi graf]]ovi<ref name="zkt"/>
* eksplicitno dati grafovi sa konačnom strukturom<ref name="zkt"/>
* [[multigraf]]ovi<ref name="zkt"/>
* [[hiper graf]]ovi<ref name="zkt"/>
* konačno izgenerisani<ref name="zkt"/>
* [[Markov proces|Markov proces odlučivanja]]<ref>[http://www.cse.iitm.ac.in/~ravi/papers/Shravan-ICML08.pdf "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.</ref>
* [[Комутативна група|komutativna]] 3-nilpotentna(primer: xyz=0 za sve elemente x,y,z) [[Полугрупа|polugrupa]]<ref name="zkt"/>
* [[Контекстно слободна граматика|Kontekstno-slobodna gramatika]]<ref name="zkt"/>
* Nepotpuno balansirani blok dizajn<ref name="zkt"/>

==== 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:<ref name="zkt"/>
* [[povezan graf|povezani grafovi]]<ref name="zkt"/>
* grafovi čiji je [[Дијаметар|dijametar]] jednak 2 a radius 1<ref name="zkt"/>
* [[direktni aciklicni graf|direktni aciklični grafovi]]<ref name="zkt"/>
* [[regularan graf|regularni grafovi]]<ref name="zkt"/>
* [[bipartitivan graf|bipartitivni grafovi]] bez ne-trivijalnih regularnih podgrafova<ref name="zkt"/>
* bipartitivni [[Ојлеров пут|Ojlerovi]] grafovi<ref name="zkt"/>
* bipartitivni regularni grafovi<ref name="zkt"/>
* linijski grafovi<ref name="zkt"/>
* split grafovi<ref name="chung1985cutwidth">{{cite journal|last1=Chung|first1=Fan RK|title=On the cutwidth and the topological bandwidth of a tree|journal=SIAM Journal on Algebraic Discrete Methods|date=1985|volume=6|issue=2|doi=10.1137/0606026|url=http://epubs.siam.org/doi/abs/10.1137/0606026|accessdate = 13. 4. 2015.|pages=268–277}}</ref>
* [[chordal graph]]s<ref name="zkt"/>
* regularni [[samo-komplenetaran graf|samo-komplementarni grafovi]]<ref name="zkt"/>

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.<ref>Colbourn M.J., [[Charles Colbourn|Colbourn Ch.J.]] "Graph isomorphism and self-complementary graphs", ''[[SIGACT News]]'', 1978, vol. 10, no. 1, 25-29.</ref>
* [[Проблем клике|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 ''n''<sup>2</sup>. Ova činjenica je interesantna jer je problem pronalaženja (''n'' &minus; ''ε'')-klike u ''M''-grafu veličine ''n''<sup>2</sup> NP-kompletan za proizvoljno malo ε.<ref>{{harvnb|Kozen|1978}}</ref>
* Problem homeomorfizma 2-kompleksa.<ref>[[John Shawe-Taylor|J. Shawe-Taylor]], T.Pisanski, "Homeomorphism of 2-Complexes is Graph Isomorphism Complete", ''[[SIAM Journal on Computing]],'' 23 (1994) 120 - 132
.</ref>

==== 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.<ref>R. Mathon, "A note on the graph isomorphism counting problem", ''[[Information Processing Letters]],'' 8 (1979). стр. 131—132; {{harvnb|Johnson|2005}}</ref>
* 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<ref>[ftp://ftp.cis.upenn.edu/pub/kannan/jacm.ps.gz Designing Programs that Check their Work]</ref> 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<sup>−100</sup> će odgovoriti pogrešno.

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

== Primene ==

U [[Heminformatika|heminformatici]] i [[matematička hemija|matematičkoj hemiji]], testiranje izomorfizma grafova koristi se za pronalaženje [[hemijskog jednjenja]] u [[hemijskoj bazi]].<ref>Christophe-André Mario Irniger. {{page1|title=Graph Matching: Filtering Databases of Graphs Using Machine Learning|year=2005|isbn=978-1-58603-557-0|pages=}}</ref> 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.<ref>{{cite book|last1=Cook|first1=Diane J.|last2=Holder|first2=Lawrence B.|title=Mining Graph Data|url=https://books.google.com/books?id=bHGy0_H0g8QC&pg=PA119|year=2006|publisher=John Wiley & Sons|isbn=978-0-470-07303-2|pages=120–122}}</ref>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.<ref>{{cite conference |title=An artwork design verification system
|last1=Baird|first1=HS|author2=Cho, YE
| conference =Proceedings of the 12th Design Automation Conference
|pages=414–420|year=1975|publisher =IEEE Press
| url=http://dl.acm.org/citation.cfm?id=809095}}</ref>

== Референце ==
{{reflist|30em}}

== Literatura ==
{{Литература|2}}
* {{citation
| first1 = Alfred V.
| last1 = Aho
| authorlink1 = Alfred Aho
| first2 = John
| last2 = Hopcroft
| authorlink2 = John Hopcroft
| first3 = Jeffrey D.
| last3 = Ullman
| authorlink3 = Jeffrey Ullman
| title = The Design and Analysis of Computer Algorithms
| publisher = Addison-Wesley
| location = Reading, MA
|year=1974}}.
* {{citation
| first1 = Vikraman
| last1 = Arvind
| first2 = Johannes
| last2 = Köbler
| contribution = Graph isomorphism is low for ZPP(NP) and other lowness results.
| title = Proceedings of the 17th Annual [[Symposium on Theoretical Aspects of Computer Science]]
| publisher = Springer-Verlag
| series = [[Lecture Notes in Computer Science]]
| volume = 1770
|isbn=978-3-540-67141-1
|pages=431–442|year=2000
| oclc = 43526888}}.
* {{citation
| first1 = Vikraman
| last1 = Arvind
| first2 = Piyush P.
| last2 = Kurur
| title = Graph isomorphism is in SPP
| journal = [[Information and Computation]]
| volume = 204
| issue = 5
|year=2006
| doi = 10.1016/j.ic.2006.02.002|pages=835–852}}.
* {{Cite book|last1=Babai| first1=László | author1-link=László Babai |last2=Codenotti| first2=Paolo | title=FOCS '08: Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science | publisher=IEEE Computer Society |isbn=978-0-7695-3436-7 |year=2008| chapter=Isomorphism of Hypergraphs of Low Rank in Moderately Exponential Time |pages=667–676}}.
* {{citation
| first1 = László 
| last1 = Babai
| authorlink1 = László Babai
| first2 = D. Yu. 
| last2 = Grigoryev
| authorlink2 = Dima Grigoriev
| first3 = David M. 
| last3 = Mount
| authorlink3 = David M. Mount 
| contribution = Isomorphism of graphs with bounded eigenvalue multiplicity
| title = Proceedings of the 14th Annual ACM [[Symposium on Theory of Computing]]
|year=1982
|pages=310–324| doi = 10.1145/800070.802206
|isbn=978-0-89791-070-5| s2cid = 12837287
}}.
* {{citation
| first = Hans
|last=Bodlaender| authorlink = Hans L. Bodlaender
| title = Polynomial algorithms for graph isomorphism and chromatic index on partial ''k''-trees
| journal = Journal of Algorithms
| volume = 11
|pages=631–643|year=1990
| doi = 10.1016/0196-6774(90)90013-5
| issue = 4}}.
* {{citation
| first1 = Kellogg S.
| last1 = Booth
| first2 = C. J.
|last2=Colbourn| author2-link = Charles Colbourn
| title = Problems polynomially equivalent to graph isomorphism
| publisher = Technical Report CS-77-04, Computer Science Department, University of Waterloo
|year=1977}}.
* {{citation
| first1 = Kellogg S.
| last1 = Booth
| first2 = George S.
| last2 = Lueker
| title = A linear time algorithm for deciding interval graph isomorphism
| journal = [[Journal of the ACM]]
| volume = 26
| issue = 2
|year=1979
| doi = 10.1145/322123.322125|pages=183–195| s2cid = 18859101
| url = https://escholarship.org/uc/item/8ss2q7bp
}}.
* {{citation
| first1 = C.
| last1 = Boucher
| first2 = D.
| last2 = Loker
| title = Graph isomorphism completeness for perfect graphs and subclasses of perfect graphs
| url = http://www.cs.uwaterloo.ca/research/tr/2006/CS-2006-32.pdf
| id = Technical Report CS-2006-32
| publisher = University of Waterloo
|year=2006}}.
* {{citation
| first = C. J.
|last=Colbourn| authorlink = Charles Colbourn
| title = On testing isomorphism of permutation graphs
| journal = Networks
| volume = 11
|pages=13–21|year=1981
| doi = 10.1002/net.3230110103}}.
* {{citation
| first1=I. S. | last1=Filotti
| first2=Jack N. | last2=Mayer
|year=1980
| contribution=A polynomial-time algorithm for determining the isomorphism of graphs of fixed genus
| title=Proceedings of the 12th Annual ACM [[Symposium on Theory of Computing]]
|pages=236–243| doi=10.1145/800141.804671
|isbn=978-0-89791-017-0| s2cid=16345164
}}.
* {{citation
| first1 = Michael R.
| last1 = Garey
| authorlink1 = Michael Garey
| first2 = David S.
| last2 = Johnson
| authorlink2 = David S. Johnson
| title = [[Computers and Intractability: A Guide to the Theory of NP-Completeness]]
| publisher = W. H. Freeman
|year=1979
|isbn=978-0-7167-1045-5
| oclc = 11745039}}.
* {{citation
| first1 = John
| last1 = Hopcroft
| authorlink1 = John Hopcroft
| first2 = J.
| last2 = Wong
| contribution = Linear time algorithm for isomorphism of planar graphs
| title = Proceedings of the Sixth Annual ACM [[Symposium on Theory of Computing]]
|year=1974
| doi = 10.1145/800119.803896|pages=172–184| s2cid = 15561884
}}.
* {{citation
| first1 = Johannes
| last1 = Köbler
| first2 = Uwe
| last2 = Schöning
| first3 = Jacobo
| last3 = Torán
| title = Graph isomorphism is low for PP
| journal = Computational Complexity
| volume = 2
| issue = 4
|year=1992
| doi = 10.1007/BF01200427|pages=301–330| s2cid = 8542603
}}.
* {{citation
| first1 = Johannes
| last1 = Köbler
| first2 = Uwe
| last2 = Schöning
| first3 = Jacobo
| last3 = Torán
| title = The Graph Isomorphism Problem: Its Structural Complexity
| publisher = Birkhäuser
|year=1993
|isbn=978-0-8176-3680-7
| oclc = 246882287}}.
* {{citation
| first = Dexter
|last=Kozen
| title = A clique problem equivalent to graph isomorphism
| journal = [[ACM SIGACT News]]
| volume = 10
| issue = 2
|pages=50–52|year=1978
| doi = 10.1145/990524.990529|s2cid=52835766
}}.
* {{citation
|last=Luks
| first = Eugene M.
| title = Isomorphism of graphs of bounded valence can be tested in polynomial time
| journal = Journal of Computer and System Sciences
| volume = 25
|pages=42–65|year=1982
| doi = 10.1016/0022-0000(82)90009-5}}.
* {{citation
| first1 = Brendan D.
| last1 = McKay
| authorlink = Brendan McKay
| title = Practical graph isomorphism
| id = 10th. Manitoba Conference on Numerical Mathematics and Computing (Winnipeg, 1980)
| journal = Congressus Numerantium
| volume = 30
|year=1981
| url = http://cs.anu.edu.au/~bdm/nauty/PGI/|pages=45–87}}.
* {{citation
| first1 = Gary
| last1 = Miller
| authorlink = Gary L. Miller (mathematician)
| contribution = Isomorphism testing for graphs of bounded genus
| title = Proceedings of the 12th Annual ACM [[Symposium on Theory of Computing]]
|year=1980
|pages=225–235| doi = 10.1145/800141.804670
|isbn=978-0-89791-017-0| s2cid = 13647304
}}.
* {{Citation
| last1=Schmidt
| first1=Douglas C.
| last2=Druffel
| first2=Larry E.
| title=A Fast Backtracking Algorithm to Test Directed Graphs for Isomorphism Using Distance Matrices
| publisher=ACM
|year=1976
| journal=J. ACM
| issn=0004-5411
| volume=23
| issue=3
| doi=10.1145/321958.321963|pages=433–445| s2cid=6163956
}}.
* {{Cite book|last1=Spielman| first1=Daniel A. | author1-link=Daniel Spielman | title=STOC '96: Proceedings of the twenty-eighth annual ACM symposium on Theory of computing |url = https://archive.org/details/proceedingsoftwe0000unse_i5x6  | publisher=ACM |isbn=978-0-89791-785-8 |year=1996| chapter=Faster isomorphism testing of strongly regular graphs |pages=[https://archive.org/details/proceedingsoftwe0000unse_i5x6/page/576 576]–584}}.
* {{citation
| first1 = Julian R.
| last1 = Ullman
| title = An algorithm for subgraph isomorphism
| journal = Journal of the ACM
| volume = 23
|pages=31–42|year=1976
| doi = 10.1145/321921.321925| s2cid = 17268751
}}.<br />
=== Ankete i monografije ===
* {{citation
|last1=Read| first1 = Ronald C.
|last2=Corneil| first2 = Derek G. | author2-link = Derek Corneil
| issue = 4
| journal = Journal of Graph Theory
| mr = 0485586
|pages=339–363| title = The graph isomorphism disease
| volume = 1
|year=1977| doi=10.1002/jgt.3190010410| s2cid = 26589776
}}..
* Gati, G. "Further annotated bibliography on the isomorphism disease." – ''Journal of Graph Theory'' 1979, 3, 95-109.
* {{Citation
|last1=Zemlyachenko| first1 = V. N.
|last2=Korneenko| first2 = N. M.
|last3=Tyshkevich| first3 = R. I.
|authorlink3=Regina Tyshkevich
| title = Graph isomorphism problem
| journal = Journal of Mathematical Sciences
| volume = 29
| issue = 4
|pages=1426–1481| doi = 10.1007/BF02104746
|year=1985| s2cid = 121818465
}}. (Translated from ''Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR'' (Records of Seminars of the [[Leningrad Department of Steklov Institute of Mathematics of the USSR Academy of Sciences]]), Vol. 118. (1982). стр. 83–158.)
* {{Citation
 |first       = V.
 |last        = Arvind
 |author2     = Jacobo Torán
 |title       = Isomorphism Testing: Perspectives and Open Problems
 |url         = http://theorie.informatik.uni-ulm.de/Personen/toran/beatcs/column86.pdf
 |journal     = Bulletin of the [[European Association for Theoretical Computer Science]]
 |volume      = 
 |issue       = 86
 |pages       = 66–84
 |doi         = 
 |year        = 2005
 |accessdate  = 26. 05. 2015
 |archiveurl  = https://web.archive.org/web/20110727130019/http://theorie.informatik.uni-ulm.de/Personen/toran/beatcs/column86.pdf
 |archivedate = 27. 07. 2011
 |url-status=dead
 }}. (A brief survey of open questions related to the isomorphism problem for graphs, rings and groups.)
* {{Citation
| first1 = Johannes
|last1=Köbler
| authorlink= Johannes Köbler
|last2=Schöning|first2=Uwe|author3= Jacobo Torán 
| title = Graph Isomorphism Problem: The Structural Complexity
| publisher = [[:de:Birkhäuser Verlag|Birkhäuser Verlag]]
|isbn=978-0-8176-3680-7
|year=1993
| oclc = 246882287}}. (''From the book cover'': The books focuses on the issue of the computational complexity of the problem and presents several recent results that provide a better understanding of the relative position of the problem in the class NP as well as in other complexity classes.)
* {{citation
| first = David S.
|last=Johnson
| authorlink = David S. Johnson
| title = The NP-Completeness Column 
| journal = [[ACM Transactions on Algorithms]]
| volume = 1
| issue = 1
|pages=160–176| doi = 10.1145/1077464.1077476
|year=2005|s2cid=12604799
}}. (This 24th edition of the Column discusses the state of the art for the open problems from the book ''[[Computers and Intractability]]'' and previous columns, in particular, for Graph Isomorphism.)
* {{Citation
 |first       = Jacobo
 |last        = Torán
 |author2     = Fabian Wagner
 |title       = The Complexity of Planar Graph Isomorphism
 |url         = http://theorie.informatik.uni-ulm.de/Personen/toran/beatcs/column97.pdf
 |journal     = Bulletin of the [[European Association for Theoretical Computer Science]]
 |volume      = 
 |issue       = 97
 |pages       = 
 |doi         = 
 |year        = 2009
 |accessdate  = 26. 05. 2015
 |archiveurl  = https://web.archive.org/web/20100920154742/http://theorie.informatik.uni-ulm.de/Personen/toran/beatcs/column97.pdf
 |archivedate = 20. 09. 2010
 |url-status=dead
 }}.

=== Softver ===
* [http://www.cs.sunysb.edu/~algorith/files/graph-isomorphism.shtml Graph Isomorphism], review of implementations, [http://www.cs.sunysb.edu/~algorith The Stony Brook Algorithm Repository].
{{Литература крај}}

{{normativna kontrola}}

[[Категорија:Рачунарски проблеми у теорији графова]]
[[Категорија:Нерешени проблеми у рачунарству]]