Izomorfni graf

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

• postoje bijekcije

[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]

• [math]\displaystyle{ \iff }[/math] [math]\displaystyle{ \theta(v) }[/math] je incidentan s [math]\displaystyle{ \phi(e) }[/math] u [math]\displaystyle{ H }[/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

[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.