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

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

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

Вычислительная сложность

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

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

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

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

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

Симметричный дисплей

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

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

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

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

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

Skeleton of the dodecahedron	Shrikhande graph	Paley graph
дистанционно-транзитивный	дистанционно-регулярный	сильно регулярный

F26A graph	Nauru graph
симметричный (дугопереходный)	t -транзитивен, t ≥ 2
(если подключен)
Holt graph	Folkman graph	Complete bipartite graph K3,5
вершинно- и реберно-транзитивен	реберно-транзитивный и регулярный	краево-транзитивный

Skeleton of the truncated tetrahedron	Frucht graph
вершинно-транзитивный	обычный

Skeleton of the triangular prism
Граф Кэли

См. также

Ссылки

^ Фрухт, Р. (1938), «Подготовка графов с заданной абстрактной группой» , Compositio Mathematica (на немецком языке), 6 : 239–250, ISSN 0010-437X , Zbl 0020.07804 .
^ Фрухт, Р. (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 года .
^ Jump up to: ^а ^б Матон, Р. (1979). «Заметка о проблеме подсчета изоморфизма графов». Письма об обработке информации . 8 (3): 131–132. дои : 10.1016/0020-0190(79)90004-8 .
^ Дона, Даниэле; Баджпай, Джитендра; Хелфготт, Харальд Андрес (12 октября 2017 г.). «Изоморфизмы графов за квазиполиномиальное время». arXiv : 1710.04574 [ math.GR ].
^ Jump up to: ^а ^б Любив, Анна (1981), «Некоторые NP-полные проблемы, подобные изоморфизму графов», SIAM Journal on Computing , 10 (1): 11–21, doi : 10.1137/0210002 , MR 0605600 .
^ Люкс, Юджин М. (1982), «Изоморфизм графов ограниченной валентности можно проверить за полиномиальное время», Journal of Computer and System Sciences , 25 (1): 42–65, doi : 10.1016/0022-0000(82) 90009-5 .
^ Кёблер, Йоханнес; Шенинг, Уве ; Торан, Хакобо (1993), Проблема изоморфизма графов: структурная сложность , Birkhäuser Verlag , ISBN 0-8176-3680-3 , OCLC 246882287
^ Jump up to: ^а ^б Торан, Хакобо (2004). «О сложности изоморфизма графов» (PDF) . SIAM Journal по вычислительной технике . 33 (5): 1093–1108. дои : 10.1137/S009753970241096X . Архивировано из оригинала (PDF) 20 ноября 2008 г. Проверено 10 марта 2010 г.
^ Маккей, Брендан (1981), «Практический изоморфизм графов» (PDF) , Congressus Numerantium , 30 : 45–87 , получено 14 апреля 2011 г.
^ Хунттила, Томми; Каски, Петтери (2007), «Разработка эффективного инструмента канонической разметки для больших и разреженных графов» (PDF) , Материалы девятого семинара по разработке алгоритмов и экспериментам (ALENEX07) .
^ Дарга, Пол; Сакалла, Карем; Марков, Игорь Л. (июнь 2008 г.), «Более быстрое обнаружение симметрии с использованием разреженности симметрий», Материалы 45-й ежегодной конференции по автоматизации проектирования (PDF) , стр. 149–154, doi : 10.1145/1391469.1391509 , ISBN 978-1-60558-115-6 , S2CID 15629172 , заархивировано из оригинала (PDF) 26 января 2021 г. , получено 14 апреля 2011 г.
^ Катеби, Хади; Сакалла, Карем; Марков, Игорь Л. (июль 2010 г.), «Симметрия и выполнимость: обновление» (PDF) , Proc. Симпозиум по удовлетворенности (SAT) .
^ Ди Баттиста, Джузеппе; Тамассия, Роберто ; Толлис, Иоаннис Г. (1992), «Требования к площади и отображение симметрии плоских восходящих рисунков», Дискретная и вычислительная геометрия , 7 (1): 381–401, doi : 10.1007/BF02187850 ; Идс, Питер ; Линь, Сюэмин (2000), «Пружинные алгоритмы и симметрия», Theoretical Computer Science , 240 (2): 379–405, doi : 10.1016/S0304-3975(99)00239-X .
^ Хонг, Сок-Хи (2002), «Симметричное рисование графиков в трех измерениях», Proc. 9-й Международный. Симп. Рисование графиков (GD 2001) , Конспекты лекций по информатике, том. 2265, Springer-Verlag, стр. 106–108, номер документа : 10.1007/3-540-45848-4_16 , ISBN. 978-3-540-43309-5 .

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

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

[1] Фрухт, Р. (1938), «Подготовка графов с заданной абстрактной группой» , Compositio Mathematica (на немецком языке), 6 : 239–250, ISSN 0010-437X , Zbl 0020.07804 .

[2] Фрухт, Р. (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 года .

[mathon-3] Jump up to: ^а ^б Матон, Р. (1979). «Заметка о проблеме подсчета изоморфизма графов». Письма об обработке информации . 8 (3): 131–132. дои : 10.1016/0020-0190(79)90004-8 .

[4] Дона, Даниэле; Баджпай, Джитендра; Хелфготт, Харальд Андрес (12 октября 2017 г.). «Изоморфизмы графов за квазиполиномиальное время». arXiv : 1710.04574 [ math.GR ].

[lubiw81-5] Jump up to: ^а ^б Любив, Анна (1981), «Некоторые NP-полные проблемы, подобные изоморфизму графов», SIAM Journal on Computing , 10 (1): 11–21, doi : 10.1137/0210002 , MR 0605600 .

[luks82-6] Люкс, Юджин М. (1982), «Изоморфизм графов ограниченной валентности можно проверить за полиномиальное время», Journal of Computer and System Sciences , 25 (1): 42–65, doi : 10.1016/0022-0000(82) 90009-5 .

[7] Кёблер, Йоханнес; Шенинг, Уве ; Торан, Хакобо (1993), Проблема изоморфизма графов: структурная сложность , Birkhäuser Verlag , ISBN 0-8176-3680-3 , OCLC 246882287

[t04-8] Jump up to: ^а ^б Торан, Хакобо (2004). «О сложности изоморфизма графов» (PDF) . SIAM Journal по вычислительной технике . 33 (5): 1093–1108. дои : 10.1137/S009753970241096X . Архивировано из оригинала (PDF) 20 ноября 2008 г. Проверено 10 марта 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) 26 января 2021 г. , получено 14 апреля 2011 г.

[12] Катеби, Хади; Сакалла, Карем; Марков, Игорь Л. (июль 2010 г.), «Симметрия и выполнимость: обновление» (PDF) , Proc. Симпозиум по удовлетворенности (SAT) .

[13] Ди Баттиста, Джузеппе; Тамассия, Роберто ; Толлис, Иоаннис Г. (1992), «Требования к площади и отображение симметрии плоских восходящих рисунков», Дискретная и вычислительная геометрия , 7 (1): 381–401, doi : 10.1007/BF02187850 ; Идс, Питер ; Линь, Сюэмин (2000), «Пружинные алгоритмы и симметрия», Theoretical Computer Science , 240 (2): 379–405, doi : 10.1016/S0304-3975(99)00239-X .

[14] Хонг, Сок-Хи (2002), «Симметричное рисование графиков в трех измерениях», Proc. 9-й Международный. Симп. Рисование графиков (GD 2001) , Конспекты лекций по информатике, том. 2265, Springer-Verlag, стр. 106–108, номер документа : 10.1007/3-540-45848-4_16 , ISBN. 978-3-540-43309-5 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]