Автоморфизм

[miroslavKK]

Не могу никак понять, как определить количество автоморфизма у графов... Где-то нашел, что надо у графа пронумеровать вершины и искать симметрию, но что-то еще больше запутался. Ведь в примере 1 можно повернуть на 180 и на 90 градусов по часовой и против, тогда число автоморфизмов равно 4?

[arseniiv]

miroslavKK в сообщении #1322374 писал(а):

Ведь в примере 1 можно повернуть на 180 и на 90 градусов по часовой и против, тогда число автоморфизмов равно 4?

Почему на 90°? Он не совпадёт с собой при таком повороте.

-- Пн июн 25, 2018 00:30:08 --

Если вам трудно с симметриями, смотрите прямо по определению: ищите изоморфизмы между графом и его копией (нарисуйте её рядышком). И вам пригодится такое очевидное следствие: если $f$ — автоморфизм, степень вершин $a$ и $f(a)$ одинаковая. Это значительно сокращает перебор.