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

.

Tehát a gráfautomorfizmus a gráf csúcsainak olyan p permutációja, melyben bármely két u és v csúcs pontosan akkor szomszédos egymással, ha p(u) és p(v) is szomszédosak.

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