Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Граф Халина.

В теории графов , А граф Халина представляет собой тип плоского графа , построенный путем соединения листьев дерева в цикл. В дереве должно быть не менее четырех вершин, ни одна из которых не имеет ровно двух соседей; он должен быть нарисован в плоскости так, чтобы ни одно из его ребер не пересекалось (это называется планарным вложением ), а цикл соединяет листы в их порядке по часовой стрелке в этом вложении. Таким образом, цикл образует внешнюю грань графа Халина с деревом внутри него. [1]

Халин графы названы в честь немецкого математика Рудольфа Halin , который изучал их в 1971 г. [2] В кубических Халин графики - те , в которых каждая вершина прикосновений ровно три ребра - уже изученные в течение столетия ранее Kirkman . [3] Графы Халина - это многогранные графы , что означает, что любой граф Халина может использоваться для образования вершин и ребер выпуклого многогранника , а многогранники, образованные из них, называются многогранниками без крыши или куполами .

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

Треугольная призма, построенная как граф Халина из дерева с шестью вершинами

Примеры [ править ]

Колесные графики

Звезда дерево ровно один внутренней вершине. Применение построения графа Халина к звезде дает граф колеса , граф (ребер) пирамиды . [4] Граф треугольной призмы также является графом Халина: его можно нарисовать так, чтобы одна из его прямоугольных граней была внешним циклом, а остальные ребра образовывали дерево с четырьмя листьями, двумя внутренними вершинами и пятью ребрами. [5]

Граф Фрухта , один из пяти наименьших кубических графов без нетривиальных графовых автоморфизмов , [6] также является графом Халина. [7]

Свойства [ править ]

Каждый граф Халина 3-связен , то есть невозможно удалить из него две вершины и разъединить оставшиеся вершины. Он является минимальным по ребрам 3-связным, что означает, что если удалить одно из его ребер, оставшийся граф больше не будет 3-связным. [1] По теореме Стейница , как 3-связный плоский граф, он может быть представлен как множество вершин и ребер выпуклого многогранника ; то есть это многогранный граф . И, как и в случае любого многогранного графа, его плоское вложение уникально до выбора того, какая из его граней должна быть внешней. [1]

Каждый граф Халина является гамильтоновым графом , и каждое ребро графа принадлежит гамильтонову циклу . Более того, любой граф Халина остается гамильтоновым после удаления любой вершины. [8] Поскольку каждое дерево без вершин степени 2 содержит два листа с одним и тем же родителем, каждый граф Халина содержит треугольник. В частности, граф Халина не может быть графом без треугольников или двудольным графом . [9]

Граф Халина без 8-циклов. Подобная конструкция позволяет избежать любой длины единого четного цикла. [10]

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

Частота хроматического числа из Halin графа G с максимальной степенью Δ ( G ) больше четырех является Δ ( G ) + 1 . [12] Это количество цветов, необходимое для раскраски всех пар ( v , e ), где v - вершина графа, а e - ребро, инцидентное v , подчиняющееся определенным ограничениям на раскраску. Пары с общей вершиной или с общим ребром не могут иметь одинаковый цвет. Кроме того, пара ( v , e ) не может иметь тот же цвет, что и другая пара, которая использует другую конечную точкуе . Для графиков Халина с Δ ( G ) = 3 или 4 хроматическое число инцидентности может достигать 5 или 6 соответственно. [13]

Вычислительная сложность [ править ]

Можно проверить, является ли данный граф с n вершинами графом Халина за линейное время , найдя планарное вложение графа (если оно существует), а затем проверив, существует ли грань, имеющая не менее n / 2 + 1 вершина, все степени три. Если это так, то таких граней может быть не более четырех, и можно проверить за линейное время для каждой из них, образует ли остальная часть графа дерево с вершинами этой грани в качестве его листьев. С другой стороны, если такой грани не существует, то граф не халинский. [14] Как вариант, граф с n вершинами и mребра являются халиновыми тогда и только тогда, когда они плоские, 3-связные и имеют грань, число вершин которой равно рангу схемы m - n + 1 графа, и все они могут быть проверены за линейное время. [15] Другие методы распознавания графов Халина в линейное время включают применение теоремы Курселя или метод, основанный на переписывании графов , ни один из которых не полагается на знание плоского вложения графа. [16]

Каждый граф Халина имеет ширину дерева = 3. [17] Следовательно, многие задачи оптимизации графов, которые являются NP-полными для произвольных плоских графов, такие как поиск максимального независимого набора , могут быть решены за линейное время на графах Халина с использованием динамического программирования [18] или теорема Курселя, или в некоторых случаях (например, построение гамильтоновых циклов ) прямыми алгоритмами. [16] Однако он NP-полныйнайти самый большой подграф Халина данного графа, проверить, существует ли подграф Халина, который включает в себя все вершины данного графа, или проверить, является ли данный граф подграфом большего графа Халина. [19]

