Izomorfni graf

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

• postoje bijekcije

$\mathrm{\exists }$ $\theta :V(G)\to V(H)$ i $\varphi :E(G)\to E(H)$

tako da je vrh v incidentan s bridom $e$ u $G$

• $⟺$ $\theta (v)$ je incidentan s $\varphi (e)$ u $H$.

Uređeni par $f=(\theta ,\varphi ):G\to H$ se tada zove izomorfnost iz $G$ u $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

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