Вкладення графа

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

У топологічній теорії графів, вкладення (також пишеться врізання) графа  у поверхню Σ  — це представлення графа на Σ, де точки Σ асоціюються з вершинами та прості дуги (гомеоморфні образи [0,1]) асоціюються з ребрами таким чином, що:

  • кінцеві точки дуги, які пов'язані з ребром , є точками, пов'язані з кінцевими вершинами дуги
  • ніяка дуга не містить точки, які асоційовані з іншими вершинами,
  • ніякі дві дуги не перетинаються у внутрішніх точках цих дуг.

Тут поверхня є компактним, зв'язаним 2-многовидом

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

Часто вкладення розглядається, як клас еквівалентності (за гомеоморфізмами Σ) представлень описаного виду.

Деякі автори дають більш слабку версію визначення «вкладення графа», в якій не вимагається відсутність перетинів ребер. У цьому контексті більш сильне визначення описується як «вкладення графа без перетинів».[2]

Ця стаття обговорює тільки строге визначення вкладення графа. Слабке визначення обговорюється в статтях «візуалізації графів» і «число перетинів».

Термінологія

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

Двоклітинне вкладання або карта (map) — це вкладення, при якому кожна грань гомеоморфна відкритому диску.[4]

Двоклітинне замкнуте вкладання — вкладення, при якому замикання будь-якої межі гомеоморфно замкнутому диску.

Рід графа — це мінімальне ціле число n, при якому граф може бути вкладений в поверхню роду n. Зокрема, планарний граф має рід 0, оскільки його можна намалювати на сфері без самоперетинів. Не орієнтований рід графа — це мінімальне ціле число n, таке, що граф може бути вкладений у не орієнтовану поверхню (не орієнтованого) роду n.[3]

Ейлерів рід — це мінімальне ціле число n s, при якому граф може бути вкладений у орієнтовану поверхню (орієнтованого) роду n/2 або орієнтовану поверхню (неориентируємого) роду n. Граф є просто орієнтованим, якщо його ейлерів рід менше, ніж не орієнтований рід.

Максимальний рід графа — це максимальне ціле число n при якому граф може бути двоклітинно вкладеним в орієнтовану поверхню роду n.

Комбінаторне вкладення

Основна стаття: Система обертання[en]

Вкладений граф однозначно визначає циклічні порядки ребер, інцидентних тій же самій вершині. Множина всіх цих циклічних порядків називається круговою системою[en]. Вкладення з тієї ж самої кругової системи вважаються еквівалентними, і відповідний клас еквівалентності вкладень називається комбінаторним вкладенням (як противагу терміну топологічне вкладення, яке відноситься до попереднього визначення точок і кривих). Іноді кругова система сама називається «комбінаторним вкладенням» [5][6][7]

Вкладений граф також визначає природні циклічні порядки ребер, які задають границі граней вкладення. Однак робота з цими гране-орієнтованими порядками менш очевидні, оскільки в деяких випадках деякі ребра можуть проходити двічі при обході границі грані. Наприклад, це завжди вірно при вкладенні дерев, які мають єдину грань. Щоб подолати цю комбінаторну перешкоду, можна вважати кожне ребро «розділеним» на два «півребра» або на дві «сторони». При цих угодах у всіх гранях границя проходить кожне півребро тільки раз і кожне півребро одного ребра завжди проходить в протилежних напрямках.

Обчислювальна складність

Задача визначення роду графа є NP-повною (задача визначення, чи має граф з n вершинами рід g, є NP-повною).[8]

У той же самий час задача визначення роду графа є фіксовано-параметрично вирішуваною[en], тобто відомі алгоритми з поліноміальним часом перевірки, може граф бути вкладеним у поверхню із заданим родом. Те ж вірно і для пошуку вкладення.

Перший прорив відбувся у 1979 році, коли алгоритми з часовою складністю O(nO(g)) були незалежно представлені щорічному симпозіуму ACV з теорії обчислень[en]: — один алгоритм запропонували В. Филотти і Г. Л. Міллер, а інший — Джон Райф. Їх підходи були повністю відмінними, але за пропозицією організаційного комітету вони представили об'єднану статтю.[9]

В 1999 було оголошено, що випадок фіксованого роду може бути вирішено за лінійний час від розміру графа і за подвійний експоненціальний час[en] від роду[10]

Вкладення графа простору великих розмірностей

Відомо, що будь-який кінцевий граф може бути вкладений в тривимірний простір.[1]

