WikiSysop: Bot: Automatski unos stranica

2021-12-06T10:01:42Z

Bot: Automatski unos stranica

Nova stranica

'''Izomorfni graf''', svojstvo grafova u [[teorija grafova|teoriji grafova]]. Dva [[Graf (teorija grafova)|grafa]] G i H su [[izomorfnost|izomorfni]] ako:<ref name=Gregurić/>
* postoje [[bijekcija|bijekcije]]
<math>\exists</math> <math> \theta:V(G) \rightarrow V(H)</math> i <math>\phi:E(G) \rightarrow E(H)</math>

tako da je [[vrh (teorija grafova)|vrh]] v incidentan s [[Brid (teorija grafova)|bridom]] <math>e</math> u <math>G</math>

*[[akko|<math>\iff </math>]] <math>\theta(v)</math> je incidentan s <math>\phi(e)</math> u <math>H</math>.

[[Uređeni par]] <math>f = (\theta,\phi) :G \rightarrow H</math> se tada zove izomorfnost iz <math>G</math> u <math>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 <ref>[https://element.hr/artikli/file/1322/uvod-u-teoriju-grafova/13537 Element] Uvod u teoriju grafova: 1. Pojam grafa, str. 4, pristupljeno 28. veljače 2020.</ref>

<math>|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 [[Incidencija (teorija grafova)|incidenciju]] i [[susjednost (teorija grafova)|susjednost]]. Otkrivanje postojanja izomorfnosti između dvaju grafova spada u zanimljive i jedne od težih problema teorije grafova.<ref name=Gregurić>[http://www.mathos.unios.hr/~mdjumic/uploads/diplomski/GRE10.pdf Sveučilište J. J. Strossmayera u Osijeku - Odjel za matematiku] Iva Gregurić: Bojenje grafova, Osijek, 2011., str. 3, pristupljeno 28. veljače 2020.</ref>

== Izvori ==
{{izvori}}

[[Kategorija:Teorija grafova]]

Izomorfni graf - Povijest promjena

WikiSysop: Bot: Automatski unos stranica