Toggle menu
310,1 tis.
44
18
525,6 tis.
Hrvatska internetska enciklopedija
Toggle preferences menu
Toggle personal menu
Niste prijavljeni
Your IP address will be publicly visible if you make any edits.

Izomorfni graf

Izvor: Hrvatska internetska enciklopedija

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

  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.
Sadržaj