Вкладення графа: відмінності між версіями

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Наступне редагування →
Вилучено вміст Додано вміст
ВізуальнийВікірозмітка
частково переклав
Мітки: суміш розкладок у тексті Візуальний редактор
(Немає відмінностей)

Версія за 18:55, 10 грудня 2016

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

At the same time, the graph genus problem is fixed-parameter tractable, i.e., polynomial time algorithms are known to check whether a graph can be embedded into a surface of a given fixed genus as well as to find the embedding.

The first breakthrough in this respect happened in 1979, when algorithms of time complexity O(nO(g)) were independently submitted to the Annual ACM Symposium on Theory of Computing: one by I. Filotti and G.L. Miller and another one by John Reif. Their approaches were quite different, but upon the suggestion of the program committee they presented a joint paper.

In 1999 it was reported that the fixed-genus case can be solved in time linear in the graph size and doubly exponential in the genus.

Embeddings of graphs into higher-dimensional spaces[edit source]

It is known that any finite graph can be embedded into a three-dimensional space.

One method for doing this is to place the points on any line in space and to draw the edges as curves each of which lies in a distinct halfplane, with all halfplanes having that line as their common boundary. An embedding like this in which the edges are drawn on halfplanes is called a book embedding of the graph. This metaphor comes from imagining that each of the planes where an edge is drawn is like a page of a book. It was observed that in fact several edges may be drawn in the same "page"; the book thickness of the graph is the minimum number of halfplanes needed for such a drawing.

Alternatively, any finite graph can be drawn with straight-line edges in three dimensions without crossings by placing its vertices in general position so that no four are coplanar. For instance, this may be achieved by placing the ith vertex at the point (i,i2,i3) of the moment curve.

An embedding of a graph into three-dimensional space in which no two of the cycles are topologically linked is called a linkless embedding. A graph has a linkless embedding if and only if it does not have one of the seven graphs of the Petersen family as a minor.

See also[edit source]

References[edit source]

  1. ^ Jump up to:a b .
  2. Jump up^ .
  3. ^ Jump up to:a b .
  4. Jump up^ .
  5. Jump up^ .
  6. Jump up^ .
  7. Jump up^ .
  8. Jump up^ 
  9. Jump up^ .
  10. Jump up^ 
  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, doi:10.1007/978-3-540-73545-8_25, ISBN 978-3-540-73544-1.
  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, doi:10.1007/3-540-44968-X_10, ISBN 978-3-540-67787-1.
  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, doi:10.1007/978-3-642-11805-0_7, ISBN 978-3-642-11804-3.
  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
Отримано з https://uk.wikipedia.org/w/index.php?title=Вкладення_графа&oldid=19318118