Gráfautomorfizmus

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

Definíció

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

$\{u,v\}\in E\iff \{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\to 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