Izomorfni graf

Izvor: Hrvatska internetska enciklopedija
Skoči na:orijentacija, traži

Izomorfni graf, svojstvo grafova u teoriji grafova. Dva grafa G i H su izomorfni ako:[1]

[math]\displaystyle{ \exists }[/math] [math]\displaystyle{ \theta:V(G) \rightarrow V(H) }[/math] i [math]\displaystyle{ \phi:E(G) \rightarrow E(H) }[/math]

tako da je vrh v incidentan s bridom [math]\displaystyle{ e }[/math] u [math]\displaystyle{ G }[/math]

Uređeni par [math]\displaystyle{ f = (\theta,\phi) :G \rightarrow H }[/math] se tada zove izomorfnost iz [math]\displaystyle{ G }[/math] u [math]\displaystyle{ H }[/math].

Dakle, ako postoji bijektivna korespondencija između njih, takva da broj bridova koji spajaju bilo koja dva izabrana vrha iz prvog grafa jednaka broju bridova koji spajaju korespondentna dva vrha u drugom grafu. Dva su grafa izomorfna i ako možemo preimenovati vrhove jednog u vrhove onog drugog, uzevši u obzir da će vrhovima grafa ponekad biti dodijeljena imena (oznake, labele). Nuždan uvjet izomorfnosti je [2]

[math]\displaystyle{ |V(G)|=|V(H)|,|E(G)|=|E(H) }[/math]

V(G), V (H) su skupovi vhrhova. E(G), E(H) su skupovi bridova.

Izomorfnost čuva incidenciju i susjednost. Otkrivanje postojanja izomorfnosti između dvaju grafova spada u zanimljive i jedne od težih problema teorije grafova.[1]

Izvori

  1. 1,0 1,1 Sveučilište J. J. Strossmayera u Osijeku - Odjel za matematiku Iva Gregurić: Bojenje grafova, Osijek, 2011., str. 3, pristupljeno 28. veljače 2020.
  2. Element Uvod u teoriju grafova: 1. Pojam grafa, str. 4, pristupljeno 28. veljače 2020.