В теории графов графом Халина называется некоторый вид планарного графа. Граф строится из дерева, имеющего по меньшей мере четыре вершины, ни одна из которых не имеет в точности двух соседей. Дерево рисуется на плоскости так, что никакие рёбра не пересекаются. Затем добавляются рёбра, соединяющие все его листья в цикл.[1] Графы Халина названы по имени немецкого математика Рудольфа Халина[en], изучавшиего их в 1971[2], но кубические графы Халина изучались за столетие до этого английским математиком Томасом Киркманом[en].[3]
Граф Халина строится следующим образом. Пусть — вложенное в плоскость[en] дерево с четырьмя или более вершинами, такой, что никакая вершина графа не имеет степень два (то есть, никакая вершина не имеет в точности двух соседей). Граф Халина создаётся путём добавления к графу цикла, проходящего через все листья таким образом, что расширяющий путь остаётся планарным.
Звезда — это дерево с единственной внутренней вершиной. Применяя построение Халина получим колесо, граф пирамиды. Граф треугольной призмы[en] является также графом Халина — его можно нарисовать так, что одна из его прямоугольных граней будет внешним циклом, а оставшиеся рёбра образуют дерево с четырьмя листьями, двумя внутренними вершинами и пятью рёбрами.
Граф Фрухта, один из двух наименьших кубических графов с нетривиальными автоморфизмами[en], является также графом Халина.
Любой граф Халина 3-связен, что означает, что нельзя разбить граф на два графа путём удаления двух вершин. Он также рёберно минимально 3-связен, что означает, что после удаления любого ребра граф перестаёт быть 3-связен.[1] По теореме Штайница[en], будучи 3-связным плпнарным графом, граф Халина можно представить в виде множества вершин и рёбер выпуклого выпуклого многогранника. Таким образом, он является графом многогранника[en]. Но в этом случае, как и для любого графа многогранника, его вложение в плоскость единственно с точностью до выбора грани, которая будет его внешней гранью.[1]
Любой граф Халина является гамильтоновым графом и любое ребро принадлежит гамильтонову циклу. Более того, любой граф Халина остаётся гамильтоновым после удаления любой вершины.[4] Поскольку любое дерево без вершин степени 2 содержит два листа с одним родителем, любой граф Халина содержит треугольник. В частности, граф Халина не может быть ни графом без треугольников, ни двудольным графом. Более строго, любой граф Халина является почти панциклическим[en], в том смысле, что он имеет циклы всех длин от 3 до n с возможным исключением одной чётной длины. Более того, любой граф Халина остаётся почти панциклическим после стягивания одного ребра, и любой граф Халина без внутренних вершин степени три является панциклическим.[5]
Любой граф Халина имеет древесную ширину максимум три.[6] Таким образом, многие задачи оптимизации, являющиеся NP-полными для произвольных графов, такие как нахождение независимого множества, для графов Халина можно решить за линейное время при использовании динамического программирования.[7]
Слабый двойственный граф вложенного планарного графа имеет вершины, соответствующие граням планарного графа и рёбра, соответствующие смежным граням (слабый двойственный получается из двойственного путём удаления вершины, соответствующей внешней грани). Слабый двойственный граф графа Халина всегда двусвязен и внешнепланарен[en]. Это свойство можно использовать для характеризации графов Халина — вложенный в плоскость планарный граф является графом Халина с циклом через листья как внешней грани вложения тогда и только тогда, когда его слабый двойственный двусвязен и внешнепланарен.[8]
В 1971 Халин (Halin) предложил графы (получившие название графов Халина) как класс минимальных 3-вершинно-связных графов — для каждого ребра графа его удаление уменьшает связность.[2] Эти графы приобрели особое значение, когда выяснилось, что многие алгоритмические задачи, решение которых нереально для произвольных планарных графов, могут быть решены эффективно на графах Халина[4][8], что впоследствии было объяснено как следствие их малой ширины дерева.[6][7].
До работ Халина задачей перечисления[en] кубических графов Халина занимался в 1856 Томас Киркман[en][3], а в 1965 — Ганс Радемахер[en].[9] Радемахер называл эти графы основанными на многранниках. Он определил их как кубические графы многогранников[en] с f гранями, у которых одна из граней имеет f − 1 рёбер. Графы, удовлетворяющие этому определению — в точности кубические графы Халина.
Графы Халина также иногда называют многогранниками без крыши[4] но, как и название «основанные на многранниках» это название можно отнести к кубическим графам Халина.[10] Выпуклые многогранники, графами которых являются графы Халина, называют также куполами.[11]
Халина елена, халина екатерина москва, халина татьяна викторовна, халина хейтц в мире цветов.
Ночные пришельцы (фильм, 1995), Гонфалоньеры, Механотроника, Обсуждение:Мировой тур ATP Challenger 2013 (июль — декабрь).
