Вікіпедія

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

граф, який можна зробити планарним, вилучивши одну вершину

В теорії графів верхівковий граф — це граф, який можна зробити планарним видаленням однієї вершини. Видалену вершину називають верхівкою графа. Зауважимо, що верхівка може бути не одна. Наприклад, у мінімальному непланарному графі 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.

Література ред.

Отримано з https://uk.wikipedia.org/w/index.php?title=Верхівковий_граф&oldid=36000301