Izomorfizam grafova
U teoriji grafova, izomorfizam grafova G i H je bijekcija izmedju čvorova G i 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 . 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.