В математической области теории графов автоморфизм графа — это форма симметрии , при которой граф отображается сам на себя, сохраняя при этом связность ребра и вершины .
Формально автоморфизм графа G = ( V , E ) — это перестановка σ множества вершин V такая, что пара вершин ( u , v ) образует ребро тогда и только тогда, когда пара ( σ ( u ), σ ( v )) также образуют ребро. То есть это изоморфизм графа G в себя. Автоморфизмы могут быть определены таким образом как для ориентированных , так и для неориентированных графов . Композиция двух автоморфизмов является другим автоморфизмом, и набор автоморфизмов данного графа при операции композиции образует группу , группу автоморфизмов графа. В противоположном направлении, по теореме Фрухта , все группы могут быть представлены как группа автоморфизмов связного графа - действительно, кубического графа . [1] [2]
Построение группы автоморфизмов по крайней мере так же сложно (с точки зрения ее вычислительной сложности ), как и решение проблемы изоморфизма графов , определяющей, соответствуют ли два заданных графа вершина-вершина и ребро-ребро. Ибо G и H изоморфны тогда и только тогда, когда несвязный граф, образованный несвязным объединением графов G и H , имеет автоморфизм, который меняет местами два компонента. [3] Фактически, простой подсчет автоморфизмов полиномиально эквивалентен изоморфизму графа. [4]
Проблема автоморфизма графа — это проблема проверки того, имеет ли граф нетривиальный автоморфизм. Он относится к классу вычислительной сложности NP . Как и в случае с проблемой изоморфизма графов, неизвестно, имеет ли она алгоритм с полиномиальным временем или является NP-полной . [5] Существует полиномиальный алгоритм решения проблемы автоморфизма графов для графов, в которых степени вершин ограничены константой. [3] Проблема автоморфизма графов полиномиально сводится к проблеме изоморфизма графов за полиномиальное время, но обратная редукция неизвестна. [4] [6] [7] Напротив, жесткость известна, когда автоморфизмы ограничены определенным образом; например, определение существования автоморфизма без неподвижных точек (автоморфизма, который не фиксирует ни одной вершины) является NP-полным, а проблема подсчета таких автоморфизмов является ♯P-полной . [5] [7]
Хотя для общей проблемы автоморфизма графов не известны алгоритмы наихудшего случая с полиномиальным временем, найти группу автоморфизмов (и распечатать неизбыточный набор генераторов) для многих больших графов, возникающих в приложениях, довольно легко. Для этой задачи доступно несколько программных инструментов с открытым исходным кодом, включая NAUTY, [8] BLISS [9] и SAUCY. [10] [11] SAUCY и BLISS особенно эффективны для разреженных графов, например, SAUCY обрабатывает некоторые графы с миллионами вершин за считанные секунды. Однако BLISS и NAUTY также могут создавать каноническую маркировку , тогда как SAUCY в настоящее время оптимизирован для решения автоморфизма графов. Важным наблюдением является то, что для графа на n вершинах группа автоморфизмов может быть задана не более чем генераторами, и вышеуказанные пакеты программного обеспечения гарантированно удовлетворяют этой границе как побочный эффект своих алгоритмов (минимальные наборы генераторов сложнее найти и на практике не особо полезны). Также оказывается, что общая поддержка (т. е. количество перемещенных вершин) всех генераторов ограничена линейной функцией от n , что важно при анализе этих алгоритмов во время выполнения. Однако по состоянию на март 2012 года это не установлено достоверно.
Практическое применение автоморфизма графов включает в себя рисование графов и другие задачи визуализации, решение структурированных случаев логической выполнимости, возникающих в контексте формальной проверки и логистики . Молекулярная симметрия может предсказать или объяснить химические свойства.
Несколько исследователей рисования графов исследовали алгоритмы рисования графов таким образом, что автоморфизмы графа становятся видимыми как симметрии рисунка. Это можно сделать либо с помощью метода, который не ориентирован на симметрию, но автоматически генерирует симметричные рисунки, когда это возможно, [12] , либо путем явного определения симметрий и использования их для управления размещением вершин на чертеже. [13] Не всегда возможно отобразить все симметрии графика одновременно, поэтому может потребоваться выбрать, какие симметрии отображать, а какие оставить неотображенными.
Несколько семейств графов определяются наличием определенных типов автоморфизмов:
Включительные отношения между этими семьями показаны в следующей таблице: