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

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

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

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

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

[ред. | ред. код]

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

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

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

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

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

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

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

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

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

[ред. | ред. код]

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

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

Вкладення

[ред. | ред. код]

Якщо граф G є верхівковим графом з верхівкою v і дорівнює мінімальному числу граней, необхідних для покриття всіх сусідів верхівки v за планарного вкладення G\{v}, то G можна вкласти у двовимірну поверхню роду додаванням такого числа мостів до планарного вкладення, з'єднавши тим самим усі грані, з якими верхівка v повинна бути з'єднана. Наприклад, додавання однієї вершини до зовніпланарного графа (графа з ) дає планарний граф. Якщо граф G\{v} 3-зв'язний, його межа не відрізняється від оптимальної більше ніж на постійний множник — будь-яке вкладення G в поверхню вимагає роду щонайменше . Однак задача визначення оптимального роду для поверхні вкладення для верхівкових графів є 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 вершинами, приклад майже планарного графа.

Якщо граф є верхівковим, не обов'язково у нього єдина верхівка. Наприклад, в мінорно мінімальних непланарних графах K5 і K3,3 верхівкою можна вибрати будь-яку вершину. Вагнер[21][22] визначив майже планарний граф як непланарний верхівковий граф, у якому кожна вершина може служити верхівкою. Таким чином, K5 і K3,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, процитовано 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.

Література

[ред. | ред. код]