Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

Формально автоморфизм графа 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-1 генераторами, и вышеуказанные программные пакеты гарантированно удовлетворяют этой границе как побочному эффекту их алгоритмов (минимальные наборы генераторы труднее найти и не особенно полезны на практике). Также кажется, что общая поддержка (т. Е. Количество перемещаемых вершин) всех генераторов ограничена линейной функцией n , что важно при анализе этих алгоритмов во время выполнения. Однако по состоянию на март 2012 года этот факт не установлен.

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

Отображение симметрии [ править ]

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

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

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

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

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

дистанционно-транзитивныйдистанционно-регулярныйстрого регулярный
симметричный (дуго-транзитивный)t -транзитивный, t ≥ 2
(если подключен)
вершинно- и реберно-транзитивныереберно-транзитивные и регулярныереберно-транзитивный
вершинно-транзитивныйобычный
Граф Кэли

См. Также [ править ]

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

Ссылки [ править ]

  1. ^ Frucht, R. (1938), "Herstellung фон графена мит vorgegebener abstrakter Gruppe" , Compositio Mathematica (на немецком языке ), 6 : 239-250, ISSN  0010-437X , Zbl  0020,07804.
  2. ^ Frucht, R. (1949), "Графы третьей степени с данной абстрактной группы" , Canadian Journal математики , 1 (4): 365-378, DOI : 10,4153 / CJM-1949-033-6 , ISSN 0008- 414X , Руководство по ремонту 0032987  .
  3. ^ Б Luks, Евгений М. (1982), «Изоморфизм графов ограниченной валентности могут быть проверены в полиномиальное время», журнал компьютерных и системных наук , 25 (1): 42-65, DOI : 10.1016 / 0022-0000 (82) 90009-5.
  4. ^ a b Mathon, R. (1979). «Заметка о проблеме подсчета изоморфизмов графов». Письма об обработке информации . 8 : 131–132. DOI : 10.1016 / 0020-0190 (79) 90004-8 .
  5. ^ Б Lubiw, Анна (1981), "Некоторые NP-полные задачи , аналогичные изоморфизма графов", SIAM журнал по вычислениям , 10 (1): 11-21, DOI : 10,1137 / 0210002 , МР 0605600 .
  6. ^ Кёблер, Йоханнес; Шёнинг, Уве ; Торан, Якобо (1993), Проблема изоморфизма графов: структурная сложность , Birkhäuser Verlag , ISBN 0-8176-3680-3, OCLC  246882287
  7. ^ а б Торан, Якобо (2004). «О сложности изоморфизма графов» (PDF) . SIAM Journal on Computing . 33 : 1093–1108. DOI : 10.1137 / S009753970241096X .
  8. ^ Маккей, Brendan (1981), "Практическая Изоморфизм графов" (PDF) , Congressus Numerantium , 30 : 45-87 , получен 14 апреля 2011 .
  9. ^ Junttila, Томми; Каски, Петтери (2007), «Разработка эффективного инструмента канонической разметки для больших и разреженных графов» (PDF) , Труды девятого семинара по разработке алгоритмов и экспериментам (ALENEX07) .
  10. ^ Дарга, Пол; Сакаллах, Карем; Марков, Игорь Леонидович (июнь 2008), «Быстрее Симметрия Discovery с помощью разреженности симметрий» (PDF) , Труды 45 - й автоматизации проектирования конференции : 149-154, DOI : 10,1145 / 1391469,1391509 , ISBN  978-1-60558-115-6.
  11. ^ Катеби, Хади; Сакаллах, Карем; Марков, Игорь Л. (июль 2010 г.), «Симметрия и выполнимость: обновление» (PDF) , Proc. Симпозиум по удовлетворенности (SAT) .
  12. ^ Ди Баттиста, Джузеппе; Тамассия, Роберто ; Толлис, Иоаннис Г. (1992), «Требования к площади и отображение симметрии плоских восходящих чертежей», Дискретная и вычислительная геометрия , 7 (1): 381–401, doi : 10.1007 / BF02187850; Идс, Питер ; Lin, Xuemin (2000), "Весенние алгоритмы и симметрия", Теоретическая информатика , 240 (2): 379-405, DOI : 10.1016 / S0304-3975 (99) 00239-X.
  13. ^ Хонг, Сок-Хи (2002), "Симметричное рисование графиков в трех измерениях", Proc. 9-е межд. 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.

Внешние ссылки [ править ]

  • Вайсштейн, Эрик В. "Автоморфизм графа" . MathWorld .