История [ править ]

В 1971 году Халин представил графы Халина как класс графов с минимальной 3-вершинной связью: для каждого ребра в графе удаление этого ребра снижает связность графа. [2] Эти графы приобрели значение с открытием того, что многие алгоритмические проблемы, которые были вычислительно невыполнимы для произвольных плоских графов, могут быть эффективно решены на них. [8] [15] Этот факт позже был объяснен как следствие их малой ширины дерева и алгоритмических мета-теорем, таких как теорема Курселя, которые обеспечивают эффективные решения этих проблем на любом графе с малой шириной дерева. [17] [18]

До работы Халина над этими графами проблемы перечисления графов, касающиеся кубических (или 3-регулярных ) графов Халина, изучались в 1856 году Томасом Киркманом [3] и в 1965 году Хансом Радемахером . [20] Радемахер называет эти графы многогранниками на основе . Он определяет их как кубические многогранные графы с f гранями, в которых одна из граней имеет f - 1 сторону. Графы, которые соответствуют этому определению, - это в точности кубические графы Халина.

Вдохновленные тем фактом, что как графы Халина, так и планарные графы с 4-вершинной связью содержат гамильтоновы циклы, Ловас и Пламмер (1974) предположили, что каждый 4-связный плоский граф содержит остовный подграф Халина; здесь «остов» означает, что подграф включает в себя все вершины большего графа. Гипотеза Ловаса – Пламмера оставалась открытой до 2015 г., когда была опубликована конструкция для бесконечного числа контрпримеров. [21]

Графы Халина иногда также называют деревьями с краями [10] или многогранниками без крыш . [8] Однако эти названия неоднозначны. Некоторые авторы используют название «огибающие деревья» для обозначения плоских графов, образованных из деревьев путем соединения листьев в цикл, но не требуя, чтобы внутренние вершины дерева имели степень три или более. [22] И, как и «многогранники на основе», название «многогранники без крыши» также может относиться к кубическим графам Халина. [23] выпуклые многогранники , чьи графы Халины графы называют также купола . [24]

