Izomorfni graf

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

• postoje bijekcije

${\displaystyle \exists }$ ${\displaystyle \theta :V(G)\rightarrow V(H)}$ i ${\displaystyle \phi :E(G)\rightarrow E(H)}$

tako da je vrh v incidentan s bridom ${\displaystyle e}$ u ${\displaystyle G}$

• ${\displaystyle \iff }$ ${\displaystyle \theta (v)}$ je incidentan s ${\displaystyle \phi (e)}$ u ${\displaystyle H}$.

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

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]

${\displaystyle |V(G)|=|V(H)|,|E(G)|=|E(H)}$

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]