Граф Халіна

Граф Халіна.

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

Графи Халіна названі на честь німецького математика Рудольфа Халіна[en], який вивчав їх у 1971 році,[2] але кубічні графи Халіна — ті, в яких кожна вершина з'єднує рівно три ребра[3] — вже більш ніж століття тому досліджувались Кіркманом[en].[4] Вони є багатогранними графами, що означає, що кожен граф Халіна може бути використаний для утворення вершин та ребер опуклих багатогранників, а багатогранники, утворені з них, отримали назву багатогранників без даху (англ. roofless polyhedra) або куполів (англ. domes).

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

Трикутна призма, побудована як граф Халіна з 6-вершинного дерева.

Приклади

Колеса.

Зірка — дерево з рівно однією внутрішньою вершиною. Застосування побудови графа Халіна до зірки створює колесо, граф складений з ребер піраміди.[5] Граф трикутної призми також є графом Халіна: він може бути зображений так, що одна з його прямокутних граней — буде зовнішнім циклом, а інші ребра утворюють дерево з чотирма листками, двома внутрішніми вершинами та п'ятьма ребрами.[6]

Граф Фрухта, один з двох найменших кубічних графів, що не містить нетривіальних автоморфізмів графів, також є графом Халіна.[7]

Властивості

Будь-який граф Халіна 3-зв'язний, що означає, що не можна розбити граф на два графи шляхом видалення двох вершин. Він також реберно мінімально 3-зв'язний, що означає, що після видалення будь-якого ребра граф перестає бути 3-зв'язний.[1] Відповідно до теореми Штайніца, як 3-зв'язний планарний граф, граф Халіна можна представити у вигляді множини вершин і ребер опуклого багатогранника, тобто він є поліедральним графом. Отже, як і для будь якого графу багатогранника, його вкладення в площину буде єдиним з точністю до вибору грані, яка буде його зовнішньою гранню.[1]

Кожен граф Халіна є Гамільтоновим графом і будь-яке ребро належить циклу Гамільтона. Більш того, кожен граф Халіна залишається Гамільтоновим після видалення будь-якої вершини.[8] Оскільки будь-яке дерево без вершин ступеня 2 містить два листи зі спільним батьком, будь-який граф Халіна містить трикутник. Зокрема, граф Халіна не може бути ні графом без трикутників, ні двочастковим графом.[9]

Граф Халіна без циклу довжини 8. Подібна побудова дозволяє уникнути циклів заданої парної довжини.[10]

Більш строго, кожен граф Халіна є майже панциклічним, в тому сенсі, що він має цикли всіх довжин від 3 до n з можливим винятком одного циклу парної довжини. Більш того, будь-який граф Халіна залишається майже панциклічним після стягування одного ребра, і будь-який граф Халіна без внутрішніх вершин степеня три є панциклічним.[11]

Інцидентне хроматичне число[en] графу Халіна з максимальним степенем Δ(G) більшим ніж чотири буде Δ(G) + 1.[12] Це число кольорів потрібне для розфарбування всіх пар (v,e), де v — вершина графу, а e — ребро інцидентне v, при певних обмеженях на фарбування. Пари які мають спільну вершину або ребро не можуть бути однакового кольору. Додатково, пара (v,e) не може мати колір однаковий з парою, у якої один кінець належить e. Для графів Халіна з Δ(G) = 3 або 4, інцидентне хроматичне число може бути 5 або 6 відповідно.[13]

Обчислювальна складність

За лінійний час можливо перевірити чи буде заданий n-вершинний граф графом Халіна, якщо шукати його планарне вкладення, і, якщо воно існує, то перевірити, чи знайдеться грань з щонайменше n/2 + 1 вершиною, кожна з яких буде степені три. Якщо так, то може бути не більше чотирьох таких граней, і можна перевірити за лінійний час для кожної з них, чи буде решта графу утворювати дерево з вершинами цієї грані у якості листків. Якщо таких граней немає, то граф не буде графом Халіна.[14] Альтернативно, граф з n вершинами та m ребрами буде графом Халіна тоді, і тільки тоді, коли він планарний, 3-зв'язний і має грань у якої число вершин дорівнює цикломатичному числу графа m − n + 1. Все з цього можна перевірити за лінійний час.[15] Інші методи перевірки, які виконуються за лінійний час, або використовують теорему Курселя або переписування графу[en], для жодного з них не потрібно з'ясовувати чи існує плоске вкладання графу.[16]

Будь-який граф Халіна має ширину дерева три.[17] Тому багато задач оптимізації, які є NP-повними для довільних графів, наприклад, така як пошук максимальної незалежної множини, для графів Халіна можна розв'язати за лінійний час при використанні динамічного програмування[18] або при використанні теореми Курселя або у деяких випадках (таких, як побудова Гамільтонова циклу) прямими алгоритмами.[16] Однак, задача пошуку найбільшого підграфу Халіна у довільному графі є NP-складною, бо потрібно перевірити, чи існує підграф Халіна, який включає всі вершини заданого графа, або перевірити, чи даний граф є підграфом більшого графу Халіна.[19]

Історія

В 1971 році Халін ввів ці графи як клас мінімальних 3-вершинних зв'язних графів: для кожного ребра графу, видалення цього ребра зменшує зв'язність графу.[2] Ці графи набули значущості, коли стало зрозуміло, що багато алгоритмічних задач, які неможливо обчислити для довільних планарних графів, можна ефективно розв'язати для них.[8][15] Цей факт пізніше був пояснений як наслідок незначної ширини їх дерева та алгоритмічними мета-теоремами, такими як теорема Курселя, які забезпечують ефективне роз'язання таких задач на будь-якому графі з незначною шириною дерева.[17][18]

До роботи Халіна по цім графам, задачи перерахування графів щодо кубічних (або 3-регулярних) графів Халіна досліджувались у 1856 році Томасом Кіркманом[en][4] і в 1965 році Гансом Радмахером[en].[20] Радемахер називав ці графи побудованими на багатокутнику. Він визначав їх як кубічний поліедральний граф з f гранями, з яких одна має f − 1 ребро. Графи, які підходять під це визначення, саме і є кубічними графами Халіна.

Натхненні тим, що як графи Халіна, так і 4-вершинно-зв'язні планарні графи містять гамільтонові цикли, Lovász та Plummer, (1974) припустили, що кожен 4-вершинно-зв'язний планарний граф містить з'єднуючий підграф Халіна; тут «з'єднуючий» (англ. spanning) означає, що підграф містить усі вершини більшого графу. Гіпотеза Lovász–Plummer залишалась не розв'язаною до 2015 роу, поки не було знайдено спосіб побудови нескінченної кількості контрприкладів.[21]

Інколи графи Халіна називають «огороженими деревами» (англ. skirted trees)[10] або «полієдрами без даху» (англ. roofless polyhedra).[8] Проте такі назви неоднозначні. Деякі автори використовують назву «огорожені дерева» для планарних графів утворених з дерев, листя яких об'єднано у цикл, без вимоги, щоб внутрішні вершими були степені три або більше.[22] Назви на кшталт «побудовані на багатокутнику» або «полієдри без даху» можуть вказувати на кубічні графи Халіна.[23] Опуклі полієдри, чиї графи є графами Халіна інколи називають «куполами» (англ. domes).[24]