Один з методів такого вкладення — помістити точки (вершини графа) на прямій і малювати ребра як криві, що лежать в окремих півплощинах, які мають цю пряму як спільну для всіх півплощин границю. Такого роду вкладення називається книжковим вкладенням[en] графа. Ця метафора стає зрозумілою, якщо представити кожну півплощину у вигляді сторінки книги. Зрозуміло, що деякі ребра можна намалювати без перехрещень на одній і тій же «сторінці».

Книжковою товщиною графа називається мінімальне число півплощин в книжковому вкладенні.

З іншого боку, будь-який кінцевий граф можна намалювати без перетинів у тривимірному просторі з прямими ребрами шляхом розміщення вершин у загальному положенні таким чином, що ніякі чотири некопланарні (не лежать в одній площині). Наприклад, цього можна досягти, розміщуючи i-ту вершину в точці (i, i2, i3) на кривій моментів[en]

Вкладення графа в тривимірний простір, в якому ніякі два цикли не є топологічно зачепленими, називається  не зачепленим вкладенням[en]. Граф має незачеплене вкладення тоді і тільки тоді, коли він не містить жодного з семи графів петерсонова сімейства як мінору.

Див. також

Примітки

  1. а б Cohen, Robert F.; Eades, Peter; Lin, Tao; Ruskey, Frank (1995). Three-dimensional graph drawing. У Tamassia, Roberto; Tollis, Ioannis G. Graph Drawing: DIMACS International Workshop, GD '94 Princeton, New Jersey, USA, October 10–12, 1994, Proceedings. Lecture Notes in Computer Science 894. Springer. с. 1–11. doi:10.1007/3-540-58950-3_351. .
  2. Katoh, Naoki; Tanigawa, Shin-ichi (2007). Enumerating Constrained Non-crossing Geometric Spanning Trees. Computing and Combinatorics, 13th Annual International Conference, COCOON 2007, Banff, Canada, July 16-19, 2007, Proceedings. Lecture Notes in Computer Science 4598. Springer-Verlag. с. 243–253. ISBN 978-3-540-73544-1. doi:10.1007/978-3-540-73545-8_25. .
  3. а б Gross, Jonathan; Tucker, Thomas W. (2001). Topological Graph Theory. Dover Publications. ISBN 0-486-41741-7. .
  4. Lando, Sergei K.; Zvonkin, Alexander K. (2004). Graphs on Surfaces and their Applications. Springer-Verlag. ISBN 3-540-00203-0. .
  5. Mutzel, Petra; Weiskircher, René (2000). Computing Optimal Embeddings for Planar Graphs. Computing and Combinatorics, 6th Annual International Conference, COCOON 2000, Sydney, Australia, July 26–28, 2000, Proceedings. Lecture Notes in Computer Science 1858. Springer-Verlag. с. 95–104. ISBN 978-3-540-67787-1. doi:10.1007/3-540-44968-X_10. .
  6. Didjev, Hristo N. (1995). On drawing a graph convexly in the plane. Graph Drawing, DIMACS International Workshop, GD '94, Princeton, New Jersey, USA, October 10–12, 1994, Proceedings. Lecture Notes in Computer Science 894. Springer-Verlag. с. 76–83. doi:10.1007/3-540-58950-3_358. .
  7. Duncan, Christian; Goodrich, Michael T.; Kobourov, Stephen (2010). Planar Drawings of Higher-Genus Graphs. Graph Drawing, 17th International Symposium, GD 2009, Chicago, IL, USA, September 22-25, 2009, Revised Papers. Lecture Notes in Computer Science 5849. Springer-Verlag. с. 45–56. ISBN 978-3-642-11804-3. doi:10.1007/978-3-642-11805-0_7. .
  8. Thomassen, Carsten (1989). The graph genus problem is NP-complete. Journal of Algorithms 10 (4): 568–576. doi:10.1016/0196-6774(89)90006-0. 
  9. Filotti, I. S.; Miller, Gary L.; Reif, John (1979). On determining the genus of a graph in O(v O(g)) steps(Preliminary Report). Proc. 11th Annu. ACM Symposium on Theory of Computing. с. 27–37. doi:10.1145/800135.804395. .
  10. Mohar, Bojan (1999). A linear time algorithm for embedding graphs in an arbitrary surface. SIAM Journal on Discrete Mathematics 12 (1): 6–26. doi:10.1137/S089548019529248X.