Automorfizm grafu

Automorfizm grafu – wzajemnie jednoznaczne przekształcenie ${\displaystyle \varphi }$ zbioru wierzchołków grafu w ten sam zbiór takie, że wierzchołki ${\displaystyle \varphi (u)}$ oraz ${\displaystyle \varphi (v)}$ są sąsiednie wtedy i tylko wtedy, gdy ${\displaystyle u}$ i ${\displaystyle v}$ są sąsiednie^[1].

Formalnie automorfizmem grafu ${\displaystyle G}$ jest każdy izomorfizm ${\displaystyle G}$ z nim samym, a więc bijekcja

${\displaystyle \varphi \colon \operatorname {V} (G)\to \operatorname {V} (G)}$

taka, że

${\displaystyle uv\in \operatorname {E} (G)\iff \varphi (u)\varphi (v)\in \operatorname {E} (G)}$

gdzie ${\displaystyle \operatorname {V} (G)}$ oznacza zbiór wierzchołków ${\displaystyle G}$, a ${\displaystyle \operatorname {E} (G)}$ zbiór jego krawędzi.

Szczególnym przypadkiem jest przekształcenie identycznościowe, które każdemu wierzchołkowi przypisuje jego samego. W kontekście automorfizmów przekształcenie to często nazywa się trywialnym automorfizmem i oznacza przez ${\displaystyle e}$ lub ${\displaystyle \operatorname {id} }$.

Zbiór automorfizmów dowolnego grafu ${\displaystyle G}$ wraz z dwuargumentową operacją ich składania ${\displaystyle \circ }$ tworzą jego grupę automorfizmów, zwykle oznaczaną przez ${\displaystyle \operatorname {Aut} (G)}$. Aby przekonać się, że ${\displaystyle \operatorname {Aut} (G)}$ jest grupą, można zauważyć, że ma ona własności grupy:

• Wewnętrzność: dla dowolnych automorfizmów ${\displaystyle f,g}$ ze zbioru ${\displaystyle \operatorname {Aut} (G)}$, złożenie ${\displaystyle f\circ g}$ również jest automorfizmem ${\displaystyle G}$,
• Łączność: dla każdych ${\displaystyle f,g,h}$ należących do ${\displaystyle \operatorname {Aut} (G)}$ zachodzi ${\displaystyle (f\circ g)\circ h=f\circ (g\circ h)}$,
• Element neutralny: przekształcenie identycznościowe ${\displaystyle e}$ na wierzchołkach ${\displaystyle G}$ należy do ${\displaystyle \operatorname {Aut} (G)}$,
• Odwracalność: każdy automorfizm grafu z definicji jest odwracalny, a jego odwrotność również jest automorfizmem, więc dla każdego elementu ${\displaystyle f}$ w ${\displaystyle \operatorname {Aut} (G)}$ istnieje ${\displaystyle g}$ w ${\displaystyle \operatorname {Aut} (G)}$, takie że ${\displaystyle f\circ g=e}$.

Na mocy udowodnionego w 1938 roku przez Roberta Fruchta twierdzenia zachodzi także odpowiedniość odwrotna, a więc dla każdej grupy ${\displaystyle \Gamma }$ można znaleźć graf ${\displaystyle G}$, taki że ${\displaystyle \Gamma }$ jest izomorficzna z ${\displaystyle \operatorname {Aut} (G)}$^[2][3], co w rozumieniu współczesnej algebry oznacza identyczność tych grup^[4].

• Robin J. Wilson: Wprowadzenie do teorii grafów. Warszawa: Wydawnictwo Naukowe PWN, 1998. ISBN 978-83-01-15066-2.
• Aleksiej I. Kostrikin: Wstęp do algebry 1. Podstawy algebry. Warszawa: Wydawnictwo Naukowe PWN, 2004. ISBN 83-01-14252-9.

• Nauty – szybki program autorstwa Brendana D. McKay do obliczania grup automorfizmów grafów i digrafów (potrafi również sprawdzać izomorficzność).
• Eric W.E.W. Weisstein Eric W.E.W., Graph Automorphism, [w:] MathWorld, Wolfram Research  (ang.). [dostęp 2025-12-22].
• Graph automorphism (ang.), Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2025-12-14].