Automorfizmy grafu

[dusiek]

Mam znaleźć automorfizmy grafu:

Automorfizm - to taka permutacja \(\displaystyle{ \alpha}\) wierzchołków, dla której zachodzi: \(\displaystyle{ \left\{ v,w\right\} \in E\left[ G\right] \Leftrightarrow \left\{ \alpha \left( v\right), \alpha \left( w\right) \right\} \in E\left[ G\right]}\) gdzie \(\displaystyle{ E\left[ G\right]}\) to zbiór krawędzi grafu \(\displaystyle{ G}\).
Czy jest jakaś ogólna metoda szukania automorfizmów grafu?

[Ein]

Intuicyjnie, automorfizmy zachowują "kształt" grafu. Z definicji automorfizmu (izomofizmu) jasno widać, że muszą być zachowane rzędy wierzchołków. W Twoim przykładzie np. tylko wierzchołek \(\displaystyle{ 3}\) ma stopień równy 4, a więc każdy automorfizm zachowa ten wierzchołek (tzn. nie przekształci go na żaden inny wierzchołek). Podobnie wierzchołek \(\displaystyle{ 1}\), mając stopień równy 1, może przejść tylko i wyłącznie na siebie bądź na wierzchołek \(\displaystyle{ 2}\). Analogicznie ma się sprawa z wierzchołkiem \(\displaystyle{ 2}\) -- może on przejść na siebie bądź na \(\displaystyle{ 1}\). Ponadto zauważ, że rzędy sąsiadów danego wierzchołka muszą się zgadzać przy przejściu przez izomorfizm. Stąd każdy automorfizm zachowa wierzchołek \(\displaystyle{ 5}\), ponieważ tylko on ma stopień 2 oraz wszyscy jego sąsiedzi mają stopień równy 2. Kwestię wierzchołków \(\displaystyle{ 4}\) i \(\displaystyle{ 6}\) pozostawiam Tobie do rozważenia.

[dusiek]

Czyli wszystkie automorfizmy to:

\(\displaystyle{ \alpha _{1} = \left( 1\right) \left( 2\right) \left( 3\right) \left( 4\right) \left( 5\right) \left( 6\right) \\
\alpha _{2} = \left( 3\right) \left( 4\right) \left( 5\right) \left( 6\right) \left( 12\right) \\
\alpha _{3} = \left( 1\right) \left( 2\right) \left( 3\right) \left( 5\right) \left( 46\right) \\
\alpha _{4} = \left( 3\right) \left( 5\right) \left( 12\right) \left( 46\right) \\}\)

Wielkie dzięki

[Ein]

Zgadza się.

Pozdrawiam.