Автоморфизм графа
В математической области теории графов автоморфизм симметрии графа , — это форма сам при которой граф отображается на себя, сохраняя при этом связность ребра и вершины .
Формально автоморфизм графа 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] БЛАЖЕНСТВО [9] и дерзкий . [10] [11] SAUCY и BLISS особенно эффективны для разреженных графов, например, SAUCY обрабатывает некоторые графы с миллионами вершин за считанные секунды. Однако BLISS и NAUTY также могут создавать каноническую маркировку , тогда как SAUCY в настоящее время оптимизирован для решения автоморфизма графов. Важным наблюдением является то, что для графа с n вершинами группа автоморфизмов может быть задана не более чем генераторы, и вышеуказанные пакеты программного обеспечения гарантированно удовлетворяют этому ограничению как побочный эффект их алгоритмов (минимальные наборы генераторов найти труднее, и они не особенно полезны на практике). Также оказывается, что общая поддержка (т. е. количество перемещенных вершин) всех генераторов ограничена линейной функцией от n , что важно при анализе этих алгоритмов во время выполнения. Однако по состоянию на март 2012 года это не установлено достоверно.
Практическое применение автоморфизма графов включает в себя рисование графов и другие задачи визуализации, решение структурированных случаев логической выполнимости , возникающих в контексте формальной проверки и логистики . Молекулярная симметрия может предсказать или объяснить химические свойства.
Отображение симметрии [ править ]
Несколько исследователей рисования графов исследовали алгоритмы рисования графов таким образом, что автоморфизмы графа становятся видимыми как симметрии рисунка. Это можно сделать либо с помощью метода, который не основан на симметрии, но автоматически генерирует симметричные чертежи, когда это возможно, [12] или путем явного определения симметрий и использования их для определения размещения вершин на чертеже. [13] Не всегда возможно отобразить все симметрии графика одновременно, поэтому может потребоваться выбрать, какие симметрии отображать, а какие оставить неотображенными.
определяемые их автоморфизмами , Семейства графов
Несколько семейств графов определяются наличием определенных типов автоморфизмов:
- Асимметричный граф — это неориентированный граф, имеющий только тривиальный автоморфизм.
- Вершинно -транзитивный граф — это неориентированный граф, в котором каждая вершина может быть отображена автоморфизмом в любую другую вершину.
- Реберно -транзитивный граф — это неориентированный граф, в котором каждое ребро может быть отображено автоморфизмом в любое другое ребро.
- — Симметричный граф это граф, в котором каждая пара смежных вершин может быть отображена автоморфизмом в любую другую пару смежных вершин.
- Дистанционно -транзитивный граф — это граф, в котором каждая пара вершин может быть отображена автоморфизмом в любую другую пару вершин, находящихся на таком же расстоянии друг от друга.
- Полусимметричный граф — это граф, транзитивный по ребрам, но не транзитивный по вершинам.
- Полутранзитивный граф — это граф, который является вершинно-транзитивным и реберно-транзитивным, но не симметричным.
- — Кососимметричный граф это ориентированный граф с перестановкой σ в вершинах, которая отображает ребра в ребра, но меняет направление каждого ребра на противоположное. Кроме того, σ должен быть инволюцией .
Включительные отношения между этими семьями показаны в следующей таблице:
 |  |  |  |  |
| дистанционно-транзитивный | дистанционно-регулярный | сильно регулярный | ||
 | ||||
 | |  | ||
| симметричный (дугопереходный) | t -транзитивен, t ≥ 2 | |||
| ||||
 | |  | |  |
| вершинно- и реберно-транзитивен | реберно-транзитивный и регулярный | краево-транзитивный | ||
| | |||
 | |  | ||
| вершинно-транзитивный | обычный | |||
 | ||||
 | ||||
| Граф Кэли |
См. также [ править ]
Ссылки [ править ]
- ^ Фрухт, Р. (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: Перейти обратно: а б Люкс, Юджин М. (1982), «Изоморфизм графов ограниченной валентности можно проверить за полиномиальное время», Journal of Computer and System Sciences , 25 (1): 42–65, doi : 10.1016/0022-0000(82) 90009-5 .
- ^ Jump up to: Перейти обратно: а б Матон, Р. (1979). «Заметка о проблеме подсчета изоморфизма графов». Письма об обработке информации . 8 (3): 131–132. дои : 10.1016/0020-0190(79)90004-8 .
- ^ Jump up to: Перейти обратно: а б Любив, Анна (1981), «Некоторые NP-полные проблемы, подобные изоморфизму графов», SIAM Journal on Computing , 10 (1): 11–21, doi : 10.1137/0210002 , MR 0605600 .
- ^ Кёблер, Йоханнес; Шенинг, Уве ; Торан, Хакобо (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 .
- ^ Маккей, Брендан (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 .
- ^ Катеби, Хади; Сакалла, Карем; Марков, Игорь Л. (июль 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 .