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.

Graph G Graph H An isomorphism
between G and H
Graph isomorphism a.svg Graph isomorphism b.svg 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.

Reference[уреди]