Верхушечный граф

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

В теории графов верхушечный граф — это граф, который можно сделать планарным удалением одной вершины. Удалённая вершина называется верхушкой графа. Заметим, что верхушка может быть не одна. Например, в минимальном непланарном графе K₅ или K_3,3 каждая вершина является верхушкой. Верхушечные графы включают изначально планарные графы, в которых каждая вершина является верхушкой. Нуль-граф считается также верхушечным, хотя в нём нет вершин для удаления .

Верхушечные графы замкнуты относительно операции образования миноров и играют большую роль в некоторых других аспектах теории миноров графов, включая незацепленное вложение^[1], гипотезу Хадвигера^[2], YΔY-сводимые графы^[3] и связь между древесной шириной и диаметром графа^[4][5].

Описание и распознавание

Верхушечные графы замкнуты относительно операции образования миноров — стягивание любого ребра или удаление вершины или ребра приводит к другому верхушечному графу. Действительно, если граф G является верхушечным с верхушкой v, то стягивание или удаление, не затрагивающее вершину v, сохраняет планарность остального графа (без вершины v). то же самое верно и при удалении любого ребра, инцидентного v. Если стягивается ребро, инцидентное v, эффект эквивалентен удалению противоположного конца ребра. Если же удаляется сама вершина v, любую другую вершину можно считать верхушкой^[6].

Поскольку верхушечные графы замкнуты по операции образования миноров, по теореме Робертсона – Сеймура они имеют характеризацию запрещёнными графами. Существует лишь конечное число графов, которые не являются верхушечными графами и не содержат в качестве минора другой граф, не являющийся верхушечным. Эти графы являются запрещёнными минорами для свойства «верхушечный граф». Любой другой граф G является верхушечным тогда и только тогда, когда ни один из запрещённых миноров не является минором графа G. Запрещённые миноры включают семь графов из петерсенова семейства, три несвязных графа, образованных из непересекающихся объединений K₅ и K_3,3 и много других графов. Полный список всех запрещённых миноров остаётся незавершённым^[6][7].

Несмотря на то, что полный список запрещённых миноров не известен, есть возможность за линейное время проверить, является ли данный граф верхушечным, и если он таковой, найти верхушку графа . Более обще, для любой фиксированной константы k можно за линейное время распознать k-верхушечные графы (графы, в которых удаление аккуратно выбранного множества, содержащего не более k вершин, приводит к планарному графу^[8]). Однако, если k не фиксировано, задача становится NP-полной^[9].

Хроматическое число

Любой верхушечный граф имеет хроматическое число, не превосходящее пяти — планарный граф без верхушки требует не более четырёх цветов по теореме о четырёх красках, а для верхушки достаточно одного добавочного цвета. Робертсон, Сеймур и Томас^[2] использовали этот факт для доказательства случая k = 6 гипотезы Хадвигера, утверждения, что любой 6-хроматический граф имеет полный граф K₆ в качестве минора — они показали, что любой минимальный контрпример гипотезе должен быть верхушечным графом, но верхушечных 6-хроматических графов нет, так что такого контрпримера не существует.

Нерешённые проблемы математики: Является ли любой вершинно 6-связный граф без миноров ${\displaystyle K_{6}}$ верхушечным?

Йоргенсен^[10] высказал гипотезу, что любой вершинно 6-связный граф, не имеющий в качестве миноров K₆, должен быть верхушечным. Если бы это было доказано, результат Робертсона – Сеймура – Томаса для гипотезы Хадвигера стал бы прямым следствием^[2]. Гипотеза Йоргенсена пока не доказана^[11]. Однако если гипотеза не верна, она имеет лишь конечное число контрпримеров^[12].

Локальная древесная ширина

Семейство графов F имеет ограниченную локальную древесную ширину, если графы из F подчиняются функциональной зависимостью между диаметром и древесной шириной — существует функция ƒ, такая, что древесная ширина графа из F с диаметром d не превосходит ƒ(d). Верхушечные графы не имеют ограниченной локальной древесной ширины — граф, образованный соединением верхушки с каждой вершиной n × n решётки имеет древесную ширину n и диаметр 2, так что древесная ширина не ограничена некоторой функцией от диаметра этих графов. Однако верхушечные графы тесно связаны с графами с ограниченной локальной древесной шириной — замкнутые по минорам семейства графов F, имеющие ограниченную локальную древесную ширину, являются в точности семействами, одним из запрещённых миноров которых является какой-либо верхушечный граф^[4][5]. Замкнутые по минорам семейства графов, имеющие верхушечный граф в качестве минора, известны как свободные от верхушечного минора. Согласно этой терминологии связь между верхушечными графами и локальной древесной шириной можно переформулировать так: семейства графов, свободных от верхушечных миноров, совпадают с семействами замкнутых по минорам графов с ограниченной локальной древесной шириной.

