stringtranslate.com

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

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

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

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

Построение группы автоморфизмов по крайней мере так же сложно (с точки зрения ее вычислительной сложности ), как и решение проблемы изоморфизма графов , определяющей, соответствуют ли два заданных графа вершина-вершина и ребро-ребро. Ибо G и H изоморфны тогда и только тогда, когда несвязный граф, образованный несвязным объединением графов G и H , имеет автоморфизм, который меняет местами два компонента. [3] Фактически, простой подсчет автоморфизмов полиномиально эквивалентен изоморфизму графа. [4]

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

Проблема автоморфизма графа — это проблема проверки того, имеет ли граф нетривиальный автоморфизм. Он относится к классу вычислительной сложности 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] Не всегда возможно отобразить все симметрии графика одновременно, поэтому может потребоваться выбрать, какие симметрии отображать, а какие оставить неотображенными.

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

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

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

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

Рекомендации

  1. ^ Фрухт, Р. (1938), "Herstellung von Graphen mit vorgegebener abstrakter Gruppe", Compositio Mathematica (на немецком языке), 6 : 239–250, ISSN  0010-437X, Zbl  0020.07804.
  2. ^ Фрухт, Р. (1949), «Графы третьей степени с заданной абстрактной группой», Canadian Journal of Mathematics , 1 (4): 365–378, doi : 10.4153/CJM-1949-033-6 , ISSN  0008- 414X, MR  0032987, S2CID  124723321.
  3. ^ ab Luks, Юджин М. (1982), «Изоморфизм графов ограниченной валентности можно проверить за полиномиальное время», Journal of Computer and System Sciences , 25 (1): 42–65, doi : 10.1016/0022-0000( 82)90009-5.
  4. ^ Аб Матон, Р. (1979). «Заметка о проблеме подсчета изоморфизма графов». Письма об обработке информации . 8 (3): 131–132. дои : 10.1016/0020-0190(79)90004-8.
  5. ^ ab Любив, Анна (1981), «Некоторые NP-полные проблемы, подобные изоморфизму графов», SIAM Journal on Computing , 10 (1): 11–21, doi : 10.1137/0210002, MR  0605600.
  6. ^ Кёблер, Йоханнес; Шенинг, Уве ; Торан, Хакобо (1993), Проблема изоморфизма графов: структурная сложность , Birkhäuser Verlag, ISBN 0-8176-3680-3, OCLC  246882287
  7. ^ Аб Торан, Хакобо (2004). «О сложности изоморфизма графов» (PDF) . SIAM Journal по вычислительной технике . 33 (5): 1093–1108. дои : 10.1137/S009753970241096X.
  8. ^ Маккей, Брендан (1981), «Практический изоморфизм графов» (PDF) , Congressus Numerantium , 30 : 45–87 , получено 14 апреля 2011 г.
  9. ^ Юнттила, Томми; Каски, Петтери (2007), «Разработка эффективного инструмента канонической разметки для больших и разреженных графов» (PDF) , Материалы девятого семинара по разработке алгоритмов и экспериментам (ALENEX07) .
  10. ^ Дарга, Пол; Сакалла, Карем; Марков, Игорь Л. (июнь 2008 г.), «Быстрое обнаружение симметрии с использованием разреженности симметрий», Труды 45-й ежегодной конференции по автоматизации проектирования (PDF) , стр. 149–154, doi : 10.1145/1391469.1391509, ISBN 978-1-60558-115-6, S2CID  15629172.
  11. ^ Катеби, Хади; Сакалла, Карем; Марков, Игорь Л. (июль 2010 г.), «Симметрия и выполнимость: обновление» (PDF) , Proc. Симпозиум по удовлетворенности (SAT) .
  12. ^ Ди Баттиста, Джузеппе; Тамассия, Роберто ; Толлис, Иоаннис Г. (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.
  13. ^ Хонг, Сок-Хи (2002), «Симметричное рисование графиков в трех измерениях», Proc. 9-й Международный. Симп. Рисование графиков (GD 2001) , Конспекты лекций по информатике, том. 2265, Springer-Verlag, стр. 106–108, номер документа : 10.1007/3-540-45848-4_16 , ISBN. 978-3-540-43309-5.

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