Перегляд вихідного коду сторінки Верхівковий граф

[[Файл:Apex_graph.svg|міні| Верхівковий граф. Підграф, утворений видаленням червоної вершини, є [[Планарний граф|планарним]].]]
В [[Теорія графів|теорії графів]] '''верхівковий граф'''&nbsp;— це граф, який можна зробити [[Планарний граф|планарним]] видаленням однієї вершини. Видалену вершину називають верхівкою графа. Зауважимо, що верхівка може бути не одна. Наприклад, у мінімальному непланарному графі ''K''<sub>5</sub> або ''K''<sub>3,3</sub> кожна вершина є верхівкою. Верхівкові графи включають початково планарні графи, в яких кожна вершина є верхівкою. Нуль-граф вважається також верхівковим, хоча в ньому немає вершин для видалення.

Верхівкові графи [[Замикання (математика)|замкнуті]] відносно операції утворення [[Мінор графа|мінорів]] і грають важливу роль у деяких інших аспектах теорії мінорів графів, таких як [[Незачеплене вкладення графа|незачеплене вкладення]]{{Sfn|Robertson, Seymour, Thomas|1993b}}, [[гіпотеза Хадвігера]]{{Sfn|Robertson, Seymour, Thomas|1993a}}, YΔY-звідні графи{{Sfn|Truemper|1992}} і зв'язок між [[Деревна ширина (теорія графів)|деревною шириною]] і [[Відстань (теорія графів)|діаметром графа]]{{Sfn|Eppstein|2000}}{{Sfn|Demaine, Hajiaghayi|2004}}.

== Опис і розпізнавання ==
Верхівкові графи [[Замикання (математика)|замкнуті]] відносно операції утворення [[Мінор графа|мінорів]]&nbsp;— стягування будь-якого ребра або видалення вершини або ребра призводить до іншого верхівкового графа. Дійсно, якщо граф ''G'' є верхівковим з верхівкою ''v'', то стягування або видалення, яке не зачіпає вершини ''v'', зберігає планарність решти графа (без вершини ''v''). Це правильно і при видаленні будь-якого ребра, інцидентного ''v''. Якщо стягується ребро, інцидентне ''v'', ефект еквівалентний видаленню протилежного кінця ребра. Якщо ж видаляється сама вершина ''v'', будь-яку іншу вершину можна вважати верхівкою{{Sfn|Gupta, Impagliazzo|1991}}.

Оскільки верхівкові графи замкнуті за операцією утворення мінорів, за [[Теорема Робертсона — Сеймура|теоремою Робертсона&nbsp;— Сеймура]] вони мають [[Характеризація забороненими графами|характеризацію забороненими графами]]. Існує лише скінченне число графів, які не є верхівковими графами і не містять як мінор інший граф, який не є верхівковим. Ці графи є ''забороненими мінорами'' для властивості «верхівковий граф». Будь-який інший граф ''G'' є верхівковим [[тоді й лише тоді]], коли жоден із заборонених мінорів не є мінором графа ''G''. Заборонені мінори включають сім графів з [[Петерсонове сімейство|петерсенового сімейства]], три незв'язних графи, утворених з об'єднань ''K''<sub>5</sub> і ''K''<sub>3,3</sub>, що не перетинаються, і багато інших графів. Повний список всіх заборонених мінорів залишається незавершеним{{Sfn|Gupta, Impagliazzo|1991}}{{Sfn|Pierce|2014}}.

Попри те, що повний список заборонених мінорів не відомий, є можливість за [[Часова складність алгоритму|лінійний час]] перевірити, чи є даний граф верхівковим, і якщо він такий, знайти верхівку графа. Загальніше, для будь-якої фіксованої константи ''k'' можна за лінійний час розпізнати '''''k''-верхівкові графи''' (графи, в яких видалення акуратно вибраної множини, що містить не більше ''k'' вершин, приводить до планарного графа{{Sfn|Kawarabayashi|2009}}). Однак, якщо ''k'' не фіксовано, задача стає [[NP-повна задача|NP-повною]]{{Sfn|Lewis, Yannakakis|1980}}.

