Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

В теорії графів верхівковий граф це граф який можна зробити планарним видаленням однієї вершини Видалену вершину називаю

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вкладення

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

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

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

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

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

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

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

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

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

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

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

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

V teoriyi grafiv verhivkovij graf ce graf yakij mozhna zrobiti planarnim vidalennyam odniyeyi vershini Vidalenu vershinu nazivayut verhivkoyu grafa Zauvazhimo sho verhivka mozhe buti ne odna Napriklad u minimalnomu neplanarnomu grafi K5 abo K3 3 kozhna vershina ye verhivkoyu Verhivkovi grafi vklyuchayut pochatkovo planarni grafi v yakih kozhna vershina ye verhivkoyu Nul graf vvazhayetsya takozh verhivkovim hocha v nomu nemaye vershin dlya vidalennya Verhivkovij graf Pidgraf utvorenij vidalennyam chervonoyi vershini ye planarnim Verhivkovi grafi zamknuti vidnosno operaciyi utvorennya minoriv i grayut vazhlivu rol u deyakih inshih aspektah teoriyi minoriv grafiv takih yak nezacheplene vkladennya gipoteza Hadvigera YDY zvidni grafi i zv yazok mizh derevnoyu shirinoyu i diametrom grafa Opis i rozpiznavannyaVerhivkovi grafi zamknuti vidnosno operaciyi utvorennya minoriv styaguvannya bud yakogo rebra abo vidalennya vershini abo rebra prizvodit do inshogo verhivkovogo grafa Dijsno yaksho graf G ye verhivkovim z verhivkoyu v to styaguvannya abo vidalennya yake ne zachipaye vershini v zberigaye planarnist reshti grafa bez vershini v Ce pravilno i pri vidalenni bud yakogo rebra incidentnogo v Yaksho styaguyetsya rebro incidentne v efekt ekvivalentnij vidalennyu protilezhnogo kincya rebra Yaksho zh vidalyayetsya sama vershina v bud yaku inshu vershinu mozhna vvazhati verhivkoyu Oskilki verhivkovi grafi zamknuti za operaciyeyu utvorennya minoriv za teoremoyu Robertsona Sejmura voni mayut harakterizaciyu zaboronenimi grafami Isnuye lishe skinchenne chislo grafiv yaki ne ye verhivkovimi grafami i ne mistyat yak minor inshij graf yakij ne ye verhivkovim Ci grafi ye zaboronenimi minorami dlya vlastivosti verhivkovij graf Bud yakij inshij graf G ye verhivkovim todi j lishe todi koli zhoden iz zaboronenih minoriv ne ye minorom grafa G Zaboroneni minori vklyuchayut sim grafiv z petersenovogo simejstva tri nezv yaznih grafi utvorenih z ob yednan K5 i K3 3 sho ne peretinayutsya i bagato inshih grafiv Povnij spisok vsih zaboronenih minoriv zalishayetsya nezavershenim Popri te sho povnij spisok zaboronenih minoriv ne vidomij ye mozhlivist za linijnij chas pereviriti chi ye danij graf verhivkovim i yaksho vin takij znajti verhivku grafa Zagalnishe dlya bud yakoyi fiksovanoyi konstanti k mozhna za linijnij chas rozpiznati k verhivkovi grafi grafi v yakih vidalennya akuratno vibranoyi mnozhini sho mistit ne bilshe k vershin privodit do planarnogo grafa Odnak yaksho k ne fiksovano zadacha staye NP povnoyu Hromatichne chisloDokladnishe Hromatichne chislo Bud yakij verhivkovij graf maye hromatichne chislo yake ne perevishuye p yati planarnij graf bez verhivki vimagaye ne bilshe chotiroh koloriv za teoremoyu pro chotiri farbi a dlya verhivki dostatno odnogo dodatkovogo koloru Robertson Sejmur i Tomas vikoristovuvali cej fakt dlya dovedennya vipadku k 6 gipotezi Hadvigera tverdzhennya sho bud 6 hromatichnij graf maye povnij graf K6 yak minor voni pokazali sho bud yakij minimalnij kontrpriklad gipotezi maye buti verhivkovim grafom ale verhivkovih 6 hromatichnih grafiv nemaye tak sho takogo kontrprikladu ne isnuye Nerozv yazana problema matematiki Chi bud yakij 6 vershinno zvyaznij graf bez minoriv K 6 displaystyle K 6 verhivkovij bilshe nerozv yazanih problem matematiki Jorgensen visloviv gipotezu sho bud yakij 6 vershinno zv yaznij graf sho ne maye minoriv K6 povinen buti verhivkovim Yakbi ce doveli rezultat Robertsona Sejmura Tomasa dlya gipotezi Hadvigera stav bi pryamim naslidkom Gipotezu Jorgensena poki ne dovedeno Odnak yaksho gipoteza hibna vona maye lishe skinchenne chislo kontrprikladiv Lokalna derevna shirinaDokladnishe Derevna shirina teoriya grafiv Rodina grafiv F maye obmezhenu lokalnu derevnu shirinu yaksho grafi z F pidporyadkovani funkcionalnij zalezhnosti mizh diametrom i derevnoyu shirinoyu isnuye funkciya ƒ taka sho derevna shirina grafa z F z diametrom d ne perevershuye ƒ d Verhivkovi grafi ne mayut obmezhenoyi lokalnoyi derevnoyi shirini graf utvorenij z yednannyam verhivki z kozhnoyu vershinoyu n n gratki maye derevnu shirinu n i diametr 2 tak sho derevna shirina ne obmezhena deyakoyu funkciyeyu vid diametra cih grafiv Prote verhivkovi grafi tisno pov yazani z grafami z obmezhenoyu lokalnoyu derevnoyu shirinoyu zamknuti za minorami rodini grafiv F sho mayut obmezhenu lokalnu derevnu shirinu ye tochno simejstvami odnim iz zaboronenih minoriv yakih ye yakij nebud verhivkovij graf Zamknuti za minorami rodini grafiv sho mayut verhivkovij graf yak minor vidomi yak vilni vid verhivkovogo minora Zgidno z ciyeyu terminologiyeyu zv yazok mizh verhivkovimi grafami ta lokalnoyu derevnoyu shirinoyu mozhna pereformulyuvati tak simejstva grafiv vilnih vid verhivkovih minoriv zbigayutsya z simejstvami zamknutih za minorami grafiv z obmezhenoyu lokalnoyu derevnoyu shirinoyu Koncepciya obmezhenoyi lokalnoyi derevnoyi shirini utvoryuye bazis teoriyi en i dozvolyaye rozv yazuvati bagato algoritmichnih zadach na vilnih vid verhivkovih minoriv grafah tochno za algoritmom polinomialnogo chasu abo en algoritmom abo zadachu mozhna nabliziti za dopomogoyu shemi nablizhennya do polinomialnogo chasu Dlya vilnih vid verhivkovih minoriv simejstv grafiv vikonuyetsya posilena versiya strukturnoyi teoremi grafiv sho privodit do dodatkovih aproksimacijnih algoritmiv dlya rozfarbovuvannya grafiv i dlya zadachi komivoyazhera Prote deyaki z cih rezultativ mozhna poshiriti na dovilni zamknuti za minorami simejstva grafiv vikoristavshi strukturni teoremi na pov yazani z simejstvami vilni vid verhivkovih minoriv grafi VkladennyaYaksho graf G ye verhivkovim grafom z verhivkoyu v i t displaystyle tau dorivnyuye minimalnomu chislu granej neobhidnih dlya pokrittya vsih susidiv verhivki v za planarnogo vkladennya G v to G mozhna vklasti u dvovimirnu poverhnyu rodu t 1 displaystyle tau 1 dodavannyam takogo chisla mostiv do planarnogo vkladennya z yednavshi tim samim usi grani z yakimi verhivka v povinna buti z yednana Napriklad dodavannya odniyeyi vershini do zovniplanarnogo grafa grafa z t 1 displaystyle tau 1 daye planarnij graf Yaksho graf G v 3 zv yaznij jogo mezha ne vidriznyayetsya vid optimalnoyi bilshe nizh na postijnij mnozhnik bud yake vkladennya G v poverhnyu vimagaye rodu shonajmenshe t 160 displaystyle tau 160 Odnak zadacha viznachennya optimalnogo rodu dlya poverhni vkladennya dlya verhivkovih grafiv ye NP skladnoyu zadacheyu Pri vikoristanni dlya koduvannya mozhlivih vkladen planarnoyi chastini verhivkovogo grafa mozhna obchisliti za polinomialnij chas ukladennya grafa na ploshinu v yakomu peretini viklikani tilki rebrami sho vihodyat z verhivki i zagalne chislo peretiniv minimalne Yaksho dozvoleno dovilni peretini zadacha minimizaciyi chisla peretiniv staye NP skladnoyu zadacheyu navit v osoblivomu vipadku verhivkovih grafiv utvorenih dodavannyam odnogo rebra u planarnij graf Verhivkovi grafi vklada ni bez zacheplennya u trivimirnij prostir yih mozhna vklasti tak sho bud yakij cikl u grafi ye mezheyu diska yakogo ne peretinaye bud yaka insha chastina grafa Malyunok takogo tipu mozhna otrimati namalyuvavshi planarnu chastinu grafa na ploshini pomistivshi verhivku grafa nad ploshinoyu i z yednavshi yiyi z susidami vidrizkami Vkladanni bez zacheplen grafi utvoryuyut zamknute za minorami simejstvo z simoma grafami z petersenovogo simejstva yak minimalnimi zaboronenimi minorami Takim chinom ci grafi ye zaboronenimi minorami i dlya verhivkovih grafiv Isnuyut odnak vkladanni bez zacheplennya grafi yaki ne ye verhivkovimi YDY zvidnistPriklad Robertsona YDY nezvidnogo verhivkovogo grafa Zv yaznij graf ye YDY zvidnim yaksho jogo mozhna zvesti do odinichnoyi vershini poslidovnistyu krokiv kozhen z yakih ye D Y abo Y D peretvorennyam vidalennyam petli abo kratnih reber vidalennyam vershini z odnim susidom i zaminoyu vershini stepenya dva i dvoh sumizhnih reber odnim rebrom Podibno do verhivkovih grafiv i vkladannih bez zacheplennya grafiv YDY zvidni grafi zamknuti vidnosno operaciyi utvorennya minoriv Podibno do vkladannih bez zacheplennya grafiv YDY zvidni grafi mayut minimalnimi zaboronenimi minorami sim grafiv z petersenovogo simejstva zvidki vinikaye pitannya chi ne ye tilki ci grafi zaboronenimi minorami i chi ne zbigayutsya simejstva YDY zvidnih grafiv i vkladannih bez zacheplennya grafiv Nil Robertson odnak naviv priklad verhivkovogo grafa sho ne ye YDY zvidnim Oskilki bud yakij verhivkovij graf vkladannij bez zacheplennya ce pokazuye sho isnuyut vkladanni bez zacheplennya grafi yaki ne ye YDY zvidnimi a tomu isnuyut dodatkovi zaboroneni minori dlya YDY zvidnih grafiv Verhivkovij graf Robertsona navedeno na malyunku Jogo mozhna otrimati z yednannyam verhivki z usima vershinami stepenya tri rombododekaedra abo zlittyam dvoh protilezhnih vershin grafa chotirivimirnogo giperkuba Oskilki graf rombododekaedra planarnij graf Robertsona ye verhivkovim Graf ne mistit trikutnikiv i maye minimalnij stepin chotiri tak sho do nogo ne mozhna zastosuvati bud yaku operaciyu YDY zvedennya Majzhe planarni grafiDrabina Mebiusa z 16 vershinami priklad majzhe planarnogo grafa Yaksho graf ye verhivkovim ne obov yazkovo u nogo yedina verhivka Napriklad v minorno minimalnih neplanarnih grafah K5 i K3 3 verhivkoyu mozhna vibrati bud yaku vershinu Vagner viznachiv majzhe planarnij graf yak neplanarnij verhivkovij graf u yakomu kozhna vershina mozhe sluzhiti verhivkoyu Takim chinom K5 i K3 3 ye majzhe planarnimi grafami Vin dav klasifikaciyu takih grafiv rozdilivshi yih na chotiri simejstva Odne simejstvo skladayetsya z grafiv yaki podibno drabini Mebiusa mozhna vklasti v strichku Mebiusa takim chinom sho kraj strichki zbigayetsya z gamiltonovim ciklom grafa She do dovedennya teoremi chotiroh farb vin doviv sho bud yakij majzhe planarnij graf mozhna rozfarbuvati ne perevishivshi chotiroh koloriv za vinyatkom grafiv utvorenih z kolesa z neparnim zovnishnim ciklom zaminoyu centralnoyi vershini dvoma sumizhnimi vershinami dlya takogo grafa potribno p yat farb Krim togo vin doviv sho za odnim vinyatkom vosmivershinnogo dopovnennya kuba bud yakij majzhe planarnij graf maye vkladennya u proyektivnu ploshinu Prote fraza majzhe planarnij graf znachnoyu miroyu neodnoznachna toj samij termin vikoristovuvavsya dlya verhivkovih grafiv grafiv utvorenih dodavannyam odnogo rebra do planarnogo grafa grafiv utvorenih z planarnogo vkladennya grafa zaminoyu obmezhenogo chisla granej vihorami obmezhenoyi shlyahovoyi shirini a takozh deyakih inshih mensh strogo viznachenih mnozhin grafiv PrimitkiRobertson Seymour Thomas 1993b Robertson Seymour Thomas 1993a Truemper 1992 Eppstein 2000 Demaine Hajiaghayi 2004 Gupta Impagliazzo 1991 Pierce 2014 Kawarabayashi 2009 Lewis Yannakakis 1980 Jorgensen 1994 Jorgensen s Conjecture Open Problem Garden procitovano 13 listopada 2016 Kawarabayashi Norine Thomas Wollan 2012 Frick Grohe 2001 Demaine Hajiaghayi 2005 Demaine Hajiaghayi Kawarabayashi 2009 Grohe 2003 Mohar 2001 Chimani Gutwenger Mutzel Wolf 2009 Cabello Mohar 2010 Robertson Seymour Thomas 1993c Wagner 1967 Wagner 1970 Archdeacon Bonnington 2004 Abraham Gavoille 2006 LiteraturaIttai Abraham Cyril Gavoille 2006 S 188 197 DOI 10 1145 1146381 1146411 Dan Archdeacon C P C Paul Bonnington Obstructions for embedding cubic graphs on the spindle surface 2004 T 91 vip 2 19 chervnya S 229 252 DOI 10 1016 j jctb 2004 02 001 Sergio Cabello Bojan Mohar Proc 26th ACM Symposium on Computational Geometry SoCG 10 2010 S 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 S 375 383 Erik D Demaine Mohammad Taghi Hajiaghayi Diameter and treewidth in minor closed graph families revisited 2004 T 40 vip 3 19 chervnya S 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 S 590 601 Erik D Demaine Mohammad Taghi Hajiaghayi Ken ichi Kawarabayashi Springer Verlag 2009 T 5555 S 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 T 27 vip 3 19 chervnya S 275 291 arXiv math CO 9907126 DOI 10 1007 s004530010020 Markus Frick Martin Grohe Deciding first order properties of locally tree decomposable structures 2001 T 48 vip 6 19 chervnya S 1184 1206 arXiv cs 0004007 DOI 10 1145 504794 504798 Martin Grohe Local tree width excluded minors and approximation algorithms 2003 T 23 vip 4 19 chervnya S 613 632 arXiv math CO 0001128 DOI 10 1007 s00493 003 0037 9 A Gupta R Impagliazzo IEEE Computer Society 1991 S 802 811 DOI 10 1109 SFCS 1991 185452 Leif K Jorgensen Contractions to K8 Journal of Graph Theory 1994 T 18 vip 5 19 chervnya S 431 448 DOI 10 1002 jgt 3190180502 Kak procitirovano u Robertsona Robertson Seymour ta Thomas 1993a Ken ichi Kawarabayashi IEEE Computer Society 2009 S 639 648 DOI 10 1109 FOCS 2009 45 Ken ichi Kawarabayashi Serguei Norine Robin Thomas Paul Wollan K 6 displaystyle K 6 minors in large 6 connected graphs 2012 19 chervnya arXiv 1203 2192 John M Lewis The node deletion problem for hereditary properties is NP complete 1980 T 20 vip 2 19 chervnya S 219 230 DOI 10 1016 0022 0000 80 90060 4 Bojan Mohar Face covers and the genus problem for apex graphs 2001 T 82 vip 1 19 chervnya S 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 K6 free graphs 1993 T 13 vip 3 19 chervnya S 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 T 28 vip 1 19 chervnya S 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 T 147 S 125 136 Contemporary Mathematics Klaus Truemper 1 Academic Press 1992 S 100 101 z dzherela 29 serpnya 2017 Klaus Wagner Fastplattbare Graphen 1967 T 3 vip 4 19 chervnya S 326 365 DOI 10 1016 S0021 9800 67 80103 0 Klaus Wagner Zum basisproblem der nicht in die projektive ebene einbettbaren graphen I 1970 T 9 vip 1 19 chervnya S 27 43 DOI 10 1016 S0021 9800 70 80052 7

Дата публікації:
Топ