График Халина - Halin graph

Граф Халина.

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

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

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

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

Примеры

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

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

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

Свойства

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

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

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

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

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

Вычислительная сложность

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

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

История

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

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

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

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

использованная литература

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

внешние ссылки