Перечисление графов

Группа. Группа подстановки

Группа – алгебра с одно бинарной операцией ( ), которая обладает следующими свойствами:

1) замкнутость
и
2) ассоциативность

3) наличие нейтрального элемента

4) существование обратного элемента
для

Группа подстановки. Пусть . Подстановкой назовем .

Операция: произведение подстановок

Пример

Пример

Группа автоморфизмов графа

Пусть - некоторый граф. Автоморфизм графа - это изоморфизм на себя (с, сохраняющая отношение смежности между вершинами графа).

Пример

- не является автоморфизмом.
- автоморфизм.

Группа автоморфизмов графа - , где - множество всех автоморфизмов графа, - операция произведения.

Пример

:

Пример

Пример

Задание

Задан автоморфизм. Определить все графы, которые допускают данный автоморфизм.