== Хроматичне число ==
{{Докладніше|Хроматичне число}}
Будь-який верхівковий граф має [[Розфарбовування графів|хроматичне число]], яке не перевищує п'яти&nbsp;— планарний граф без верхівки вимагає не більше чотирьох кольорів за [[Проблема чотирьох фарб|теоремою про чотири фарби]], а для верхівки достатньо одного додаткового кольору. Робертсон, Сеймур і Томас{{Sfn|Robertson, Seymour, Thomas|1993a}} використовували цей факт для доведення випадку ''k''&nbsp;=&nbsp;6 [[Гіпотеза Хадвігера|гіпотези Хадвігера]], твердження, що будь-6-хроматичний граф має [[повний граф]] ''K''<sub>6</sub> як мінор&nbsp;— вони показали, що будь-який мінімальний контрприклад гіпотезі має бути верхівковим графом, але верхівкових 6-хроматичних графів немає, так що такого контрприкладу не існує.{{Нерозв'язано|математики|Чи будь-який 6-вершинно-звязний граф без мінорів <math>K_6</math> - верхівковий?}}Йоргенсен{{Sfn|Jørgensen|1994}} висловив гіпотезу, що будь-який [[K-вершинно-зв'язний граф|6-вершинно-зв'язний]] граф, що не має мінорів {{Math|''K''<sub>6</sub>}}, повинен бути верхівковим. Якби це довели, результат Робертсона&nbsp;— Сеймура&nbsp;— Томаса для гіпотези Хадвігера став би прямим наслідком{{Sfn|Robertson, Seymour, Thomas|1993a}}. Гіпотезу Йоргенсена поки не доведено<ref>{{Citation|url=http://www.openproblemgarden.org/op/jorgensens_conjecture|title=Jorgensen's Conjecture|work=Open Problem Garden|access-date=2016-11-13}}.</ref>. Однак якщо гіпотеза хибна, вона має лише скінченне число контрприкладів{{Sfn|Kawarabayashi, Norine, Thomas, Wollan|2012}}.

== Локальна деревна ширина ==
{{Докладніше|Деревна ширина (теорія графів)}}
Родина графів ''F'' має ''обмежену локальну деревну ширину'', якщо графи з ''F'' підпорядковані функціональній залежності між [[Відстань (теорія графів)|діаметром]] і [[Деревна ширина (теорія графів)|деревною шириною]]&nbsp;— існує функція ƒ, така, що деревна ширина графа з ''F'' з діаметром ''d'' не перевершує ƒ(''d''). Верхівкові графи не мають обмеженої локальної деревної ширини&nbsp;— граф, утворений з'єднанням верхівки з кожною вершиною ''n''&nbsp;×&nbsp;''n'' [[Решітка (теорія графів)|ґратки]] має деревну ширину ''n'' і діаметр 2, так що деревна ширина не обмежена деякою функцією від діаметра цих графів. Проте верхівкові графи тісно пов'язані з графами з обмеженою локальною деревною шириною&nbsp;— замкнуті за мінорами родини графів ''F'', що мають обмежену локальну деревну ширину, є точно сімействами, одним із заборонених мінорів яких є який-небудь верхівковий граф{{Sfn|Eppstein|2000}}{{Sfn|Demaine, Hajiaghayi|2004}}. Замкнуті за мінорами родини графів, що мають верхівковий граф як мінор, відомі як ''вільні від верхівкового мінора''. Згідно з цією термінологією зв'язок між верхівковими графами та локальною деревною шириною можна переформулювати так: сімейства графів, вільних від верхівкових мінорів, збігаються з сімействами замкнутих за мінорами графів з обмеженою локальною деревною шириною.

Концепція обмеженої локальної деревної ширини утворює базис теорії {{Не перекладено|Двовимірність|двовимірності|en|bidimensionality}} і дозволяє розв'язувати багато алгоритмічних задач на вільних від верхівкових мінорів графах точно за алгоритмом поліноміального часу, або {{Не перекладено|Фіксовано-параметрична розв'язність|фіксовано-параметрично розв'язним|en|fixed-parameter tractability}} алгоритмом, або задачу можна наблизити за допомогою [[схема наближення до поліноміального часу|схеми наближення до поліноміального часу]]{{Sfn|Eppstein|2000}}{{Sfn|Frick, Grohe|2001}}{{Sfn|Demaine, Hajiaghayi|2005}}. Для вільних від верхівкових мінорів сімейств графів виконується посилена версія [[Структурна теорема графів|структурної теореми графів]], що приводить до додаткових [[Апроксимаційний алгоритм|апроксимаційних алгоритмів]] для [[розфарбовування графів]] і для [[Задача комівояжера|задачі комівояжера]]{{Sfn|Demaine, Hajiaghayi, Kawarabayashi|2009}}. Проте деякі з цих результатів можна поширити на довільні замкнуті за мінорами сімейства графів використавши структурні теореми на пов'язані з сімействами вільні від верхівкових мінорів графи{{Sfn|Grohe|2003}}.

== Вкладення ==
Якщо граф ''G'' є верхівковим графом з верхівкою ''v'' і <math>\tau</math> дорівнює мінімальному числу граней, необхідних для покриття всіх сусідів верхівки ''v'' за планарного вкладення ''G''\''{v},'' то ''G'' можна вкласти у двовимірну поверхню [[Рід (математика)|роду]] <math>\tau - 1</math> додаванням такого числа мостів до планарного вкладення, з'єднавши тим самим усі грані, з якими верхівка ''v'' повинна бути з'єднана. Наприклад, додавання однієї вершини до [[Зовніпланарний граф|зовніпланарного графа]] (графа з <math>\tau = 1</math>) дає планарний граф. Якщо граф ''G''\''{v}'' 3-зв'язний, його межа не відрізняється від оптимальної більше ніж на постійний множник&nbsp;— будь-яке вкладення ''G'' в поверхню вимагає роду щонайменше <math>\tau /160</math>. Однак задача визначення оптимального роду для поверхні вкладення для верхівкових графів є [[Клас складності NP|NP-складною задачею]]{{Sfn|Mohar|2001}}.

При використанні [[SPQR-дерево|SPQR-дерев]] для кодування можливих вкладень планарної частини верхівкового графа, можна обчислити за поліноміальний час [[Візуалізація графів|укладення]] графа на площину, в якому перетини викликані тільки ребрами, що виходять з верхівки, і загальне число перетинів мінімальне{{Sfn|Chimani, Gutwenger, Mutzel, Wolf|2009}}. Якщо дозволено довільні перетини, задача мінімізації числа перетинів стає NP-складною задачею навіть в особливому випадку верхівкових графів, утворених додаванням одного ребра у планарний граф{{Sfn|Cabello, Mohar|2010}}.

Верхівкові графи [[Незачеплене вкладення графа|вклада́ні без зачеплення]] у тривимірний простір&nbsp;— їх можна вкласти так, що будь-який цикл у графі є межею диска, якого не перетинає будь-яка інша частина графа{{Sfn|Robertson, Seymour, Thomas|1993c}}. Малюнок такого типу можна отримати, намалювавши планарну частину графа на площині, помістивши верхівку графа над площиною, і з'єднавши її з сусідами відрізками. Вкладанні без зачеплень графи утворюють замкнуте за мінорами сімейство з сімома графами з [[Петерсонове сімейство|петерсенового сімейства]] як мінімальними забороненими мінорами{{Sfn|Robertson, Seymour, Thomas|1993b}}. Таким чином, ці графи є забороненими мінорами і для верхівкових графів. Існують, однак, вкладанні без зачеплення графи, які не є верхівковими.

== YΔY-звідність ==
[[Файл:Apex_rhombic_dodecahedron.svg|міні|Приклад Робертсона YΔY-незвідного верхівкового графа.]]
Зв'язний граф є YΔY-звідним, якщо його можна звести до одиничної вершини послідовністю кроків, кожен з яких є [[Перетворення трикутника-зірка|Δ-Y або Y-Δ перетворенням]], видаленням петлі або кратних ребер, видаленням вершини з одним сусідом і заміною вершини степеня два і двох суміжних ребер одним ребром{{Sfn|Truemper|1992}}.

Подібно до верхівкових графів і вкладанних без зачеплення графів YΔY-звідні графи замкнуті відносно операції утворення мінорів. Подібно до вкладанних без зачеплення графів YΔY-звідні графи мають мінімальними забороненими мінорами сім графів з [[Петерсонове сімейство|петерсенового сімейства]], звідки виникає питання, чи не є тільки ці графи забороненими мінорами і чи не збігаються сімейства YΔY-звідних графів і вкладанних без зачеплення графів. Ніл Робертсон, однак, навів приклад верхівкового графа, що не є YΔY-звідним. Оскільки будь-який верхівковий граф вкладанний без зачеплення, це показує, що існують вкладанні без зачеплення графи, які не є YΔY-звідними, а тому існують додаткові заборонені мінори для YΔY-звідних графів{{Sfn|Truemper|1992}}.

Верхівковий граф Робертсона наведено на малюнку. Його можна отримати з'єднанням верхівки з усіма вершинами степеня три [[Ромбододекаедр|ромбододекаедра]] або злиттям двох протилежних вершин [[Граф гіперкуба|графа чотиривимірного гіперкуба]]. Оскільки граф ромбододекаедра планарний, граф Робертсона є верхівковим. Граф не містить [[Граф без трикутників|трикутників]] і має мінімальний [[Степінь вершини (теорія графів)|степінь]] чотири, так що до нього не можна застосувати будь-яку операцію YΔY-зведення{{Sfn|Truemper|1992}}.

== Майже планарні графи ==
[[Файл:Moebius-ladder-16.svg|міні| [[Драбина Мебіуса]] з 16 вершинами, приклад майже планарного графа.]]
Якщо граф є верхівковим, не обов'язково у нього єдина верхівка. Наприклад, в мінорно мінімальних непланарних графах ''K''<sub>5</sub> і ''K''<sub>3,3</sub> верхівкою можна вибрати будь-яку вершину. Вагнер{{Sfn|Wagner|1967}}{{Sfn|Wagner|1970}} визначив '''майже планарний граф''' як непланарний верхівковий граф, у якому кожна вершина може служити верхівкою. Таким чином, ''K''<sub>5</sub> і ''K''<sub>3,3</sub> є майже планарними графами. Він дав класифікацію таких графів, розділивши їх на чотири сімейства. Одне сімейство складається з графів, які (подібно [[Драбина Мебіуса|драбини Мебіуса]]) можна вкласти в [[Стрічка Мебіуса|стрічку Мебіуса]] таким чином, що край стрічки збігається з [[Гамільтонів граф|гамільтоновим циклом]] графа. Ще до доведення теореми [[Проблема чотирьох фарб|чотирьох фарб]] він довів, що будь-який майже планарний граф можна розфарбувати, не перевищивши чотирьох кольорів, за винятком графів, утворених з [[Колесо (теорія графів)|колеса]] з непарним зовнішнім циклом заміною центральної вершини двома суміжними вершинами&nbsp;— для такого графа потрібно п'ять фарб. Крім того, він довів, що, за одним винятком (восьмивершинного [[Доповнення графа|доповнення]] [[Куб|куба]]), будь-який майже планарний граф має вкладення у [[Проєктивна площина|проєктивну площину]].

Проте фраза «майже планарний граф» значною мірою неоднозначна&nbsp;— той самий термін використовувався для верхівкових графів{{Sfn|Robertson, Seymour, Thomas|1993c}}{{Sfn|Eppstein|2000}}, графів, утворених додаванням одного ребра до планарного графа{{Sfn|Archdeacon, Bonnington|2004}}, графів, утворених з планарного вкладення графа заміною обмеженого числа граней «вихорами» обмеженої [[Шляхова ширина графа|шляхової ширини]]{{Sfn|Abraham, Gavoille|2006}}, а також деяких інших менш строго визначених множин графів.

== Примітки ==
{{Reflist|2}}

== Література ==
{{Refbegin|2}}
* {{Книга
|автор = Ittai Abraham, Cyril Gavoille
|ref = Abraham, Gavoille
|doi = 10.1145/1146381.1146411
|сторінки = 188–197
|заголовок = [[Симпозіум з принципів розподілених обчислень|Proc. 25th ACM Symposium on Principles of Distributed Computing (PODC '06)]]
|рік = 2006
}}
* {{Стаття|author=Dan Archdeacon, C.P.C. Paul Bonnington|ref=Archdeacon, Bonnington|doi=10.1016/j.jctb.2004.02.001|issue=2|видання=[[Journal of Combinatorial Theory|Journal of Combinatorial Theory, Series B]]|pages=229–252|title=Obstructions for embedding cubic graphs on the spindle surface|том=91|date=2004}}
* {{Книга
|автор = Sergio Cabello, Bojan Mohar
|ref = Cabello, Mohar
|doi = 10.1145/1810959.1810972
|сторінки = 68–76
|заголовок = Proc. 26th ACM Symposium on Computational Geometry (SoCG '10)
|посилання = http://www.fmf.uni-lj.si/~mohar/Reprints/Inprint/BM10_SoCG10_Cabello_crossingNumberHard.pdf
|рік = 2010
}}
* {{Книга
|автор = Markus Chimani, Carsten Gutwenger, Petra Mutzel, Christian Wolf
|ref = Chimani, Gutwenger, Mutzel, Wolf
|сторінки = 375–383
|заголовок = Proc. 20th ACM-SIAM Symposium on Discrete Algorithms (SODA '09)
|посилання = http://portal.acm.org/citation.cfm?id=1496812
|рік = 2009
}}
* {{Стаття|author=Erik D. Demaine, Mohammad Taghi Hajiaghayi|ref=Demaine, Hajiaghayi|doi=10.1007/s00453-004-1106-1|issue=3|видання=[[Algorithmica]]|pages=211–215|title=Diameter and treewidth in minor-closed graph families, revisited|том=40|date=2004}}
* {{Книга
|автор = Erik D. Demaine, Mohammad Taghi Hajiaghayi
|ref = Demaine, Hajiaghayi
|сторінки = 590–601
|заголовок = Proc. 16th ACM-SIAM Symposium on Discrete Algorithms (SODA '05)
|посилання = http://erikdemaine.org/papers/GenApprox_SODA2005/
|рік = 2005
}}
* {{Книга
|автор = Erik D. Demaine, Mohammad Taghi Hajiaghayi, Ken-ichi Kawarabayashi
|ref = Demaine, Hajiaghayi, Kawarabayashi
|doi = 10.1007/978-3-642-02927-1_27
|сторінки = 316–327
|видавництво = Springer-Verlag
|серія = Lecture Notes in Computer Science
|заголовок = [[Міжнародний колоквіум з автоматів, мов і програмування|Proc. 36th International Colloquium Automata, Languages and Programming (ICALP '09)]]
|посилання = http://erikdemaine.org/papers/ApexMinorFree_ICALP2009/paper.pdf
|том = 5555
|рік = 2009
}}
* {{Стаття|author=David Eppstein|ref=Eppstein|doi=10.1007/s004530010020|issue=3|видання=[[Algorithmica]]|pages=275–291|title=Diameter and treewidth in minor-closed graph families|том=27|date=2000|arxiv=math.CO/9907126}}
* {{Стаття|author=Markus Frick, Martin Grohe|ref=Frick, Grohe|doi=10.1145/504794.504798|issue=6|видання=[[Journal of the ACM]]|pages=1184–1206|title=Deciding first-order properties of locally tree-decomposable structures|том=48|date=2001|arxiv=cs/0004007}}
* {{Стаття|author=Martin Grohe|ref=Grohe|doi=10.1007/s00493-003-0037-9|issue=4|видання=[[Combinatorica]]|pages=613–632|title=Local tree-width, excluded minors, and approximation algorithms|том=23|date=2003|arxiv=math.CO/0001128}}
* {{Книга
|автор = A. Gupta, R. Impagliazzo
|ref = Gupta, Impagliazzo
|doi = 10.1109/SFCS.1991.185452
|сторінки = 802–811
|видавництво = IEEE Computer Society
|заголовок = [[Симпозіум з основ комп'ютерних наук|Proc. 32nd IEEE Symposium on Foundations of Computer Science (FOCS '91)]]
|посилання = http://www.cse.ucsd.edu/users/russell/arvind.ps
|рік = 1991
}}
* {{Стаття|author=Leif K Jørgensen|ref=Jørgensen|doi=10.1002/jgt.3190180502|issue=5|видання=Journal of Graph Theory|pages=431–448|title=Contractions to ''K''<sub>8</sub>|том=18|date=1994}}. Как процитировано у Робертсона ({{Harvard citation|Robertson|Seymour|Thomas|1993a}}).
* {{Книга
|автор = Ken-ichi Kawarabayashi
|ref = Kawarabayashi
|doi = 10.1109/FOCS.2009.45
|сторінки = 639–648
|видавництво = IEEE Computer Society
|заголовок = [[Симпозіум з основ комп'ютерних наук|Proc. 50th IEEE Symposium on Foundations of Computer Science (FOCS '09)]]
|посилання = http://research.nii.ac.jp/~k_keniti/focsfinal.pdf
|рік = 2009
}}.
* {{Стаття|author=Ken-ichi Kawarabayashi, Serguei Norine, Robin Thomas, Paul Wollan|ref=Kawarabayashi, Norine, Thomas, Wollan|arxiv=1203.2192|title=<math>K_6</math> minors in large 6-connected graphs|date=2012}}
* {{Стаття|author=John M. Lewis,  [[Яннакакіс Михаліс|Mihalis Yannakakis]]|ref=Lewis,  Yannakakis|doi=10.1016/0022-0000(80)90060-4|issue=2|видання=[[Journal of Computer and System Sciences]]|pages=219–230|title=The node-deletion problem for hereditary properties is NP-complete|том=20|date=1980}}
* {{Стаття|author=Bojan Mohar|ref=Mohar|doi=10.1006/jctb.2000.2026|issue=1|видання=[[Journal of Combinatorial Theory|Journal of Combinatorial Theory, Series B]]|pages=102–117|title=Face covers and the genus problem for apex graphs|url=http://www.fmf.uni-lj.si/~mohar/Papers/ApexGenus.pdf|том=82|date=2001}}
* {{Книга
|автор = Mike Pierce
|ref = Pierce
|видавництво = California State University, Chico
|серія = Honours thesis
|заголовок = Searching for and classifying the finite set of minor-minimal non-apex graphs
|посилання = http://www.csuchico.edu/~tmattman/mpthesis.pdf
|рік = 2014
}}
* {{Стаття|author=Neil Robertson, Paul Seymour, Robin Thomas|ref=Robertson, Seymour, Thomas|doi=10.1007/BF01202354|issue=3|видання=[[Combinatorica]]|pages=279–361|title=Hadwiger's conjecture for ''K''<sub>6</sub>-free graphs|url=http://people.math.gatech.edu/~thomas/PAP/hadwiger.pdf|том=13|date=1993a}}
* {{Стаття|author=Neil Robertson, Paul Seymour, Robin Thomas|ref=Robertson, Seymour, Thomas|doi=10.1090/S0273-0979-1993-00335-5|issue=1|видання=[[Bulletin of the American Mathematical Society]]|pages=84–89|title=Linkless embeddings of graphs in 3-space|том=28|date=1993b|arxiv=math/9301216}}.
* {{Книга
|автор = Neil Robertson, Paul Seymour, Robin Thomas
|ref = Robertson, Seymour, Thomas
|відповідальний = Neil Robertson, Paul Seymour
|сторінки = 125–136
|видавництво = American Mathematical Society
|серія = Contemporary Mathematics
|заголовок = Graph Structure Theory: Proc. AMS–IMS–SIAM Joint Summer Research Conference on Graph Minors
|посилання = http://people.math.gatech.edu/~thomas/PAP/linklsurvey.pdf
|том = 147
|рік = 1993c
}}
* {{Книга
|автор = Klaus Truemper
|ref = Truemper
|сторінки = 100–101
|видавництво = Academic Press
|заголовок = Matroid Decomposition
|посилання = http://www.utdallas.edu/~klaus/Mbook/matroiddecompositionbook.pdf
|рік = 1992
|назва = 
|archivedate = 29 серпня 2017
|archiveurl = https://web.archive.org/web/20170829042050/http://www.utdallas.edu/~klaus/Mbook/matroiddecompositionbook.pdf
}}
* {{Стаття|author=Klaus Wagner|ref=Wagner|doi=10.1016/S0021-9800(67)80103-0|issue=4|видання=[[Journal of Combinatorial Theory]]|language=German|pages=326–365|title=Fastplättbare Graphen|том=3|date=1967}}
* {{Стаття|author=Klaus Wagner|ref=Wagner|doi=10.1016/S0021-9800(70)80052-7|issue=1|видання=[[Journal of Combinatorial Theory]]|language=German|pages=27–43|title=Zum basisproblem der nicht in die projektive ebene einbettbaren graphen, I|том=9|date=1970}}
{{Refend}}
[[Категорія:Теорія мінорів графів]]
[[Категорія:Види графів]]
[[Категорія:Планарні графи]]