Izomorfizam grafova

U teoriji grafova, izomorfizam grafova G i H je bijekcija izmedju čvorova G i H

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

takva da bilo koja dva čvora u i v iz G su susedni čvorovi u G ako i samo ako ƒ(u) i ƒ(v) su susedni čvorovi u H.

U gornjoj definiciji, podrazumeva se da su grafovi neusmereni, neobeleženi i da grane nemaju težinu. Medjutim, notacija izmorfizma može biti primenjena na sve druge varijante notacije grafova, dodajući uslove koji ce sačuvati odgovarajuće dodatne elemente strukture: pravac, težinu grane, itd., sa sledećim izuzetkom. Kada se govori o obležavanju grafova sa jedinstvenim oznakama, koje obično idu od 1, 2,..., n, gde je n broj cvorova grafa, dva obelezena grafa su izomorfna ako su odgovarajuci polazni neobelezeni grafi izomorfni.

Ako postoji izomorfizam izmedju dva grafa, onda kažemo da su grafovi izomorfni i pišemo $G\simeq H$. U slučaju da bijekcija slika graf u samoga sebe npr., kada G i H predstavljaju isti graf, onda se bijekcija naziva automorfizam od G.

Izomorfizam grafova je relacija ekvivalencije i kao takva, deli klasu svih grafova u klase ekvivalencije. Skup medjusobno izomorfnih grafova se zove klasa izomorfizama grafova.

Primer

Sledeća dva grafu su izomorfna, iako njihovi crteži izgledaju potpuno drugacije.

Graf G	Graf H	Izomorfizam između G i H
		f(a) = 1 f(b) = 6 f(c) = 8 f(d) = 3 f(g) = 5 f(h) = 2 f(i) = 4 f(j) = 7

Motivacija

Formalna notacija izomorfizma, npr. izomorfizam grafova, obuhvata neformalnu notaciju da neki objekti imaju istu strukturu ako se ignorisu idividualne razlike sitnih komponenti objekata u pitanju. Kada god je individualnost sitnih komponenti (cvorovi, grane) važna za tačnu reprezentaciju bilo čega što je modelovano grafovima, model bude doradjen dodajući dodatne uslove na strukturu.