В теории графов граф Халина — это тип планарного графа , построенного путем соединения листьев дерева в цикл. Дерево должно иметь не менее четырех вершин, ни одна из которых не имеет ровно двух соседей; оно должно быть нарисовано на плоскости так , чтобы ни одно из его ребер не пересекалось (это называется планарным вложением ), а цикл соединяет листья в их порядке по часовой стрелке в этом вложении. Таким образом, цикл образует внешнюю грань графа Халина с деревом внутри него. [1]
Графы Халина названы в честь немецкого математика Рудольфа Халина , который изучал их в 1971 году. [ 2] Кубические графы Халина — те, в которых каждая вершина касается ровно трех ребер — уже были изучены более века назад Киркманом . [ 3] Графы Халина являются многогранными графами , что означает, что каждый граф Халина может быть использован для формирования вершин и ребер выпуклого многогранника , а многогранники, образованные из них, были названы многогранниками без крыши или куполами .
Каждый граф Халина имеет гамильтонов цикл через все его вершины, а также циклы почти всех длин вплоть до числа вершин графа. Графы Халина могут быть распознаны за линейное время . Поскольку графы Халина имеют низкую древовидную ширину , многие вычислительные задачи, которые сложны для других видов планарных графов, такие как поиск гамильтоновых циклов, могут быть быстро решены на графах Халина.
Звезда — это дерево с ровно одной внутренней вершиной. Применение построения графа Халина к звезде дает граф-колесо , граф (ребер) пирамиды . [4] Граф треугольной призмы также является графом Халина: его можно нарисовать так, чтобы одна из его прямоугольных граней была внешним циклом, а оставшиеся ребра образовывали дерево с четырьмя листьями, двумя внутренними вершинами и пятью ребрами. [5]
Граф Фрухта , один из пяти наименьших кубических графов без нетривиальных автоморфизмов графа , [6] также является графом Халина. [7]
Каждый граф Халина является 3-связным , что означает, что невозможно удалить из него две вершины и разъединить оставшиеся вершины. Он является рёберно-минимальным 3-связным, что означает, что если удалить любое из его ребер, оставшийся граф больше не будет 3-связным. [1] По теореме Штейница , как 3-связный планарный граф, он может быть представлен как множество вершин и рёбер выпуклого многогранника ; то есть, это многогранный граф . Многогранник, который реализует граф, может быть выбран так, что грань, содержащая все листья дерева, будет горизонтальной, а все остальные грани лежат над ней с равными наклонами. [8] Как и в случае с каждым многогранным графом, графы Халина имеют уникальное планарное вложение, с точностью до выбора того, какая из его граней должна быть внешней гранью. [1]
Каждый граф Халина является гамильтоновым графом , и каждое ребро графа принадлежит гамильтонову циклу . Более того, любой граф Халина остается гамильтоновым после удаления любой вершины. [9] Поскольку каждое дерево без вершин степени 2 содержит два листа, которые имеют одного и того же родителя, каждый граф Халина содержит треугольник. В частности, граф Халина не может быть графом без треугольников или двудольным графом . [10]
Более строго, каждый граф Халина почти панцикличен , в том смысле, что он имеет циклы всех длин от 3 до n, за исключением, возможно, одной четной длины. Более того, любой граф Халина остается почти панциклическим, если одно ребро стягивается, и каждый граф Халина без внутренних вершин степени три является панциклическим. [12]
Инцидентное хроматическое число графа Халина G с максимальной степенью Δ( G ) больше четырех равно Δ( G ) + 1 . [13] Это число цветов, необходимое для раскраски всех пар ( v , e ), где v — вершина графа, а e — ребро, инцидентное v , с соблюдением определенных ограничений на раскраску. Пары, которые имеют общую вершину или общее ребро, не могут иметь одинаковый цвет. Кроме того, пара ( v , e ) не может иметь тот же цвет, что и другая пара, которая использует другую конечную точку e . Для графов Халина с Δ( G ) = 3 или 4 инцидентное хроматическое число может достигать 5 или 6 соответственно. [14]
Можно проверить, является ли заданный n -вершинный граф графом Халина за линейное время , найдя планарное вложение графа (если оно существует), а затем проверив, существует ли грань, имеющая по крайней мере n / 2 + 1 вершин, все степени три. Если это так, то может быть не более четырех таких граней, и для каждой из них можно проверить за линейное время, образует ли остальная часть графа дерево с вершинами этой грани в качестве его листьев. С другой стороны, если такой грани не существует, то граф не является графом Халина. [15] Альтернативно, граф с n вершинами и m ребрами является графом Халина тогда и только тогда, когда он планарный, 3-связный и имеет грань, число вершин которой равно рангу цепи m − n + 1 графа, все из которых можно проверить за линейное время. [16] Другие методы распознавания графов Халина за линейное время включают применение теоремы Курселя или метод, основанный на переписывании графа , ни один из которых не полагается на знание планарного вложения графа. [17]
Каждый граф Халина имеет древовидную ширину = 3. [18] Поэтому многие задачи оптимизации графов, которые являются NP-полными для произвольных планарных графов, такие как нахождение максимального независимого множества , могут быть решены за линейное время на графах Халина с использованием динамического программирования [19] или теоремы Курселя, или в некоторых случаях (таких как построение гамильтоновых циклов ) с помощью прямых алгоритмов. [17] Однако NP-полной является задача нахождения наибольшего подграфа Халина заданного графа, проверка того, существует ли подграф Халина, включающий все вершины заданного графа, или проверка того, является ли заданный граф подграфом большего графа Халина. [20]
В 1971 году Халин представил графы Халина как класс графов с минимальным количеством вершин 3: для каждого ребра в графе удаление этого ребра уменьшает связность графа. [2] Эти графы приобрели значение с открытием того, что многие алгоритмические проблемы, которые были вычислительно невыполнимы для произвольных планарных графов, могли быть эффективно решены на них. [9] [16] Позднее этот факт был объяснен как следствие их низкой древовидной ширины и алгоритмических метатеорем, таких как теорема Курселя , которые предоставляют эффективные решения этих проблем на любом графе с низкой древовидной шириной. [18] [19]
До работы Халина над этими графами, проблемы перечисления графов, касающиеся кубических (или 3-регулярных ) графов Халина, изучались в 1856 году Томасом Киркманом [3] и в 1965 году Гансом Радемахером . Радемахер называет эти графы основанными на многогранниках . Он определяет их как кубические многогранные графы с f гранями, в которых одна из граней имеет f − 1 сторон. [21] Графы, которые соответствуют этому определению, являются в точности кубическими графами Халина. [22]
Вдохновленные тем фактом, что и графы Халина, и 4-вершинно-связанные планарные графы содержат гамильтоновы циклы, Ловас и Пламмер (1974) предположили, что каждый 4-вершинно-связанный планарный граф содержит остовной подграф Халина; здесь «остовной» означает, что подграф включает все вершины большего графа. Гипотеза Ловаса–Пламмера оставалась открытой до 2015 года, когда была опубликована конструкция для бесконечного числа контрпримеров. [23]
Графы Халина иногда также называют деревьями с юбкой [11] или многогранниками без крыши . [9] Однако эти названия неоднозначны. Некоторые авторы используют название «деревья с юбкой» для обозначения планарных графов, образованных из деревьев путем соединения листьев в цикл, но не требуя, чтобы внутренние вершины дерева имели степень три или более. [24] И как и «основанные многогранники», название «многогранники без крыши» может также относиться к кубическим графам Халина. [22] Выпуклые многогранники , графы которых являются графами Халина, также называются куполами . [25]