Автоморфізм графів: відмінності між версіями

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Інтерактивний перегляд історії
[неперевірена версія][неперевірена версія]
← Попереднє редагуванняНаступне редагування →
Вилучено вміст Додано вміст
ВізуальнийВікірозмітка
TXiKiBoT (обговорення | внесок)
Боти
195 330 редагувань
м r2.4.6) (робот додав: en:Graph automorphism
Немає опису редагування
Рядок 2: Рядок 2:


Формально, автоморфізм графа ''G''&nbsp;=&nbsp;(''V'',''E'') це [[перестановка]] &sigma; множини вершин ''V'' така, що для будь-якого ребра ''e''&nbsp;=&nbsp;(''u'',''v''), &sigma;(''e'')&nbsp;=&nbsp;(&sigma;(''u''),&sigma;(''v'')) також ребро. Тобто, це [[ізоморфізм графів|ізоморфізм]] ''G'' на себе. Автоморфізм може бути визначеним таким чином і для [[орієнтований граф|орієнтованих]], і для неорієнтованих графів. [[Композиція функцій|Композиція]] двох автоморфізмів це знов автоморфізм, і множина автоморфізмів даного графа, із операцією композиція, формує [[Група (математика)|групу]], [[група автоморфізмів|групу автоморфізмів]] графа. В зворотньому напрямку, за [[теорема Фрухта|теоремою Фрухта]], всі групи можуть бути представлені як група автоморфізмів зв'язного графа&nbsp;— насправді, [[кубічний граф|кубічного графа]].<ref>{{Citation | last1=Frucht | first1=R. | title=Herstellung von Graphen mit vorgegebener abstrakter Gruppe. | url=http://www.numdam.org/item?id=CM_1939__6__239_0 | language=German | id={{Zbl|0020.07804}} | year=1938 | journal=Compositio Mathematica | issn=0010-437X | volume=6 | pages=239–250}}.</ref><ref>{{Citation | last1=Frucht | first1=R. | title=Graphs of degree three with a given abstract group | url=http://cms.math.ca/cjm/v1/p365 | id={{MathSciNet | id = 0032987}} | year=1949 | journal=Canadian Journal of Mathematics | issn=0008-414X | volume=1 | pages=365–378}}.</ref>
Формально, автоморфізм графа ''G''&nbsp;=&nbsp;(''V'',''E'') це [[перестановка]] &sigma; множини вершин ''V'' така, що для будь-якого ребра ''e''&nbsp;=&nbsp;(''u'',''v''), &sigma;(''e'')&nbsp;=&nbsp;(&sigma;(''u''),&sigma;(''v'')) також ребро. Тобто, це [[ізоморфізм графів|ізоморфізм]] ''G'' на себе. Автоморфізм може бути визначеним таким чином і для [[орієнтований граф|орієнтованих]], і для неорієнтованих графів. [[Композиція функцій|Композиція]] двох автоморфізмів це знов автоморфізм, і множина автоморфізмів даного графа, із операцією композиція, формує [[Група (математика)|групу]], [[група автоморфізмів|групу автоморфізмів]] графа. В зворотньому напрямку, за [[теорема Фрухта|теоремою Фрухта]], всі групи можуть бути представлені як група автоморфізмів зв'язного графа&nbsp;— насправді, [[кубічний граф|кубічного графа]].<ref>{{Citation | last1=Frucht | first1=R. | title=Herstellung von Graphen mit vorgegebener abstrakter Gruppe. | url=http://www.numdam.org/item?id=CM_1939__6__239_0 | language=German | id={{Zbl|0020.07804}} | year=1938 | journal=Compositio Mathematica | issn=0010-437X | volume=6 | pages=239–250}}.</ref><ref>{{Citation | last1=Frucht | first1=R. | title=Graphs of degree three with a given abstract group | url=http://cms.math.ca/cjm/v1/p365 | id={{MathSciNet | id = 0032987}} | year=1949 | journal=Canadian Journal of Mathematics | issn=0008-414X | volume=1 | pages=365–378}}.</ref>

==Обчислювальна складність==
Побудова групи автоморфізмів щонайменше так само складне (в термінах [[Теорія складності обчислень|теорії складності обчислень]]) як розв'язання [[проблема ізоморфності графів|проблеми ізоморфності графів]]. ''G'' і ''H'' ізоморфні [[тоді і тільки тоді]], коли незв'язний граф утворений за допомогою диз'юнктивного об'єднання графів ''G'' і ''H'' має автоморфізм, що міняє місцями дві компоненти.<ref>{{citation|last=Luks|first=Eugene M.|title=Isomorphism of graphs of bounded valence can be tested in polynomial time|journal=Journal of Computer and System Sciences|volume=25|year=1982|pages=42–65|issue=1|doi=10.1016/0022-0000(82)90009-5}}.</ref>
[[Image:Petersen1_tiny.svg|thumb|right|Це зображення [[граф Петерсена|графа Петерсена]] показує [[підгрупа|підгрупу]] його симетрій, ізоморфну до [[Дігедральна група|дігедральної групи]] ''D''<sub>5</sub>, але граф має додаткові симетрії, які не представлені на малюнку (бо граф [[симетричний граф|симетричний]]).]]

'''Задача автоморфізму графа''' полягає в визначенні чи має граф нетривіальний автоморфізм. Вона належить до [[Клас складності NP|класу складності NP]] обчислювальної складності. Подібно до проблеми ізоморфізму графів, невідомо чи існує алгоритм з [[Клас складності P|поліноміальним часом]] чи це [[NP-повна задача]].<ref>A. Lubiw, "Some NP-complete problems similar to Graph Isomorphism", SIAM Journal on Computing, 1O:ll-21, 1981.</ref> Відомо, що задача автоморфізму графа [[Багатозначна зводимість|багатозначно зводима]] за поліноміальний час до проблеми ізоморфізму графів, але зворотня зводимість невідома.<ref>R. Mathon, "A note on the graph isomorphism counting problem", ''Information Processing Letters,'' 8 (1979) pp. 131-132 </ref><ref>{{Citation
| first = Johannes
| last = Köbler
| coauthors = Uwe Schöning, Jacobo Torán
| title = Graph Isomorphism Problem: The Structural Complexity
| publisher = [[:de:Birkhäuser Verlag|Birkhäuser Verlag]]
|isbn= 0817636803
| year = 1993
| oclc = 246882287}} </ref>
<ref>Jacobo Torán, "[http://theorie.informatik.uni-ulm.de/Personen/toran/papers/hard.pdf|On the Hardness of Graph Isomorphism]", ''SIAM Journal on Computing,'' vol. 33, no. 5, 2004, pp. 1093-1108, {{doi|10.1137/S009753970241096X}}</ref>

==Зображення симетрії==
Декілька дослідників [[Візуалізація графів|візуалізації графів]] вивчали алгоритми зображення графів так, щоб автоморфізм графів був видимий як симетрія на малюнку. Це можна зробити через використання методу, який не був спроектованим навколо симетрій, але за можливості автоматично створює симетричні зображення,<ref>{{citation|first1=Giuseppe|last1=Di Battista|first2=Roberto|last2=Tamassia|first3=Ioannis G.|last3=Tollis|title=Area requirement and symmetry display of planar upward drawings|journal=Discrete and Computational Geometry|volume=7|issue=1|year=1992|pages=381–401|doi=10.1007/BF02187850}}; {{citation|first1=Peter|last1=Eades|first2=Xuemin|last2=Lin|title=Spring algorithms and symmetry|journal=Theoretical Computer Science|volume=240|issue=2|year=2000|pages=379–405|doi=10.1016/S0304-3975(99)00239-X}}.</ref> або через явне визначення симетрій і використання їх як керівництва для розташування вершин в зображенні.<ref>{{citation|first=Seok-Hee|last=Hong|contribution=Drawing graphs symmetrically in three dimensions|title=Proc. 9th Int. Symp. Graph Drawing (GD 2001)|publisher=Springer-Verlag|series=Lecture Notes in Computer Science|year=2002|volume=2265|doi=10.1007/3-540-45848-4_16|pages=106–108}}.</ref> Не завжди можливо одночасно зобразити всі симетрії графа одночасно, тож виникає необхідність обирати які симетрії зображувати, а які залишати невідображеними.


{{пишу}}
{{пишу}}

Версія за 09:46, 12 березня 2011

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

Формально, автоморфізм графа 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] Не завжди можливо одночасно зобразити всі симетрії графа одночасно, тож виникає необхідність обирати які симетрії зображувати, а які залишати невідображеними.

Ця стаття в процесі редагування певний час.

Будь ласка, не редагуйте її, бо Ваші зміни можуть бути втрачені.

Якщо ця сторінка не редагувалася кілька днів, будь ласка, приберіть цей шаблон. Це повідомлення призначене для уникнення конфліктів редагування.

Останнє редагування зробив користувач Igor Yalovecky (внесок, журнали) о 09:46 UTC (6982079 хвилин тому).

Див. також

Примітки

  1. ↑ Frucht, R. (1938), Herstellung von Graphen mit vorgegebener abstrakter Gruppe., Compositio Mathematica (German) , 6: 239—250, ISSN 0010-437X, Zbl 0020.07804.
  2. ↑ Frucht, R. (1949), Graphs of degree three with a given abstract group, Canadian Journal of Mathematics, 1: 365—378, ISSN 0008-414X, MR0032987.
  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.
Отримано з https://uk.wikipedia.org/w/index.php?title=Автоморфізм_графів&oldid=6250817