Концепция ограниченной локальной древесной ширины образует базис теории двухмерности^[англ.] и позволяют решать многие алгоритмические задачи на свободных от верхушечных миноров графах в точности алгоритмом полиномиального времени, или фиксированно-параметрически разрешимым^[англ.] алгоритмом, или задача может быть приближена с помощью приближенной схемы полиномиального времени^[4][13][14]. Для свободных от верхушечных миноров семейств графов выполняется усиленная версия структурной теоремы графов, что приводит к дополнительным аппроксимационным алгоритмам для раскраски графов и для задачи коммивояжёра^[15]. Однако некоторые из этих результатов могут быть распространены на произвольные замкнутые по минорам семейства графов с помощью использования структурных теорем на связанные с семействами свободные от верхушечных миноров графы^[16].

Вложения

Если граф G является верхушечным графом с верхушкой v и ${\displaystyle \tau }$ равно минимальному числу граней, необходимых для покрытия всех соседей верхушки v при планарном вложении G\{v}, то G может быть вложено в двумерную поверхность рода ${\displaystyle \tau -1}$ путём добавления такого числа мостов к планарному вложению, соединив тем самым все грани, с которыми верхушка v должна быть соединена. Например, добавление одной вершины к внешнепланарному графу (графу с a ${\displaystyle \tau =1}$) даёт планарный граф. Если граф G\{v} 3-связен, его граница не отличается от оптимальной более чем на постоянный множитель — любое вложение G в поверхность требует род по меньшей мере ${\displaystyle \tau /160}$. Однако задача определения оптимального рода для поверхности вложения для верхушечных графов является NP-трудной задачей^[17].

При использовании SPQR-деревьев для кодировки возможных вложений планарной части верхушечного графа, можно вычислить за полиномиальное время укладку графа на плоскость, в которой пересечения вызваны только рёбрами, исходящими из верхушечной вершины, и общее число пересечений минимально^[18]. Если разрешены произвольные пересечения, задача минимизации числа пересечений становится NP-трудной задачей даже в специальном случае верхушечных графов, образованных добавлением одного ребра в планарный граф^[19].

Верхушечные графы вложимы без зацепления в трёхмерное пространство — их можно вложить так, что любой цикл в графе является границей диска, который не пересекается любой другой частью графа^[20]. Рисунок такого типа можно получить, нарисовав планарную часть графа на плоскости, поместив верхушку графа над плоскостью, и соединив её с соседями отрезками. Вложимые без зацеплений графы образуют замкнутое по минорам семейство с семью графами из петерсенова семейства в качестве минимальных запрещённых миноров^[1]. Таким образом, эти графы являются запрещёнными минорами и для верхушечных графов. Существуют, однако, вложимые без зацепления графы, не являющиеся верхушечными.

YΔY-сводимость

Пример Робертсона YΔY-несводимого верхушечного графа.

Связный граф является YΔY-сводимым, если он может быть сведён к одиночной вершине последовательностью шагов, каждый из которых является Δ-Y или Y-Δ преобразованием, удалением петли или кратных рёбер, удалением вершины с одним соседом и заменой вершины степени два и двух её смежных рёбер одним ребром^[3].

Подобно верхушечным графам и вложимым без зацепления графам YΔY-сводимые графы замкнуты относительно операции образования миноров. Подобно вложимым без зацепления графам YΔY-сводимые графы имеют семь графов из петерсенова семейства в качестве минимальных запрещённых миноров, откуда возникает вопрос, не являются ли только эти графы запрещёнными минорами и не совпадают ли семейства YΔY-сводимых графов и вложимых без зацепления графов. Нейл Робертсон, однако, привёл пример верхушечного графа, не являющегося YΔY-сводимым. Поскольку любой верхушечный граф вложим без зацепления, это показывает, что существуют вложимые без зацепления графы, не являющиеся YΔY-сводимыми, а потому существуют дополнительные запрещённые миноры для YΔY-сводимых графов^[3].

