Izomorfni graf

Izvor: Wikipedija
Prijeđi na navigaciju Prijeđi na pretraživanje

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

i

tako da je vrh v incidentan s bridom u

  • je incidentan s u .

Uređeni par se tada zove izomorfnost iz u .

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]

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

  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.