Gráfizomorfizmus

A Wikipédiából, a szabad enciklopédiából

A gráfizomorfizmusok gráfok közötti bijektív struktúratartó leképezések, értve ezalatt azt, hogy a függvény és az inverz függvény egyaránt szomszédos csúcsokat szomszédos csúcsokra képez le. Az általuk meghatározott ekvivalenciarelációt gráfizomorfiának nevezzük.

Definíció[szerkesztés]

Legyenek és gráfok. Egy bijektív függvény gráfizomorfizmus, ha

.

Ilyenkor azt mondjuk, hogy és izomorf.

Példa[szerkesztés]

Graph isomorphism a.svg Graph isomorphism b.svg

Elemi tulajdonságok[szerkesztés]

Lásd még[szerkesztés]