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 | forrásszöveg szerkesztése]

Legyenek G:=(V,E) és G':=(V',E') gráfok. Egy f:V \rightarrow V' bijektív függvény gráfizomorfizmus, ha

\{u,v\}\in E \Leftrightarrow \{f(u),f(v)\}\in E'.

Ilyenkor azt mondjuk, hogy G és G' izomorf.

Példa[szerkesztés | forrásszöveg szerkesztése]

G = (V, E) G' = (V', E') f:V \rightarrow V'
Graph isomorphism a.svg Graph isomorphism b.svg  f(a) = 1

 f(b) = 6

 f(c) = 8

 f(d) = 3

 f(g) = 5

 f(h) = 2

 f(i) = 4

 f(j) = 7

Elemi tulajdonságok[szerkesztés | forrásszöveg szerkesztése]

Lásd még[szerkesztés | forrásszöveg szerkesztése]