Примітки

  1. ↑ а б в Encyclopaedia of Mathematics, first Supplementary volume, 1988, ISBN 0-7923-4709-9, p. 281, article «Halin Graph» [Архівовано 11 січня 2014 у Wayback Machine.], and references therein.
  2. ↑ а б Halin, R. (1971), Studies on minimally n-connected graphs, Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969), London: Academic Press, с. 129—136, MR 0278980.
  3. ↑ тобто, степінь вершини буде 3
  4. ↑ а б Kirkman, Th. P. (1856), On the enumeration of x-edra having triedral summits and an (x − 1)-gonal base, Philosophical Transactions of the Royal Society of London: 399—411, doi:10.1098/rstl.1856.0018, JSTOR 108592.
  5. ↑ Cornuéjols, Naddef та Pulleyblank, (1983): «If T is a star, i.e., a single node v joined to n other nodes, then H is called a wheel and is the simplest type of Halin graph.»
  6. ↑ See Sysło та Proskurowski, (1983), Prop. 4.3, p. 254, which identifies the triangular prism as the unique graph with exactly three cycles that can be the outer cycle of a realization as a Halin graph.
  7. ↑ Weisstein, Eric W. Halin Graph(англ.) на сайті Wolfram MathWorld.
  8. ↑ а б в Cornuéjols, G.; Naddef, D.; Pulleyblank, W. R. (1983), Halin graphs and the travelling salesman problem, Mathematical Programming, 26 (3): 287—294, doi:10.1007/BF02591867.
  9. ↑ See the proof of Theorem 10 in Wang, Weifan; Bu, Yuehua; Montassier, Mickaël; Raspaud, André (2012), On backbone coloring of graphs, Journal of Combinatorial Optimization, 23 (1): 79—93, doi:10.1007/s10878-010-9342-6, MR 2875236: «Since G contains a 3-cycle consisting of one inner vertex and two outer vertices, G is not a bipartite graph.»
  10. ↑ а б Malkevitch, Joseph (1978), Cycle lengths in polytopal graphs, Theory and applications of graphs (Proc. Internat. Conf., Western Mich. Univ., Kalamazoo, Mich., 1976), Berlin: Springer, 642: 364—370, doi:10.1007/BFb0070393, MR 0491287
  11. ↑ Skowrońska, Mirosława (1985), The pancyclicity of Halin graphs and their exterior contractions, у Alspach, Brian R.; Godsil, Christopher D. (ред.), Cycles in Graphs, Annals of Discrete Mathematics, т. 27, Elsevier Science Publishers B.V., с. 179—194.
  12. ↑ Wang, Shu-Dong; Chen, Dong-Ling; Pang, Shan-Chen (2002), The incidence coloring number of Halin graphs and outerplanar graphs, Discrete Mathematics, 256 (1-2): 397—405, doi:10.1016/S0012-365X(01)00302-8, MR 1927561.
  13. ↑ Shiu, W. C.; Sun, P. K. (2008), Invalid proofs on incidence coloring, Discrete Mathematics, 308 (24): 6575—6580, doi:10.1016/j.disc.2007.11.030, MR 2466963.
  14. ↑ Fomin, Fedor V.; Thilikos, Dimitrios M. (2006), A 3-approximation for the pathwidth of Halin graphs, Journal of Discrete Algorithms, 4 (4): 499—510, doi:10.1016/j.jda.2005.06.004, MR 2577677.
  15. ↑ а б Sysło, Maciej M.; Proskurowski, Andrzej (1983), On Halin graphs, Graph Theory: Proceedings of a Conference held in Lagów, Poland, February 10–13, 1981, Lecture Notes in Mathematics, т. 1018, Springer-Verlag, с. 248—256, doi:10.1007/BFb0071635.
  16. ↑ а б Eppstein, David (2016), Simple recognition of Halin graphs and their generalizations, Journal of Graph Algorithms and Applications, 20 (2): 323—346, arXiv:1502.05334, doi:10.7155/jgaa.00395.
  17. ↑ а б Bodlaender, Hans (1988), Planar graphs with bounded treewidth (PDF), Technical Report RUU-CS-88-14, Department of Computer Science, Utrecht University, архів оригіналу (PDF) за 28 липня 2004 {{citation}}: Cite має пустий невідомий параметр: |df= (довідка).
  18. ↑ а б Bodlaender, Hans (1988), Dynamic programming on graphs with bounded treewidth, Proceedings of the 15th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science, т. 317, Springer-Verlag, с. 105—118, doi:10.1007/3-540-19488-6_110, ISBN 978-3540194880.
  19. ↑ Horton, S. B.; Parker, R. Gary (1995), On Halin subgraphs and supergraphs, Discrete Applied Mathematics, 56 (1): 19—35, doi:10.1016/0166-218X(93)E0131-H, MR 1311302.
  20. ↑ Rademacher, Hans (1965), On the number of certain types of polyhedra, Illinois Journal of Mathematics, 9: 361—380, MR 0179682, архів оригіналу за 24 липня 2018, процитовано 24 липня 2018.
  21. ↑ Chen, Guantao; Enomoto, Hikoe; Ozeki, Kenta; Tsuchiya, Shoichi (2015), Plane triangulations without a spanning Halin subgraph: counterexamples to the Lovász-Plummer conjecture on Halin graphs, SIAM Journal on Discrete Mathematics, 29 (3): 1423—1426, doi:10.1137/140971610, MR 3376776.
  22. ↑ Skowrońska, M.; Sysło, M. M. (1987), Hamiltonian cycles in skirted trees, Proceedings of the International Conference on Combinatorial Analysis and its Applications (Pokrzywna, 1985), Polska Akademia Nauk, 19 (3-4): 599–610 (1988), MR 0951375
  23. ↑ Lovász, L.; Plummer, M. D. (1974), On a family of planar bicritical graphs, Combinatorics (Proc. British Combinatorial Conf., Univ. Coll. Wales, Aberystwyth, 1973), London: Cambridge Univ. Press, с. 103–107. London Math. Soc. Lecture Note Ser., No. 13, MR 0351915.
  24. ↑ Demaine, Erik D.; Demaine, Martin L.; Uehara, Ryuhei (2013), Zipper unfolding of domes and prismoids, Proceedings of the 25th Canadian Conference on Computational Geometry (CCCG 2013), Waterloo, Ontario, Canada, August 8–10, 2013, с. 43—48, архів оригіналу за 24 липня 2018, процитовано 24 липня 2018.

Посилання