Граф Халіна у теорії графів є типом планарного графу, який будується з'єднанням листя дерева у цикл. Дерево повинне мати щонайменше чотири вершини, жодна з яких не має рівно двох сусідів; воно повинно бути намальовано в площині, так що жодні з його ребер не перетинаються (це називається плоским вкладенням), і цикл з'єднує листки за годинниковою стрілкою у цьому вкладенні. Таким чином, цикл утворює зовнішню грань графа Халіна, яка містить дерево всередині.Encyclopaedia of Mathematics, first Supplementary volume, 1988, , p. 281, article «Halin Graph» , and references therein.

Графи Халіна названі на честь німецького математика , який вивчав їх у 1971 році,. але кубічні графи Халіна — ті, в яких кожна вершина з'єднує рівно три ребратобто, степінь вершини буде 3 — вже більш ніж століття тому досліджувались .. Вони є багатогранними графами, що означає, що кожен граф Халіна може бути використаний для утворення вершин та ребер опуклих багатогранників, а багатогранники, утворені з них, отримали назву багатогранників без даху () або куполів ().

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

Приклади

Зірка — дерево з рівно однією внутрішньою вершиною. Застосування побудови графа Халіна до зірки створює колесо, граф складений з ребер піраміди.: «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 , 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.

Граф Фрухта, один з двох найменших кубічних графів, що не містить нетривіальних автоморфізмів графів, також є графом Халіна.

Властивості Будь-який граф Халіна 3-зв'язний, що означає, що не можна розбити граф на два графи шляхом видалення двох вершин. Він також реберно мінімально 3-зв'язний, що означає, що після видалення будь-якого ребра граф перестає бути 3-зв'язний. Відповідно до теореми Штайніца, як 3-зв'язний планарний граф, граф Халіна можна представити у вигляді множини вершин і ребер опуклого багатогранника, тобто він є поліедральним графом. Отже, як і для будь якого графу багатогранника, його вкладення в площину буде єдиним з точністю до вибору грані, яка буде його зовнішньою гранню.

Кожен граф Халіна є Гамільтоновим графом і будь-яке ребро належить циклу Гамільтона. Більш того, кожен граф Халіна залишається Гамільтоновим після видалення будь-якої вершини.. Оскільки будь-яке дерево без вершин ступеня 2 містить два листи зі спільним батьком, будь-який граф Халіна містить трикутник. Зокрема, граф Халіна не може бути ні графом без трикутників, ні двочастковим графом.See the proof of Theorem 10 in : «Since G contains a 3-cycle consisting of one inner vertex and two outer vertices, G is not a bipartite graph.»

Більш строго, кожен граф Халіна є майже панциклічним, в тому сенсі, що він має цикли всіх довжин від 3 до n з можливим винятком одного циклу парної довжини. Більш того, будь-який граф Халіна залишається майже панциклічним після стягування одного ребра, і будь-який граф Халіна без внутрішніх вершин степеня три є панциклічним..

графу Халіна з максимальним степенем більшим ніж чотири буде .. Це число кольорів потрібне для розфарбування всіх пар (v,e), де v — вершина графу, а e — ребро інцидентне v, при певних обмеженях на фарбування. Пари які мають спільну вершину або ребро не можуть бути однакового кольору. Додатково, пара (v,e) не може мати колір однаковий з парою, у якої один кінець належить e. Для графів Халіна з або , інцидентне хроматичне число може бути або відповідно..

Обчислювальна складність

За лінійний час можливо перевірити чи буде заданий -вершинний граф графом Халіна, якщо шукати його планарне вкладення, і, якщо воно існує, то перевірити, чи знайдеться грань з щонайменше вершиною, кожна з яких буде степені три. Якщо так, то може бути не більше чотирьох таких граней, і можна перевірити за лінійний час для кожної з них, чи буде решта графу утворювати дерево з вершинами цієї грані як листків. Якщо таких граней немає, то граф не буде графом Халіна.. Альтернативно, граф з вершинами та ребрами буде графом Халіна тоді, і тільки тоді, коли він планарний, 3-зв'язний і має грань у якої число вершин дорівнює цикломатичному числу графа . Все з цього можна перевірити за лінійний час.. Інші методи перевірки, які виконуються за лінійний час, або використовують теорему Курселя або , для жодного з них не потрібно з'ясовувати чи існує плоске вкладання графу..

Будь-який граф Халіна має ширину дерева три.. Тому багато задач оптимізації, які є NP-повними для довільних графів, наприклад, така як пошук максимальної незалежної множини, для графів Халіна можна розв'язати за лінійний час при використанні динамічного програмування. або при використанні теореми Курселя або у деяких випадках (таких, як побудова Гамільтонова циклу) прямими алгоритмами. Однак, задача пошуку найбільшого підграфу Халіна у довільному графі є NP-складною, бо потрібно перевірити, чи існує підграф Халіна, який включає всі вершини заданого графа, або перевірити, чи даний граф є підграфом більшого графу Халіна..

Історія

В 1971 році Халін ввів ці графи як клас мінімальних 3-вершинних зв'язних графів: для кожного ребра графу, видалення цього ребра зменшує зв'язність графу. Ці графи набули значущості, коли стало зрозуміло, що багато алгоритмічних задач, які неможливо обчислити для довільних планарних графів, можна ефективно розв'язати для них. Цей факт пізніше був пояснений як наслідок незначної ширини їх дерева та алгоритмічними мета-теоремами, такими як теорема Курселя, які забезпечують ефективне роз'язання таких задач на будь-якому графі з незначною шириною дерева.

До роботи Халіна по цім графам, задачи перерахування графів щодо кубічних (або 3-регулярних) графів Халіна досліджувались у 1856 році і в 1965 році .. Радемахер називав ці графи побудованими на багатокутнику. Він визначав їх як кубічний поліедральний граф з гранями, з яких одна має ребро. Графи, які підходять під це визначення, саме і є кубічними графами Халіна.

Натхненні тим, що як графи Халіна, так і 4-вершинно-зв'язні планарні графи містять гамільтонові цикли, припустили, що кожен 4-вершинно-зв'язний планарний граф містить з'єднуючий підграф Халіна; тут «з'єднуючий» () означає, що підграф містить усі вершини більшого графу. Гіпотеза Lovász–Plummer залишалась не розв'язаною до 2015 року, поки не було знайдено спосіб побудови нескінченної кількості контрприкладів..

Інколи графи Халіна називають «огороженими деревами» () або «полієдрами без даху» (). Проте такі назви неоднозначні. Деякі автори використовують назву «огорожені дерева» для планарних графів утворених з дерев, листя яких об'єднано у цикл, без вимоги, щоб внутрішні вершими були степені три або більше. Назви на кшталт «побудовані на багатокутнику» або «полієдри без даху» можуть вказувати на кубічні графи Халіна.. Опуклі полієдри, чиї графи є графами Халіна інколи називають «куполами» ()..

Примітки

Посилання Графи Халіна, Інформаційна система про включення класів графів.