Gráfautomorfizmus

A gráfautomorfizmus egy gráf önmagára való izomorfizmusa.

Definíció

Legyen $G:=(V,E)$ gráf. Egy $f:V \rightarrow V$ bijektív függvény gráfautomorfizmus, ha

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

Példa

$G = (V, E)$	$f:V \rightarrow V$
	$f(a) = g$ $f(b) = h$ $f(c) = i$ $f(d) = j$ $f(g) = a$ $f(h) = b$ $f(i) = c$ $f(j) = d$

Elemi tulajdonságok

• Gráfautomorfizmusok kompozíciója és inverze is gráfautomorfizmus.
• Egy $(V, E)$ gráf automorfizmusai a $V$ permutációcsoportjának egy részcsoportját alkotják.

Lásd még

• Gráfizomorfizmus
• Gráfhomomorfizmus
• Csúcstranzitív gráf