Верхушечный граф Робертсона показан на рисунке. Его можно получить соединением верхушки со всеми вершинами степени три ромбододекаэдра или путём слияния двух противоположных вершин графа четырёхмерного гиперкуба. Поскольку граф ромбододекаэдра планарен, граф Робертсона является верхушечным. Граф не содержит треугольников и имеет минимальную степень четыре, так что к нему нельзя применить любую операцию YΔY-сведения^[3].

Почти планарные графы

Лестница Мёбиуса с 16 вершинами, пример почти планарного графа.

Если граф является верхушечным, не обязательно у него единственная верхушка. Например, в минорно минимальных непланарных графах K₅ и K_3,3 любую вершину можно выбрать в качестве верхушки. Вагнер^[21][22] определил почти планарный граф как непланарный верхушечный граф, в котором любая вершина может служить верхушкой. Таким образом, K₅ и K_3,3 являются почти планарными графами. Он дал классификацию таких графов, разделив их на четыре семейства. Одно семейство состоит из графов, которые (подобно лестницам Мёбиуса) могут быть вложены в ленту Мёбиуса таким образом, что край ленты совпадает с гамильтоновым циклом графа. Ещё до доказательства теоремы четырёх красок он доказал, что любой почти планарный граф может быть раскрашен, не превышая четырёх цветов, за исключением графов, образованных из колеса с нечётным внешним циклом путём замены центральной вершины двумя смежными вершинами — для такого графа нужно пять красок. Кроме того, он доказал, что, за одним исключением (восьмивершинного дополнения куба), любой почти планарный граф имеет вложение в проективную плоскость.

Однако фраза «почти планарный граф» в высокой степени неоднозначна — тот же термин использовался для верхушечных графов^[20][4], графов, образованных добавлением одного ребра к планарному графу^[23], графов, образованных из планарного вложения графа заменой ограниченного числа граней «вихрями» ограниченной путевой ширины^[24], а также некоторых других менее строго определённых множеств графов.

Примечания

1. Robertson, Seymour, Thomas, 1993b.
2. Robertson, Seymour, Thomas, 1993a.
3. Truemper, 1992.
4. Eppstein, 2000.
5. Demaine, Hajiaghayi, 2004.
6. Gupta, Impagliazzo, 1991.
7. Pierce, 2014.
8. Kawarabayashi, 2009.
9. Lewis, Yannakakis, 1980.
10. Jørgensen, 1994.
11. "Jorgensen's Conjecture", Open Problem Garden, Архивировано 14 ноября 2016, Дата обращения: 13 ноября 2016 Источник  (неопр.). Дата обращения: 30 ноября 2016. Архивировано 14 ноября 2016 года..
12. Kawarabayashi, Norine, Thomas, Wollan, 2012.
13. Frick, Grohe, 2001.
14. Demaine, Hajiaghayi, 2005.
15. Demaine, Hajiaghayi, Kawarabayashi, 2009.
16. Grohe, 2003.
17. Mohar, 2001.
18. Chimani, Gutwenger, Mutzel, Wolf, 2009.
19. Cabello, Mohar, 2010.
20. Robertson, Seymour, Thomas, 1993c.
21. Wagner, 1967.
22. Wagner, 1970.
23. Archdeacon, Bonnington, 2004.
24. Abraham, Gavoille, 2006.

Литература

• Ittai Abraham, Cyril Gavoille. Proc. 25th ACM Symposium on Principles of Distributed Computing (PODC '06). — 2006. — С. 188–197. — doi:10.1145/1146381.1146411.
• Dan Archdeacon, C.P.C. Paul Bonnington. Obstructions for embedding cubic graphs on the spindle surface // Journal of Combinatorial Theory, Series B. — 2004. — Т. 91, вып. 2. — С. 229–252. — doi:10.1016/j.jctb.2004.02.001.
• Sergio Cabello, Bojan Mohar. Proc. 26th ACM Symposium on Computational Geometry (SoCG '10). — 2010. — С. 68–76. — doi:10.1145/1810959.1810972.
• Markus Chimani, Carsten Gutwenger, Petra Mutzel, Christian Wolf. Proc. 20th ACM-SIAM Symposium on Discrete Algorithms (SODA '09). — 2009. — С. 375–383.
• Erik D. Demaine, Mohammad Taghi Hajiaghayi. Diameter and treewidth in minor-closed graph families, revisited // Algorithmica. — 2004. — Т. 40, вып. 3. — С. 211–215. — doi:10.1007/s00453-004-1106-1.
• Erik D. Demaine, Mohammad Taghi Hajiaghayi. Proc. 16th ACM-SIAM Symposium on Discrete Algorithms (SODA '05). — 2005. — С. 590–601.
• Erik D. Demaine, Mohammad Taghi Hajiaghayi, Ken-ichi Kawarabayashi. Proc. 36th International Colloquium Automata, Languages and Programming (ICALP '09). — Springer-Verlag, 2009. — Т. 5555. — С. 316–327. — (Lecture Notes in Computer Science). — doi:10.1007/978-3-642-02927-1_27.
• David Eppstein. Diameter and treewidth in minor-closed graph families // Algorithmica. — 2000. — Т. 27, вып. 3. — С. 275–291. — doi:10.1007/s004530010020. — arXiv:math.CO/9907126.
• Markus Frick, Martin Grohe. Deciding first-order properties of locally tree-decomposable structures // Journal of the ACM. — 2001. — Т. 48, вып. 6. — С. 1184–1206. — doi:10.1145/504794.504798. — arXiv:cs/0004007.
• Martin Grohe. Local tree-width, excluded minors, and approximation algorithms // Combinatorica. — 2003. — Т. 23, вып. 4. — С. 613–632. — doi:10.1007/s00493-003-0037-9. — arXiv:math.CO/0001128.
• A. Gupta, R. Impagliazzo. Proc. 32nd IEEE Symposium on Foundations of Computer Science (FOCS '91). — IEEE Computer Society, 1991. — С. 802–811. — doi:10.1109/SFCS.1991.185452.
• Leif K Jørgensen. Contractions to K₈ // Journal of Graph Theory. — 1994. — Т. 18, вып. 5. — С. 431–448. — doi:10.1002/jgt.3190180502.. Как процитировано у Робертсона ((Robertson, Seymour & Thomas 1993a)).
• Ken-ichi Kawarabayashi. Proc. 50th IEEE Symposium on Foundations of Computer Science (FOCS '09). — IEEE Computer Society, 2009. — С. 639–648. — doi:10.1109/FOCS.2009.45..
• Ken-ichi Kawarabayashi, Serguei Norine, Robin Thomas, Paul Wollan. ${\displaystyle K_{6}}$ minors in large 6-connected graphs. — 2012. — arXiv:1203.2192.
• John M. Lewis, Mihalis Yannakakis. The node-deletion problem for hereditary properties is NP-complete // Journal of Computer and System Sciences. — 1980. — Т. 20, вып. 2. — С. 219–230. — doi:10.1016/0022-0000(80)90060-4.
• Bojan Mohar. Face covers and the genus problem for apex graphs // Journal of Combinatorial Theory, Series B. — 2001. — Т. 82, вып. 1. — С. 102–117. — doi:10.1006/jctb.2000.2026.
• Mike Pierce. Searching for and classifying the finite set of minor-minimal non-apex graphs. — California State University, Chico, 2014. — (Honours thesis).
• Neil Robertson, Paul Seymour, Robin Thomas. Hadwiger's conjecture for K₆-free graphs // Combinatorica. — 1993a. — Т. 13, вып. 3. — С. 279–361. — doi:10.1007/BF01202354.
• Neil Robertson, Paul Seymour, Robin Thomas. Linkless embeddings of graphs in 3-space // Bulletin of the American Mathematical Society. — 1993b. — Т. 28, вып. 1. — С. 84–89. — doi:10.1090/S0273-0979-1993-00335-5. — arXiv:math/9301216..
• Neil Robertson, Paul Seymour, Robin Thomas. Graph Structure Theory: Proc. AMS–IMS–SIAM Joint Summer Research Conference on Graph Minors / Neil Robertson, Paul Seymour. — American Mathematical Society, 1993c. — Т. 147. — С. 125–136. — (Contemporary Mathematics).
• Klaus Truemper. Matroid Decomposition. — Academic Press, 1992. — С. 100–101.
• Klaus Wagner. Fastplättbare Graphen (нем.) // Journal of Combinatorial Theory. — 1967. — Т. 3, вып. 4. — С. 326–365. — doi:10.1016/S0021-9800(67)80103-0.
• Klaus Wagner. Zum basisproblem der nicht in die projektive ebene einbettbaren graphen, I (нем.) // Journal of Combinatorial Theory. — 1970. — Т. 9, вып. 1. — С. 27–43. — doi:10.1016/S0021-9800(70)80052-7.