Gráfizomorfizmus

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ó

Legyenek $G:=(V,E)$ és $G^{\prime }:=(V^{\prime },E^{\prime })$ gráfok. Egy $f:V\to V^{\prime }$ bijektív függvény gráfizomorfizmus, ha

$\{u,v\}\in E\iff \{f(u),f(v)\}\in E^{\prime }$.

Ilyenkor azt mondjuk, hogy $G$ és $G^{\prime }$ izomorf.

Példa

$G=(V,E)$	$G^{\prime }=(V^{\prime },E^{\prime })$	$f:V\to V^{\prime }$
		$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

• Gráfizomorfizmusok kompozíciója és inverze is gráfizomorfizmus; gráfok izomorfiája tehát ekvivalenciareláció.
• Egy gráf önmagával való izomorfizmusait automorfizmusoknak hívjuk. Egy $(V,E)$ gráf automorfizmusai a $V$ permutációcsoportjának egy részcsoportját alkotják.

További információk

• Sablon:Cite web

Lásd még

• Gráfhomomorfizmus
• Gráfizomorfizmus-probléma
• GI bonyolultsági osztály
• Gráfautomorfizmus