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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

В математичному напрямку теорії графів, автоморфізм графа це форма симетрії за якої граф відображається на себе зі збереженням реберно-вершинних зв'язків.

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

Обчислювальна складність[ред.ред. код]

Побудова групи автоморфізмів щонайменше так само складне (в термінах теорії складності обчислень) як розв'язання проблеми ізоморфності графів. G і H ізоморфні тоді і тільки тоді, коли незв'язний граф утворений за допомогою диз'юнктивного об'єднання графів G і H має автоморфізм, що міняє місцями дві компоненти.[3]

Це зображення графа Петерсена показує підгрупу його симетрій, ізоморфну до дігедральної групи D5, але граф має додаткові симетрії, які не представлені на малюнку (бо граф симетричний).

Задача автоморфізму графа полягає в визначенні чи має граф нетривіальний автоморфізм. Вона належить до класу складності NP обчислювальної складності. Подібно до проблеми ізоморфізму графів, невідомо чи існує алгоритм з поліноміальним часом чи це NP-повна задача.[4] Відомо, що задача автоморфізму графа багатозначно зводима за поліноміальний час до проблеми ізоморфізму графів, але зворотна зводимість невідома.[5][6] [7]

Зображення симетрії[ред.ред. код]

Декілька дослідників візуалізації графів вивчали алгоритми зображення графів так, щоб автоморфізм графів був видимий як симетрія на малюнку. Це можна зробити через використання методу, який не був спроектованим навколо симетрій, але за можливості автоматично створює симетричні зображення,[8] або через явне визначення симетрій і використання їх як керівництва для розташування вершин в зображенні.[9] Не завжди можливо одночасно зобразити всі симетрії графа одночасно, тож виникає необхідність обирати які симетрії зображувати, а які залишати невідображеними.

Види графів за їхніми автоморфізмами[ред.ред. код]

Декілька видів графів через типи їхніх автоморфізмів:

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

Скелет додекаедра
Arrow east.svg
граф Шріханде
Arrow west.svg
граф Пейлі
відстанево-транзитивний відстанево-регулярний сильно регулярний
Arrow south.svg
граф F26A
Arrow west.svg
граф Науру
симетричний (дуго-транзитивний) t-транзитивний, t ≥ 2
Arrow south.svg
(якщо зв'язний)
граф Хольта
Arrow east.svg
граф Фолькмана
Arrow east.svg
Повний дводольний граф K3,5
вершинно- та реберно-транзитивний реберно-транзитивний і регулярний реберно-транзитивний
Arrow south.svg
Arrow south.svg
Скелет стятого тетраедра
Arrow east.svg
граф Фрухта
вершинно-транзитивний регулярний
Arrow north.svg
Скелет трикутної призми
Граф Келі

Див. також[ред.ред. код]

Примітки[ред.ред. код]

  1. Frucht, R. (1938), «Herstellung von Graphen mit vorgegebener abstrakter Gruppe.» (German), Compositio Mathematica 6: 239–250, Zbl 0020.07804, ISSN 0010-437X, http://www.numdam.org/item?id=CM_1939__6__239_0 .
  2. Frucht, R. (1949), «Graphs of degree three with a given abstract group», Canadian Journal of Mathematics 1: 365–378, MR0032987, ISSN 0008-414X, http://cms.math.ca/cjm/v1/p365 .
  3. Luks, Eugene M. (1982), «Isomorphism of graphs of bounded valence can be tested in polynomial time», Journal of Computer and System Sciences 25 (1): 42–65, doi:10.1016/0022-0000(82)90009-5 .
  4. A. Lubiw, "Some NP-complete problems similar to Graph Isomorphism", SIAM Journal on Computing, 1O:ll-21, 1981.
  5. R. Mathon, "A note on the graph isomorphism counting problem", Information Processing Letters, 8 (1979) pp. 131-132
  6. Köbler, Johannes; Uwe Schöning, Jacobo Torán (1993), Graph Isomorphism Problem: The Structural Complexity, Birkhäuser Verlag, ISBN 0817636803, OCLC 246882287 
  7. Jacobo Torán, "the Hardness of Graph Isomorphism", SIAM Journal on Computing, vol. 33, no. 5, 2004, pp. 1093-1108, doi:10.1137/S009753970241096X
  8. Di Battista, Giuseppe; Tamassia, Roberto; Tollis, Ioannis G. (1992), «Area requirement and symmetry display of planar upward drawings», Discrete and Computational Geometry 7 (1): 381–401, doi:10.1007/BF02187850 ; Eades, Peter; Lin, Xuemin (2000), «Spring algorithms and symmetry», Theoretical Computer Science 240 (2): 379–405, doi:10.1016/S0304-3975(99)00239-X .
  9. Hong, Seok-Hee (2002), «Drawing graphs symmetrically in three dimensions», 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 .