Автоморфизм графа

Отображение графа на самого себя без изменения связности ребер и вершин

В математической области теории графов автоморфизм графа — это форма симметрии , при которой граф отображается сам на себя, сохраняя при этом связность ребер и вершин .

Формально, автоморфизм графа G = ( V , E ) — это перестановка σ множества вершин V , такая, что пара вершин ( u , v ) образует ребро тогда и только тогда, когда пара ( σ ( u ), σ ( v )) также образует ребро. То есть, это изоморфизм графа из G в себя. Автоморфизмы могут быть определены таким образом как для ориентированных графов, так и для неориентированных графов . Композиция двух автоморфизмов — это другой автоморфизм, а множество автоморфизмов данного графа при операции композиции образует группу , группу автоморфизмов графа. В противоположном направлении, по теореме Фрухта , все группы могут быть представлены как группа автоморфизмов связного графа — на самом деле, кубического графа . ^{[1] [2]}

Сложность вычислений

Построение группы автоморфизмов графа в виде списка генераторов является полиномиально эквивалентной задачей изоморфизма графов и, следовательно, разрешимой за квазиполиномиальное время , то есть со временем выполнения для некоторого фиксированного . ^{[3] [4]} Следовательно, как и задача изоморфизма графов, задача нахождения группы автоморфизмов графа, как известно, принадлежит классу сложности NP , но неизвестно, принадлежит ли она классу P или является ли она NP-полной , и, следовательно, может быть NP-промежуточной . ${\displaystyle 2^{O((\log n)^{c})}}$ ${\displaystyle c>0}$

Этот рисунок графа Петерсена отображает подгруппу его симметрий, изоморфную диэдральной группе D ₅ , но граф имеет дополнительные симметрии, которые отсутствуют на рисунке. Например, поскольку граф симметричен , все ребра эквивалентны.

Более простая задача проверки наличия у графа симметрии (нетривиальных автоморфизмов), известная как задача автоморфизма графа , также не имеет известного решения за полиномиальное время . ^[5] Существует алгоритм полиномиального времени для решения задачи автоморфизма графа для графов, где степени вершин ограничены константой. ^[6] Задача автоморфизма графа сводится за полиномиальное время к задаче изоморфизма графа, но обратная редукция неизвестна. ^{[3] [7] [8]} Напротив, сложность известна, когда автоморфизмы ограничены определенным образом; например, определение существования автоморфизма без неподвижной точки (автоморфизма, который не фиксирует ни одной вершины) является NP-полной, а задача подсчета таких автоморфизмов является ♯P-полной . ^{[5] [8]}

Алгоритмы, программное обеспечение и приложения

Хотя для общей задачи автоморфизма графа не известны алгоритмы с полиномиальным временем в худшем случае , нахождение группы автоморфизмов (и вывод неизбыточного набора генераторов) для многих больших графов, возникающих в приложениях, довольно просто. Для этой задачи доступно несколько программных инструментов с открытым исходным кодом, включая NAUTY, ^[9] BLISS ^[10] и SAUCY. ^{[11] [12]} SAUCY и BLISS особенно эффективны для разреженных графов, например, SAUCY обрабатывает некоторые графы с миллионами вершин всего за несколько секунд. Однако BLISS и NAUTY также могут производить каноническую маркировку , тогда как SAUCY в настоящее время оптимизирован для решения задачи автоморфизма графа. Важное наблюдение заключается в том, что для графа с n вершинами группа автоморфизмов может быть задана не более чем генераторами, и вышеуказанные программные пакеты гарантированно удовлетворяют этой границе в качестве побочного эффекта своих алгоритмов (минимальные наборы генераторов сложнее найти и они не особенно полезны на практике). Также, похоже, что общая поддержка (т.е. количество перемещенных вершин) всех генераторов ограничена линейной функцией n , что важно при анализе времени выполнения этих алгоритмов. Однако, по состоянию на март 2012 года, это не было установлено как факт. ${\displaystyle n-1}$

Практические приложения графового автоморфизма включают рисование графов и другие задачи визуализации, решение структурированных случаев булевой выполнимости , возникающих в контексте формальной проверки и логистики . Молекулярная симметрия может предсказывать или объяснять химические свойства.

Симметричное отображение

Несколько исследователей рисования графов исследовали алгоритмы рисования графов таким образом, чтобы автоморфизмы графа становились видимыми как симметрии рисунка. Это можно сделать либо с помощью метода, который не разработан вокруг симметрий, но который автоматически генерирует симметричные рисунки, когда это возможно, ^[13] или путем явного определения симметрий и использования их для управления размещением вершин на рисунке. ^[14] Не всегда возможно отобразить все симметрии графа одновременно, поэтому может потребоваться выбрать, какие симметрии отображать, а какие оставить невизуализированными.

Семейства графов, определяемые их автоморфизмами

Несколько семейств графов определяются наличием определенных типов автоморфизмов:

