Automorfizm grafu – wzajemnie jednoznaczne przekształcenie zbioru wierzchołków grafu w ten sam zbiór takie, że wierzchołki oraz są sąsiednie wtedy i tylko wtedy, gdy i są sąsiednie.
Definicja Formalnie automorfizmem grafu jest każdy izomorfizm z nim samym, a więc bijekcja
taka, że
gdzie oznacza zbiór wierzchołków , a 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 lub .
Grupa automorfizmów Zbiór automorfizmów dowolnego grafu wraz z dwuargumentową operacją ich składania tworzą jego grupę automorfizmów, zwykle oznaczaną przez . Aby przekonać się, że jest grupą, można zauważyć, że ma ona własności grupy: Wewnętrzność: dla dowolnych automorfizmów ze zbioru , złożenie również jest automorfizmem , Łączność: dla każdych należących do zachodzi , Element neutralny: przekształcenie identycznościowe na wierzchołkach należy do , Odwracalność: każdy automorfizm grafu z definicji jest odwracalny, a jego odwrotność również jest automorfizmem, więc dla każdego elementu w istnieje w , takie że .
Na mocy udowodnionego w 1938 roku przez Roberta Fruchta twierdzenia zachodzi także odpowiedniość odwrotna, a więc dla każdej grupy można znaleźć graf , taki że jest izomorficzna z , co w rozumieniu współczesnej algebry oznacza identyczność tych grup.
Przypisy
Bibliografia
Linki zewnętrzne Nauty – szybki program autorstwa Brendana D. McKay do obliczania grup automorfizmów grafów i digrafów (potrafi również sprawdzać izomorficzność). [dostęp 2025-12-22]. Graph automorphism , Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2025-12-14].
Kategoria:Teoria grafów Kategoria:Morfizmy