Ссылки [ править ]

  1. ^ a b c Энциклопедия математики , первый дополнительный том, 1988, ISBN  0-7923-4709-9 , стр. 281, статья «График Халина» и ссылки в ней.
  2. ^ a b Халин, Р. (1971), "Исследования минимально n -связных графов", Комбинаторная математика и ее приложения (Proc. Conf., Oxford, 1969) , Лондон: Academic Press, стр. 129–136, MR 0278980  CS1 maint: обескураженный параметр ( ссылка ).
  3. ^ a b Киркман, Th. П. (1856), «О перечислении x- эдра, имеющих тристральные вершины и ( x - 1 ) -угольное основание», Philosophical Transactions of the Royal Society of London , 146 : 399–411, doi : 10.1098 / rstl. 1856.0018 , JSTOR 108592  CS1 maint: обескураженный параметр ( ссылка ).
  4. ^ Cornuéjols, Naddef & Pulleyblank (1983) : «Если T - звезда, т. Е. Единственный узел v, соединенный с n другими узлами, то H называется колесом и является простейшим типом графа Халина».
  5. ^ См. Sysło & Proskurowski (1983) , Prop. 4.3, p. 254, который идентифицирует треугольную призму как уникальный граф с ровно тремя циклами, который может быть внешним циклом реализации как графа Халина.
  6. ^ Буссемейкер, ФК; Cobeljic, S .; Цветкович, DM; Зайдель, Дж. Дж. (1976), Компьютерное исследование кубических графов , отчет EUT, 76-WSK-01, кафедра математики и вычислительной техники, Технологический университет Эйндховена
  7. Перейти ↑ Weisstein, Eric W. , «Halin Graph» , MathWorld
  8. ^ a b c Cornuéjols, G .; Наддеф, Д .; Pulleyblank, WR (1983), "Халин графики и задача коммивояжера", Математическое программирование , 26 (3): 287-294, DOI : 10.1007 / BF02591867.
  9. ^ См. Доказательство теоремы 10 в Wang, Weifan; Бу, Юэхуа; Монтасье, Микаэль; Распо, Андре (2012), "О позвоночнике раскраске графов", журнал комбинаторной оптимизации , 23 (1): 79-93, DOI : 10.1007 / s10878-010-9342-6 , MR 2875236 : «Поскольку G содержит 3-цикл, состоящий из одной внутренней и двух внешних вершин, G не является двудольным графом».
  10. ^ a b Малькевич, Джозеф (1978), "Длины цикла в многогранных графах", Теория и приложения графов (Proc. Internat. Conf., Western Mich. Univ., Kalamazoo, Mich., 1976) , Конспекты лекций по математике, Берлин: Springer, 642 : 364–370, doi : 10.1007 / BFb0070393 , ISBN 978-3-540-08666-6, Руководство по ремонту  0491287
  11. ^ Сковроньска, Мирослава (1985), «Панцикличность графов Халина и их внешние сокращения», в Alspach, Брайан Р .; Годсил, Кристофер Д. (ред.), Циклы в графах , Анналы дискретной математики, 27 , Elsevier Science Publishers BV, стр. 179–194..
  12. ^ Ван, Шу-Донг; Чен, Дун-Линь; Панг, Шан-Чен (2002), «Число индицирующей раскраски графов Халина и внешнепланарных графов», Дискретная математика , 256 (1-2): 397-405, DOI : 10.1016 / S0012-365X (01) 00302-8 , MR 1927561 .
  13. ^ Шиу, WC; Вс, П. К. (2008), "Недействительные доказательства на заболеваемость окраски", дискретная математика , 308 (24): 6575-6580, DOI : 10.1016 / j.disc.2007.11.030 , МР 2466963 .
  14. ^ Фомин, Федор В .; Thilikos, Димитриос М. (2006), "3-приближение для pathwidth графов Halin", журнал дискретных алгоритмов , 4 (4): 499-510, DOI : 10.1016 / j.jda.2005.06.004 , МР 2577677 .
  15. ^ a b Sysło, Maciej M .; Проскуровский, Анджей (1983), «О графах Халина», Теория графов: Труды конференции, состоявшейся в Лагове, Польша, 10–13 февраля 1981 г. , Конспект лекций по математике, 1018 , Springer-Verlag, стр. 248–256, DOI : 10.1007 / BFb0071635.
  16. ^ a b Эппштейн, Дэвид (2016), «Простое распознавание графов Халина и их обобщений», Журнал алгоритмов и приложений графов , 20 (2): 323–346, arXiv : 1502.05334 , doi : 10.7155 / jgaa.00395 CS1 maint: обескураженный параметр ( ссылка ).
  17. ^ a b Бодлендер, Ханс (1988), Планарные графы с ограниченной шириной дерева (PDF) , Технический отчет RUU-CS-88-14, Департамент компьютерных наук, Утрехтский университет , заархивировано из оригинала (PDF) 28 июля 2004 г. CS1 maint: обескураженный параметр ( ссылка ).
  18. ^ Б Bodlaender Ганс (1988), «Динамическое программирование на графах с ограниченной древесная ширина», Труды 15 - й Международный коллоквиум автоматного, языки и программирование , конспекты лекций по информатике, 317 , Springer-Verlag, стр. 105-118 , DOI : 10.1007 / 3-540-19488-6_110 , ISBN 978-3540194880 CS1 maint: обескураженный параметр ( ссылка ).
  19. ^ Хортон, SB; Паркер, Р. Гэри (1995), «О подграфах и суперграфах Халина», Дискретная прикладная математика , 56 (1): 19–35, DOI : 10.1016 / 0166-218X (93) E0131-H , MR 1311302 .
  20. ^ Радемахер, Ганс (1965), "О числе некоторых типов многогранников", штат Иллинойс Журнал математики , 9 (3): 361-380, DOI : 10,1215 / IJM / 1256068140 , МР 0179682  CS1 maint: обескураженный параметр ( ссылка ).
  21. ^ Чен, Гуантао; Эномото, Хико; Озэки, Кента; Цутия, Шоичи (2015), "Плоские триангуляции без остовного подграфа Halin: контрпримеры к гипотезе Lovász-Пламмер на графах Халин", SIAM журнал по дискретной математике , 29 (3): 1423-1426, DOI : 10,1137 / 140971610 , MR 3376776 .
  22. ^ Skowrońska, M .; Сысло, М.М. (1987), "Гамильтоновы циклы в деревьях с бортиками", Труды Международной конференции по комбинаторному анализу и его приложениям (Pokrzywna, 1985), Zastos. Мат. , 19 (3–4): 599–610 (1988), MR 0951375. 
  23. ^ Ловас, Л .; Пламмер, доктор медицины (1974), "О семействе плоских бикритических графов", Комбинаторика (Proc. British Combinatorial Conf., Univ. Coll. Wales, Aberystwyth, 1973) , Лондон: Cambridge Univ. Press, стр. 103–107. Лондонская математика. Soc. Лекционная записка Сер. № 13, MR 0351915 .
  24. ^ Demaine, Эрик Д .; Демейн, Мартин Л .; Уэхара, Рюхей (2013), «Застежка-молния куполов и призмоидов», Труды 25-й Канадской конференции по вычислительной геометрии (CCCG 2013), Ватерлоо, Онтарио, Канада, 8–10 августа 2013 г. , стр. 43–48.

Внешние ссылки [ править ]

  • Графы Халина , Информационная система о включениях классов графов.