Gráfautomorfizmus
A gráfautomorfizmus egy gráf önmagára való izomorfizmusa.
Definíció[szerkesztés]
Legyen gráf. Egy bijektív függvény gráfautomorfizmus, ha
- .
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[szerkesztés]
|
Elemi tulajdonságok[szerkesztés]
- Gráfautomorfizmusok kompozíciója és inverze is gráfautomorfizmus.
- Egy gráf automorfizmusai a permutációcsoportjának egy részcsoportját alkotják.