• Асимметричный граф — это неориентированный граф, имеющий только тривиальный автоморфизм.
• Вершинно -транзитивный граф — это неориентированный граф, в котором каждая вершина может быть отображена автоморфизмом в любую другую вершину.
• Реберно -транзитивный граф — это неориентированный граф, в котором каждое ребро может быть отображено автоморфизмом в любое другое ребро.
• Симметричный граф — это граф, в котором каждая пара смежных вершин может быть отображена автоморфизмом в любую другую пару смежных вершин.
• Дистанционно -транзитивный граф — это граф, в котором каждая пара вершин может быть отображена автоморфизмом в любую другую пару вершин, находящихся на том же расстоянии друг от друга.
• Полусимметричный граф — это граф, который является рёберно-транзитивным, но не вершинно-транзитивным.
• Полутранзитивный граф — это граф, который является вершинно-транзитивным и рёберно-транзитивным, но не симметричным.
• Кососимметричный граф — это ориентированный граф вместе с перестановкой σ на вершинах, которая отображает ребра в ребра, но меняет направление каждого ребра на противоположное. Кроме того, σ требуется, чтобы быть инволюцией .

Отношения включения между этими семьями показаны в следующей таблице:

Смотрите также

• Алгебраическая теория графов
• Отличительная окраска

Ссылки

1. Фрухт, Р. (1938), "Herstellung von Graphen mit vorgegebener abstrakter Gruppe", Compositio Mathematica (на немецком языке), 6 : 239–250, ISSN  0010-437X, Zbl  0020.07804.
2. Frucht, R. (1949), «Графы степени три с заданной абстрактной группой» (PDF) , Canadian Journal of Mathematics , 1 (4): 365–378, doi : 10.4153/CJM-1949-033-6 , ISSN  0008-414X, MR  0032987, S2CID 124723321 , архивировано из оригинала 9 июня 2012 г. .
3. Mathon, R. (1979). «Заметка о проблеме подсчета изоморфизма графов». Information Processing Letters . 8 (3): 131–132. doi :10.1016/0020-0190(79)90004-8.
4. Дона, Даниэль; Баджпай, Джитендра; Хельфготт, Харальд Андрес (12 октября 2017 г.). «Изоморфизмы графов за квазиполиномиальное время». arXiv : 1710.04574 [math.GR].
5. Lubiw, Anna (1981), «Некоторые NP-полные задачи, похожие на изоморфизм графов», SIAM Journal on Computing , 10 (1): 11–21, doi :10.1137/0210002, MR  0605600.
6. Люкс, Юджин М. (1982), «Изоморфизм графов ограниченной валентности можно проверить за полиномиальное время», Журнал компьютерных и системных наук , 25 (1): 42–65, doi :10.1016/0022-0000(82)90009-5.
7. Кёблер, Йоханнес; Шенинг, Уве ; Торан, Хакобо (1993), Проблема изоморфизма графов: структурная сложность , Birkhäuser Verlag, ISBN 0-8176-3680-3, OCLC  246882287
8. Torán, Jacobo (2004). "On the hardness of graph ismorphism" (PDF) . SIAM Journal on Computing . 33 (5): 1093–1108. doi :10.1137/S009753970241096X. Архивировано из оригинала (PDF) 2008-11-20 . Получено 10.03.2010 .
9. Маккей, Брендан (1981), «Практический изоморфизм графов» (PDF) , Congressus Numerantium , 30 : 45–87 , получено 14 апреля 2011 г.
10. Юнттила, Томми; Каски, Петтери (2007), «Разработка эффективного инструмента канонической маркировки для больших и разреженных графов» (PDF) , Труды Девятого семинара по разработке алгоритмов и экспериментам (ALENEX07) .
11. Дарга, Пол; Сакаллах, Карем; Марков, Игорь Л. (июнь 2008 г.), «Быстрое обнаружение симметрии с использованием разреженности симметрий», Труды 45-й ежегодной конференции по автоматизации проектирования (PDF) , стр. 149–154, doi :10.1145/1391469.1391509, ISBN 978-1-60558-115-6, S2CID  15629172, заархивировано из оригинала (PDF) 2021-01-26 , извлечено 2011-04-14 .
12. Катеби, Хади; Сакаллах, Карем; Марков, Игорь Л. (июль 2010 г.), «Симметрия и выполнимость: обновление» (PDF) , Proc. Satisfiability Symposium (SAT) .
13. Ди Баттиста, Джузеппе; Тамассиа, Роберто ; Толлис, Иоаннис Г. (1992), «Требование площади и отображение симметрии плоских восходящих рисунков», Дискретная и вычислительная геометрия , 7 (1): 381–401, doi : 10.1007/BF02187850; Идс, Питер ; Лин, Сюэминь (2000), «Пружинные алгоритмы и симметрия», Теоретическая информатика , 240 (2): 379–405, doi :10.1016/S0304-3975(99)00239-X.
14. Хонг, Сок-Хи (2002), «Рисование графов симметрично в трех измерениях», Proc. 9th Int. Symp. Graph Drawing (GD 2001) , Lecture Notes in Computer Science, т. 2265, Springer-Verlag, стр. 106–108, doi : 10.1007/3-540-45848-4_16 , ISBN 978-3-540-43309-5.

Внешние ссылки

• Вайсштейн, Эрик В. «Автоморфизм графа». Математический мир .