6.30. Группы и обыкновенные графы

Каждый обыкновенный граф обладает, по крайней мере, одним собственным изоморфизмом, а именно, тривиальным изоморфизмом, при котором каждая вершина и ребро соответствуют самим себе. Однако кроме изоморфизма тождественности можно установить и другие виды собственного изоморфизма. Изоморфизм графа с самим собой называется автоморфизмом. Совокупность автоморфизмов графа образует группу, называемую группой графа. Такую группу всегда можно рассматривать как группу перестановок вершин графа. Автоморфизмы многоугольника с сторонами (n-угольника) образуют группу, которая называется группой диэдра порядка Группа автоморфизмов полного -вершинного графа называется симметричной группой порядка Порядок группы называется симметрическим числом графа. Задача о том, является ли каждая перестановочная группа в общем случае группой графа, до сих пор не решена. Она возникает при определении числа неизоморфных графов с заданной перестановочной группой.

Упражнение 6.28. (см. скан)

Рассмотрим операцию сложения целых чисел по модулю заданного целого числа. Укажем с помощью графа отношения между элементами, входящими в вычеты при добавлении ко всем этим элементам одного из них. Например, возьмем целые числа по Получим вычеты 0, 1, 2, 3, 4 и 5. Добавим ко всем

вычетам 4 и укажем полученные связи. Начнем с нуля. В результате получим два контура рис. 6.72.

С другой стороны, умножение на 4 дает граф рис. 6.73. Точки О, 2 и 4 называются фиксированными, так как они отображаются на себя. Аналогично можно получить граф для функции например, где а и о — элементы класса вычетов, а х принимает значение из этого же класса.

Упражнение 6.29. (см. скан)

Рис. 6.71.

Рис. 6.72.

Рис. 6.73.

Замечание. Дробь получается следующим образом. Сначала находится элемент х в классе вычетов, который после умножения на 3 дает т. е. получаем, что Умножая 4X5, получим Следовательно,

Упражнение 6.30, (см. скан)

Рассмотренные идеи приводят к графам, которые известны под названием цветных графов Кэли, или диаграмм Вениа. Начнем с некоторой конечной группы и выделим ее подмножество (например, множество элементов, которые формируют группу). Поставим в соответствие каждому элементу группы некоторую

вершину и дугу, которая заканчивается вершине, являющейся конечной точкой преобразования (например, умножения или сложения), выполняемого элементом выделенного подмножества над рассматриваемым элементом.

Таким образом, каждая вершина является начальной для стольких дуг, сколько элементов содержится в рабочем подмножестве. Каждая дуга окрашивается в свой цвет, соответствующий цвету элемента рабочего подмножества. Заметим, что вершине соответствует петля, если воздействие тождественно. В результате формируется цветной граф Кэли. Известно, что такой граф связен тогда и только тогда, когда в процессе его получения образуется группа, т. е. существует путь между любой парой вершин, так как с помощью последовательных умножений на элементы подмножества любой рассматриваемый элемент можно преобразовать в любой другой. Таким образом, 4 не формирует группы, определенной вычетами по mod 6 при сложении, так как соответствующий граф не связен.

Упражнение 6.31. Показать, что 5 является генератором такой группы, доказав, что соответствующий граф связен.