Автоморфизм графа - Graph automorphism
В математической области теории графов , автоморфизм графа является формой симметрии , в которой график отображается на себя, сохраняя при этом возможность соединения края вершины.
Формально автоморфизм графа G = ( V , E ) - это перестановка σ множества вершин V такая, что пара вершин ( u , v ) образует ребро тогда и только тогда, когда пара (σ ( u ), σ ( v )) также образуют ребро. То есть, это изоморфизм графов из G к себе. Таким образом можно определить автоморфизмы как для ориентированных, так и для неориентированных графов . Композиция двух автоморфизмов еще один автоморфизм, а множество автоморфизмов данного графа, при операции композиции, образует группу , в группу автоморфизмов графа. В противоположном направлении, по теореме Фрухта , все группы могут быть представлены как группа автоморфизмов связного графа - точнее, кубического графа .
Вычислительная сложность
Построение группы автоморфизмов по крайней мере так же сложно (с точки зрения ее вычислительной сложности ), как решение проблемы изоморфизма графов , определение того, соответствуют ли два заданных графа вершина за вершиной и ребро за ребром. Действительно, G и H изоморфны тогда и только тогда, когда несвязный граф, образованный несвязным объединением графов G и H, имеет автоморфизм, который меняет местами две компоненты. Фактически, простой подсчет автоморфизмов полиномиально эквивалентен изоморфизму графов.
Проблема автоморфизма графа - это проблема проверки наличия у графа нетривиального автоморфизма. Он принадлежит к классу вычислительной сложности NP . Подобно проблеме изоморфизма графов, неизвестно, имеет ли она алгоритм с полиномиальным временем или он является NP-полным . Существует алгоритм с полиномиальным временем для решения проблемы автоморфизма графов для графов, в которых степени вершин ограничены константой. Проблема автоморфизма графов за полиномиальное время сводится к проблеме изоморфизма графов, но обратная редукция неизвестна. Напротив, твердость известна, когда автоморфизмы ограничены определенным образом; например, определение существования автоморфизма без неподвижной точки (автоморфизма, не фиксирующего вершину) является NP-полным, а проблема подсчета таких автоморфизмов является ♯P-полной .
Алгоритмы, программное обеспечение и приложения
Хотя для общей проблемы автоморфизма графов не известны алгоритмы наихудшего случая с полиномиальным временем, найти группу автоморфизмов (и распечатать неизбыточный набор генераторов) для многих больших графов, возникающих в приложениях, довольно просто. Для этой задачи доступно несколько программных инструментов с открытым исходным кодом, включая NAUTY , BLISS и SAUCY . SAUCY и BLISS особенно эффективны для разреженных графов, например, SAUCY обрабатывает некоторые графы с миллионами вершин за считанные секунды. Однако BLISS и NAUTY также могут создавать канонические метки, тогда как SAUCY в настоящее время оптимизирован для решения автоморфизма графов. Важное наблюдение состоит в том, что для графа с n вершинами группа автоморфизмов может быть определена не более чем с n-1 генераторами, и вышеуказанные программные пакеты гарантированно удовлетворяют этой границе как побочному эффекту их алгоритмов (минимальные наборы генераторы труднее найти и не особенно полезны на практике). Также кажется, что общая поддержка (т. Е. Количество перемещаемых вершин) всех генераторов ограничена линейной функцией n , что важно при анализе этих алгоритмов во время выполнения. Однако по состоянию на март 2012 года этот факт не установлен.
Практические приложения автоморфизма графов включают рисование графов и другие задачи визуализации, решение структурированных примеров логической удовлетворенности, возникающих в контексте формальной проверки и логистики . Молекулярная симметрия может предсказывать или объяснять химические свойства.
Отображение симметрии
Несколько графиков рисования ученые исследовали алгоритмы для рисования графиков таким образом , что автоморфизмы графа становятся видимыми как симметрии рисунка. Это можно сделать либо с помощью метода, который не ориентирован на симметрии, но который автоматически генерирует симметричные рисунки, когда это возможно, либо путем явного определения симметрий и их использования для направления размещения вершин на рисунке. Не всегда возможно отобразить все симметрии графика одновременно, поэтому может потребоваться выбрать, какие симметрии отображать, а какие оставить невидимыми.
Семейства графов, определяемые их автоморфизмами
Несколько семейств графов определяются наличием определенных типов автоморфизмов:
- Асимметричный граф неориентированный граф с только тривиальным автоморфизмом.
- Вершина-симметрический граф неориентированный граф , в котором каждая вершина может быть отображена на автоморфизм в любую другую вершину.
- Края симметрический граф неориентированный граф , в котором каждое ребро может быть отображен на автоморфизм в любой другой край.
- Симметрический граф представляет собой график , таким образом, что каждая пара смежных вершин может быть отображена на автоморфизм в любую другую пару смежных вершин.
- Расстояние-симметрический граф представляет собой график таким образом, что каждая пара вершин может быть отображен на автоморфизм в любой другой паре вершин , которые находятся на одинаковом расстоянии друг от друга.
- Пол-симметрический граф представляет собой график , который является краевым транзитивен , но не вершиной-транзитивны.
- Половинной симметрический граф представляет собой график , который является вершиной-симметрический и ребра транзитивны , но не симметричным.
- Кососимметрична граф представляет собой ориентированный граф вместе с перестановкой а на вершинах, отображающие края к краям , но изменяет направление каждого ребра. Кроме того, требуется, чтобы σ была инволюцией .
Отношения включения между этими семьями показаны в следующей таблице:
