Верхівковий граф

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

Верхівковий граф. Підграф, утворений видаленням червоної вершини, є планарним.

Верхівкові графи замкнуті відносно операції утворення (мінорів) і грають важливу роль у деяких інших аспектах теорії мінорів графів, таких як незачеплене вкладення, гіпотеза Хадвігера, YΔY-звідні графи і зв'язок між деревною шириною і діаметром графа.

Опис і розпізнавання

Верхівкові графи замкнуті відносно операції утворення (мінорів) — стягування будь-якого ребра або видалення вершини або ребра призводить до іншого верхівкового графа. Дійсно, якщо граф G є верхівковим з верхівкою v, то стягування або видалення, яке не зачіпає вершини v, зберігає планарність решти графа (без вершини v). Це правильно і при видаленні будь-якого ребра, інцидентного v. Якщо стягується ребро, інцидентне v, ефект еквівалентний видаленню протилежного кінця ребра. Якщо ж видаляється сама вершина v, будь-яку іншу вершину можна вважати верхівкою.

Оскільки верхівкові графи замкнуті за операцією утворення мінорів, за (теоремою Робертсона — Сеймура) вони мають характеризацію забороненими графами. Існує лише скінченне число графів, які не є верхівковими графами і не містять як мінор інший граф, який не є верхівковим. Ці графи є забороненими мінорами для властивості «верхівковий граф». Будь-який інший граф G є верхівковим тоді й лише тоді, коли жоден із заборонених мінорів не є мінором графа G. Заборонені мінори включають сім графів з (петерсенового сімейства), три незв'язних графи, утворених з об'єднань K₅ і K_3,3, що не перетинаються, і багато інших графів. Повний список всіх заборонених мінорів залишається незавершеним.

Попри те, що повний список заборонених мінорів не відомий, є можливість за лінійний час перевірити, чи є даний граф верхівковим, і якщо він такий, знайти верхівку графа. Загальніше, для будь-якої фіксованої константи k можна за лінійний час розпізнати k-верхівкові графи (графи, в яких видалення акуратно вибраної множини, що містить не більше k вершин, приводить до планарного графа). Однак, якщо k не фіксовано, задача стає NP-повною.

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

Докладніше: Хроматичне число

Будь-який верхівковий граф має хроматичне число, яке не перевищує п'яти — планарний граф без верхівки вимагає не більше чотирьох кольорів за теоремою про чотири фарби, а для верхівки достатньо одного додаткового кольору. Робертсон, Сеймур і Томас використовували цей факт для доведення випадку k = 6 гіпотези Хадвігера, твердження, що будь-6-хроматичний граф має повний граф K₆ як мінор — вони показали, що будь-який мінімальний контрприклад гіпотезі має бути верхівковим графом, але верхівкових 6-хроматичних графів немає, так що такого контрприкладу не існує.

Нерозв'язана проблема математики: Чи будь-який 6-вершинно-звязний граф без мінорів ${\displaystyle K_{6}}$ - верхівковий? (більше нерозв'язаних проблем математики)

Йоргенсен висловив гіпотезу, що будь-який 6-вершинно-зв'язний граф, що не має мінорів K₆, повинен бути верхівковим. Якби це довели, результат Робертсона — Сеймура — Томаса для гіпотези Хадвігера став би прямим наслідком. Гіпотезу Йоргенсена поки не доведено. Однак якщо гіпотеза хибна, вона має лише скінченне число контрприкладів.

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

Докладніше: Деревна ширина (теорія графів)

Родина графів F має обмежену локальну деревну ширину, якщо графи з F підпорядковані функціональній залежності між діаметром і деревною шириною — існує функція ƒ, така, що деревна ширина графа з F з діаметром d не перевершує ƒ(d). Верхівкові графи не мають обмеженої локальної деревної ширини — граф, утворений з'єднанням верхівки з кожною вершиною n × n ґратки має деревну ширину n і діаметр 2, так що деревна ширина не обмежена деякою функцією від діаметра цих графів. Проте верхівкові графи тісно пов'язані з графами з обмеженою локальною деревною шириною — замкнуті за мінорами родини графів F, що мають обмежену локальну деревну ширину, є точно сімействами, одним із заборонених мінорів яких є який-небудь верхівковий граф. Замкнуті за мінорами родини графів, що мають верхівковий граф як мінор, відомі як вільні від верхівкового мінора. Згідно з цією термінологією зв'язок між верхівковими графами та локальною деревною шириною можна переформулювати так: сімейства графів, вільних від верхівкових мінорів, збігаються з сімействами замкнутих за мінорами графів з обмеженою локальною деревною шириною.

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

Вкладення

Якщо граф G є верхівковим графом з верхівкою v і ${\displaystyle \tau }$ дорівнює мінімальному числу граней, необхідних для покриття всіх сусідів верхівки v за планарного вкладення G\{v}, то G можна вкласти у двовимірну поверхню роду ${\displaystyle \tau -1}$ додаванням такого числа мостів до планарного вкладення, з'єднавши тим самим усі грані, з якими верхівка v повинна бути з'єднана. Наприклад, додавання однієї вершини до зовніпланарного графа (графа з ${\displaystyle \tau =1}$) дає планарний граф. Якщо граф G\{v} 3-зв'язний, його межа не відрізняється від оптимальної більше ніж на постійний множник — будь-яке вкладення G в поверхню вимагає роду щонайменше ${\displaystyle \tau /160}$. Однак задача визначення оптимального роду для поверхні вкладення для верхівкових графів є NP-складною задачею.

При використанні для кодування можливих вкладень планарної частини верхівкового графа, можна обчислити за поліноміальний час укладення графа на площину, в якому перетини викликані тільки ребрами, що виходять з верхівки, і загальне число перетинів мінімальне. Якщо дозволено довільні перетини, задача мінімізації числа перетинів стає NP-складною задачею навіть в особливому випадку верхівкових графів, утворених додаванням одного ребра у планарний граф.

Верхівкові графи вклада́ні без зачеплення у тривимірний простір — їх можна вкласти так, що будь-який цикл у графі є межею диска, якого не перетинає будь-яка інша частина графа. Малюнок такого типу можна отримати, намалювавши планарну частину графа на площині, помістивши верхівку графа над площиною, і з'єднавши її з сусідами відрізками. Вкладанні без зачеплень графи утворюють замкнуте за мінорами сімейство з сімома графами з (петерсенового сімейства) як мінімальними забороненими мінорами. Таким чином, ці графи є забороненими мінорами і для верхівкових графів. Існують, однак, вкладанні без зачеплення графи, які не є верхівковими.

YΔY-звідність

Приклад Робертсона YΔY-незвідного верхівкового графа.

Зв'язний граф є YΔY-звідним, якщо його можна звести до одиничної вершини послідовністю кроків, кожен з яких є (Δ-Y або Y-Δ перетворенням), видаленням петлі або кратних ребер, видаленням вершини з одним сусідом і заміною вершини степеня два і двох суміжних ребер одним ребром.

Подібно до верхівкових графів і вкладанних без зачеплення графів YΔY-звідні графи замкнуті відносно операції утворення мінорів. Подібно до вкладанних без зачеплення графів YΔY-звідні графи мають мінімальними забороненими мінорами сім графів з (петерсенового сімейства), звідки виникає питання, чи не є тільки ці графи забороненими мінорами і чи не збігаються сімейства YΔY-звідних графів і вкладанних без зачеплення графів. Ніл Робертсон, однак, навів приклад верхівкового графа, що не є YΔY-звідним. Оскільки будь-який верхівковий граф вкладанний без зачеплення, це показує, що існують вкладанні без зачеплення графи, які не є YΔY-звідними, а тому існують додаткові заборонені мінори для YΔY-звідних графів.

Верхівковий граф Робертсона наведено на малюнку. Його можна отримати з'єднанням верхівки з усіма вершинами степеня три ромбододекаедра або злиттям двох протилежних вершин графа чотиривимірного гіперкуба. Оскільки граф ромбододекаедра планарний, граф Робертсона є верхівковим. Граф не містить трикутників і має мінімальний степінь чотири, так що до нього не можна застосувати будь-яку операцію YΔY-зведення.

Майже планарні графи

(Драбина Мебіуса) з 16 вершинами, приклад майже планарного графа.

Якщо граф є верхівковим, не обов'язково у нього єдина верхівка. Наприклад, в мінорно мінімальних непланарних графах K₅ і K_3,3 верхівкою можна вибрати будь-яку вершину. Вагнер визначив майже планарний граф як непланарний верхівковий граф, у якому кожна вершина може служити верхівкою. Таким чином, K₅ і K_3,3 є майже планарними графами. Він дав класифікацію таких графів, розділивши їх на чотири сімейства. Одне сімейство складається з графів, які (подібно (драбини Мебіуса)) можна вкласти в стрічку Мебіуса таким чином, що край стрічки збігається з гамільтоновим циклом графа. Ще до доведення теореми чотирьох фарб він довів, що будь-який майже планарний граф можна розфарбувати, не перевищивши чотирьох кольорів, за винятком графів, утворених з колеса з непарним зовнішнім циклом заміною центральної вершини двома суміжними вершинами — для такого графа потрібно п'ять фарб. Крім того, він довів, що, за одним винятком (восьмивершинного доповнення куба), будь-який майже планарний граф має вкладення у проєктивну площину.

Проте фраза «майже планарний граф» значною мірою неоднозначна — той самий термін використовувався для верхівкових графів, графів, утворених додаванням одного ребра до планарного графа, графів, утворених з планарного вкладення графа заміною обмеженого числа граней «вихорами» обмеженої (шляхової ширини), а також деяких інших менш строго визначених множин графів.

Примітки

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, процитовано 13 листопада 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. . — 2006. — С. 188–197. — DOI:10.1145/1146381.1146411.
• Dan Archdeacon, C.P.C. Paul Bonnington. Obstructions for embedding cubic graphs on the spindle surface // . — 2004. — Т. 91, вип. 2 (19 червня). — С. 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 // . — 2004. — Т. 40, вип. 3 (19 червня). — С. 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. . — 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 // . — 2000. — Т. 27, вип. 3 (19 червня). — С. 275–291. — arXiv:math.CO/9907126. — DOI:10.1007/s004530010020.
• Markus Frick, Martin Grohe. Deciding first-order properties of locally tree-decomposable structures // . — 2001. — Т. 48, вип. 6 (19 червня). — С. 1184–1206. — arXiv:cs/0004007. — DOI:10.1145/504794.504798.
• Martin Grohe. Local tree-width, excluded minors, and approximation algorithms // . — 2003. — Т. 23, вип. 4 (19 червня). — С. 613–632. — arXiv:math.CO/0001128. — DOI:10.1007/s00493-003-0037-9.
• A. Gupta, R. Impagliazzo. . — 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 (19 червня). — С. 431–448. — DOI:10.1002/jgt.3190180502.. Как процитировано у Робертсона ((Robertson, Seymour та Thomas, 1993a)).
• Ken-ichi Kawarabayashi. . — 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. — 19 червня. — arXiv:1203.2192.
• John M. Lewis, . The node-deletion problem for hereditary properties is NP-complete // . — 1980. — Т. 20, вип. 2 (19 червня). — С. 219–230. — DOI:10.1016/0022-0000(80)90060-4.
• Bojan Mohar. Face covers and the genus problem for apex graphs // . — 2001. — Т. 82, вип. 1 (19 червня). — С. 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 // . — 1993. — Т. 13, вип. 3 (19 червня). — С. 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. — 1993. — Т. 28, вип. 1 (19 червня). — С. 84–89. — arXiv:math/9301216. — DOI:10.1090/S0273-0979-1993-00335-5..
• 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. [1] — Academic Press, 1992. — С. 100–101. з джерела 29 серпня 2017
• Klaus Wagner. Fastplättbare Graphen // . — 1967. — Т. 3, вип. 4 (19 червня). — С. 326–365. — DOI:10.1016/S0021-9800(67)80103-0.
• Klaus Wagner. Zum basisproblem der nicht in die projektive ebene einbettbaren graphen, I // . — 1970. — Т. 9, вип. 1 (19 червня). — С. 27–43. — DOI:10.1016/S0021-9800(70)80052-7.