Граф Халіна
Граф Халіна у теорії графів є типом планарного графу, який будується з'єднанням листя дерева у цикл. Дерево повинне мати щонайменше чотири вершини, жодна з яких не має рівно двох сусідів; воно повинно бути намальовано в площині, так що жодні з його ребер не перетинаються (це називається плоским вкладенням), і цикл з'єднує листки за годинниковою стрілкою у цьому вкладенні. Таким чином, цикл утворює зовнішню грань графа Халіна, яка містить дерево всередині.[1]
Графи Халіна названі на честь німецького математика Рудольфа Халіна, який вивчав їх у 1971 році,[2] але кубічні графи Халіна — ті, в яких кожна вершина з'єднує рівно три ребра[3] — вже більш ніж століття тому досліджувались Кіркманом.[4] Вони є багатогранними графами, що означає, що кожен граф Халіна може бути використаний для утворення вершин та ребер опуклих багатогранників, а багатогранники, утворені з них, отримали назву багатогранників без даху (англ. roofless polyhedra) або куполів (англ. domes).
Кожен граф Халіна має цикл Гамільтона, що проходить через всі його вершини, а також цикли майже всіх довжин відповідно до кількості вершин. Графи Халіна можуть бути визначені за лінійний час. Оскільки графи Халіна мають невелику ширину дерева, багато обчислювальних задач, які є складними у випадку інших видів планарних графів, таких як пошук циклу Гамільтона, можуть бути швидко розв'язані на графах Халіна.
Приклади
Зірка — дерево з рівно однією внутрішньою вершиною. Застосування побудови графа Халіна до зірки створює колесо, граф складений з ребер піраміди.[5] Граф трикутної призми також є графом Халіна: він може бути зображений так, що одна з його прямокутних граней — буде зовнішнім циклом, а інші ребра утворюють дерево з чотирма листками, двома внутрішніми вершинами та п'ятьма ребрами.[6]
Граф Фрухта, один з двох найменших кубічних графів, що не містить нетривіальних автоморфізмів графів, також є графом Халіна.[7]
Властивості
Будь-який граф Халіна 3-зв'язний, що означає, що не можна розбити граф на два графи шляхом видалення двох вершин. Він також реберно мінімально 3-зв'язний, що означає, що після видалення будь-якого ребра граф перестає бути 3-зв'язний.[1] Відповідно до теореми Штайніца, як 3-зв'язний планарний граф, граф Халіна можна представити у вигляді множини вершин і ребер опуклого багатогранника, тобто він є поліедральним графом. Отже, як і для будь якого графу багатогранника, його вкладення в площину буде єдиним з точністю до вибору грані, яка буде його зовнішньою гранню.[1]
Кожен граф Халіна є Гамільтоновим графом і будь-яке ребро належить циклу Гамільтона. Більш того, кожен граф Халіна залишається Гамільтоновим після видалення будь-якої вершини.[8] Оскільки будь-яке дерево без вершин ступеня 2 містить два листи зі спільним батьком, будь-який граф Халіна містить трикутник. Зокрема, граф Халіна не може бути ні графом без трикутників, ні двочастковим графом.[9]
Більш строго, кожен граф Халіна є майже панциклічним, в тому сенсі, що він має цикли всіх довжин від 3 до n з можливим винятком одного циклу парної довжини. Більш того, будь-який граф Халіна залишається майже панциклічним після стягування одного ребра, і будь-який граф Халіна без внутрішніх вершин степеня три є панциклічним.[11]
Інцидентне хроматичне число графу Халіна з максимальним степенем Δ(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] Інші методи перевірки, які виконуються за лінійний час, або використовують теорему Курселя або переписування графу, для жодного з них не потрібно з'ясовувати чи існує плоске вкладання графу.[16]
Будь-який граф Халіна має ширину дерева три.[17] Тому багато задач оптимізації, які є NP-повними для довільних графів, наприклад, така як пошук максимальної незалежної множини, для графів Халіна можна розв'язати за лінійний час при використанні динамічного програмування[18] або при використанні теореми Курселя або у деяких випадках (таких, як побудова Гамільтонова циклу) прямими алгоритмами.[16] Однак, задача пошуку найбільшого підграфу Халіна у довільному графі є NP-складною, бо потрібно перевірити, чи існує підграф Халіна, який включає всі вершини заданого графа, або перевірити, чи даний граф є підграфом більшого графу Халіна.[19]
Історія
В 1971 році Халін ввів ці графи як клас мінімальних 3-вершинних зв'язних графів: для кожного ребра графу, видалення цього ребра зменшує зв'язність графу.[2] Ці графи набули значущості, коли стало зрозуміло, що багато алгоритмічних задач, які неможливо обчислити для довільних планарних графів, можна ефективно розв'язати для них.[8][15] Цей факт пізніше був пояснений як наслідок незначної ширини їх дерева та алгоритмічними мета-теоремами, такими як теорема Курселя, які забезпечують ефективне роз'язання таких задач на будь-якому графі з незначною шириною дерева.[17][18]
До роботи Халіна по цім графам, задачи перерахування графів щодо кубічних (або 3-регулярних) графів Халіна досліджувались у 1856 році Томасом Кіркманом[4] і в 1965 році Гансом Радмахером.[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]
Примітки
- Encyclopaedia of Mathematics, first Supplementary volume, 1988, ISBN 0-7923-4709-9, p. 281, article «Halin Graph», and references therein.
- 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
- 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. JSTOR 108592. doi:10.1098/rstl.1856.0018..
- 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.»
- 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.
- Weisstein, Eric W. Halin Graph(англ.) на сайті Wolfram MathWorld.
- 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..
- 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. MR 2875236. doi:10.1007/s10878-010-9342-6.: «Since G contains a 3-cycle consisting of one inner vertex and two outer vertices, G is not a bipartite graph.»
- 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. MR 0491287. doi:10.1007/BFb0070393.
- 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..
- 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. MR 1927561. doi:10.1016/S0012-365X(01)00302-8..
- Shiu, W. C.; Sun, P. K. (2008). Invalid proofs on incidence coloring. Discrete Mathematics 308 (24): 6575–6580. MR 2466963. doi:10.1016/j.disc.2007.11.030..
- Fomin, Fedor V.; Thilikos, Dimitrios M. (2006). A 3-approximation for the pathwidth of Halin graphs. Journal of Discrete Algorithms 4 (4): 499–510. MR 2577677. doi:10.1016/j.jda.2005.06.004..
- 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..
- 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..
- Bodlaender, Hans (1988). Planar graphs with bounded treewidth. Technical Report RUU-CS-88-14. Department of Computer Science, Utrecht University. Архів оригіналу за 28 липня 2004..
- 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. ISBN 978-3540194880. doi:10.1007/3-540-19488-6_110..
- Horton, S. B.; Parker, R. Gary (1995). On Halin subgraphs and supergraphs. Discrete Applied Mathematics 56 (1): 19–35. MR 1311302. doi:10.1016/0166-218X(93)E0131-H..
- Rademacher, Hans (1965). On the number of certain types of polyhedra. Illinois Journal of Mathematics 9: 361–380. MR 0179682..
- 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. MR 3376776. doi:10.1137/140971610..
- 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 951375.
- 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..
- 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..
Посилання
- Графи Халіна, Інформаційна система про включення класів графів.
- Weisstein, Eric W. Halin Graph(англ.) на сайті Wolfram MathWorld.
- 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. MR 1927561. doi:10.1016/S0012-365X(01)00302-8.