Izomorfizem grafov

Izomorfízem gráfov G in H je v teoriji grafov takšna bijektivna preslikava med množico točk G in H:

$f\colon V(G)\to V(H)\!\,,$

da sta poljubni dve točki u in v grafa G sosednji v G, če in samo če sta ƒ(u) in ƒ(v) sosednji v H. Ta vrsta bijektivne preslikave se običajno opiše kot »bijektivna preslikava, ki ohranja točke« v soglasju s splošno predstavo o izomorfizmu kot bijektivni preslikavi, ki ohranja strukturo.

Če med dvema grafoma G in H obstaja izomorfizem, sta grafa med seboj izomorfna, kar se označi kot $G\simeq H$. V primeru, če je bijektivna preslikava preslikava grafa v samega sebe, torej kadar sta G in H kar en in isti graf, se ta bijektivna preslikava imenuje avtomorfizem grafa G.

Izomorfizem grafov je ekvivalenčna relacija na grafih in kot taka razdelili razred vseh grafov v ekvivalenčne razrede. Množica med seboj izomorfnih grafov se imenuje razred izomorfizmov grafov.

Spodaj prikazana grafa sta izomorfna čeprav sta njuni sliki različni.

graf G	graf H	izomorfizem med G in H	permutacija izomorfizma $f\,$
		f(a) = 1 f(b) = 6 f(c) = 8 f(d) = 3 f(g) = 5 f(h) = 2 f(i) = 4 f(j) = 7	${\begin{pmatrix}a&b&c&d&g&h&i&j\\1&6&8&3&5&2&4&7\end{pmatrix}}$

Različice grafov

V zgornji definiciji so mišljeni neusmerjeni neoznačeni neuteženi grafi. Pojem izomorfizma se lahko uporabi tudi na vse druge različice pojma grafa z dodajanjem zahtev za ohranitev odgovarjajočih dodatnih elementov strukture: smeri lokov, teže povezav, itd. z naslednjo izjemo.

Izomorfizem označenih grafov

Za označene grafe se rabita dve definiciji.

Po eni definiciji je izomorfizem bijektivna preslikava točk, ki ohranja povezave in hkrati ohranja oznake.

Po drugi definiciji je izomorfizem bijektivna preslikava točk, ki ohranja povezave in ohranja ekvivalenčne razrede oznak, točke z ekevivalentnimi (oziroma enakimi) oznakami se preslikajo v točke z ekvivalentnimi oznakami in obratno, enako z oznakami povezav.

Graf $K_{2}\,$ z dvema točkama, označenima z 1 in 2, ima na primer en avtomorfizem po prvi definiciji in dva avtomorfizma po drugi definiciji.

Druga definicija se privzema v določenih primerih, ko imajo grafi edinstvene oznake običajno vzete iz množice celih števil 1,...,n, kjer je n število točk grafa, ki se rabijo le za enolično označitev točk. V takšnih primerih sta dva označena grafa izomorfna, če sta izomorfna odgovarjajoča osnovna neoznačena grafa, drugače bi bila definicija izomorfizma trivialna.

Motivacija

Formalna predstava »izomorfizma«, oziroma »izomorfizma grafov«, zavzema neformalno predstavo o tem, da imajo nekateri objekti »enako strukturo«, če se zanamerijo posamezne različnosti »atomskih« komponent obravnavanih objektov. Kadar je posameznost »atomskih« komponent (točk in povezav za grafe) pomembna za pravilno reprezentacijo tistega kar modelirajo grafi, se model izboljša z naložitvijo dodatnih omejitev na strukturo ali pa se uporabijo drugi matematični objekti: digrafi, označeni grafi, obarvani grafi, drevesa s korenom ipd. Relacija izomorfizma se lahko definira tudi za vse te posplošitve grafov: izomorfna bijektivna preslikava mora ohranjati elemente strukture, ki definira obravnavano vrsto objekta: loke, oznake, barve točk/povezav, koren dreves s korenom, itd.

Pojem »izomorfizma grafov« omogoča razlikovanje invariant grafov, ki pripadajo strukturam samih grafov, od invariant, ki so povezane z reprezentacijami grafov: slike grafov, podatkovne strukture za grafe, označevanje grafov itd. Če ima na primer graf točno en cikel, potem imajo tudi vsi grafi v njegovem izomorfnem razredu točno en cikel. Na drugi strani v splošnem primeru, kadar so točke grafa predstavljene s celimi števili 1, 2,... N, potem je lahko izraz:

$\sum _{v\in V(G)}v\cdot {\text{deg }}v\!\,$

različen za dva izomorfna grafa.

Whitneyjev izrek

Izjema Whitneyjevega izreka: ta dva grafa nista izomorfna, imata pa izomorfna povezavna grafa.

Whitneyjev izrek izomorfizma grafov, ki ga je podal Hassler Whitney, pravi, da sta dva povezana grafa izomorfna, če in samo če sta izomorfna njuna povezavna grafa, z eno izjemo: K₃, polnega grafa na 3-točkah in polnega dvodelnega grafa K_1,3 (šape), ki med seboj nista izomorfna, njun povezavni graf pa je K₃. Whitneyjev izrek se lahko posploši na hipergrafe.

Prepoznavanje izomorfizma grafov

Čeprav se lahko izomorfizem grafov raziskuje na klasični matematični način, kot pokaže Whitneyjev izrek, se kot problem obravnava algoritemsko. Računski problem prepoznavanja izomorfizma dveh grafov se imenuje problem izomorfizma grafov.

Med praktične uporabe spadajo: kemoinformatika, matematična kemija (identifikacija spojin) in avtomatizacija načrtovanja elektronike (EDA, preverjanje enakovrednosti različnih predstavitev konstrukcij elektronskih vezij).

Problem izomorfizma grafov je en od standardnih problemov v računski teoriji zahtevnosti in pripada razredu NP. Ni pa znano ali pripada (oziroma ali velja (problem P = NP|P ≠ NP]]) eni od njenih zelo znanih disjunktnih množic: P in NP-polnost. Je eden od skupaj 12-ih problemov, navedenih v delu Gareyja in Johnsona Computers and Intractability iz leta 1979 in njegova zahtevnost ostaja nerešena. Znano je, da če je problem NP-poln, se polinomska hierarhija zruši na končni nivo.

Novembra 2015 je László Babai, matematik in računalnikar z Univerze v Chicagu, najavil dokaz, da je problem izomorfizma grafov rešljiv v kvazipolinomskem času. Njegovo delo še ni potrjeno.

Posplošitev problema, problem izomorfizma podgrafa, je NP-poln.

Glavna področja raziskovanja problema so načrtovanje hitrih algoritmov in teoretični izsledki njegove računske zahtevnosti tako za splošni problem kot za posebne razrede grafov.

Glej tudi

• homomorfizem grafov
• avtomorfizem grafa
• kanonizacija grafa
• invarianta

Viri

• Champin, Pierre-Antoine; Solnon, Christine (2003). »Measuring the Similarity of Labeled Graphs«. Case-Based Reasoning Research and Development. Lecture Notes in Computer Science. Zv. 2689. str. 80–95. doi:10.1007/3-540-45006-8_9.
• Cho, Adrian (10. november 2015), »Mathematician claims breakthrough in complexity theory«, Science, doi:10.1126/science.aad7416
• Garey, Michael Randolph; Johnson, David Stifler (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, COBISS 93529, ISBN 0-7167-1045-5
• Hsieh, Shu-Ming; Hsu, Chiun-Chieh; Hsu, Li-Fu (2006). »Efficient Method to Perform Isomorphism Testing of Labeled Graphs«. Computational Science and Its Applications - ICCSA 2006. Lecture Notes in Computer Science. Zv. 3984. str. 422–431. doi:10.1007/11751649_46.
• Klarreich, Erica (14. december 2015), »Landmark Algorithm Breaks 30-Year Impasse«, Quanta Magazine
• Schöning, Uwe (1988), »Graph isomorphism is in the low hierarchy«, Journal of Computer and System Sciences, 37: 312–323, doi:10.1016/0022-0000(88)90010-4
• Vertigan, Dirk L.; Whittle, Geoffrey P. (1997), »A 2-Isomorphism Theorem for Hypergraphs«, Journal of Combinatorial Theory, Series B, 72 (2): 215–230
• Whitney, Hassler (Januar 1932), »Congruent Graphs and the Connectivity of Graphs«, American Journal of Mathematics, The Johns Hopkins University Press, 54 (1): 150–168, doi:10.2307/2371086, pridobljeno 17. avgusta 2012

Zunanje povezave

• Weisstein, Eric Wolfgang. »Graph Isomorphism«. MathWorld.