Построение Хайоша (Hkvmjkyuny }gwkog)
Построение Хайоша — это операция над графами, названная именем венгерского математика Дьёрдя Хайоша[1], которая может быть использована для построения любого критического графа или любого графа, хроматическое число которого не меньше некоторого заданного порога.
Построение
[править | править код]Пусть G и H — два неориентированных графа, vw — ребро графа G, а xy — ребро графа H. Тогда построение Хайоша образует новый граф, комбинирующий два графа путём объединения вершин v и x в одну вершину, удаления рёбер vw и xy и добавления нового ребра wy.
Например, пусть G и H — два полных графа K4 с четырьмя вершинами. Ввиду симметрии этих графов выбор рёбер в этих графах несущественен. В этом случае результатом применения построения Хайоша будет веретено Мозера, граф единичных расстояний с семью вершинами, требующий для раскраски четыре цвета.
Другой пример, если G а H — два цикла длины p и q соответственно, то результатом применения построения Хайоша будет снова цикл длины p + q − 1.
Конструируемые графы
[править | править код]Говорят, что граф G k-конструируемый (или k-конструируемый по Хайошу), если он образован одним из трёх способов [2]:
- Полный граф Kk является k-конструируемым.
- Пусть G и H — два k-конструируемых графа. Тогда граф, образованный применением построения Хайоша к G и H, является k-конструируемым.
- Пусть G — любой k-конструируемый граф, и пусть u и v — любые две несмежные вершины в G. Тогда граф, образованный объединением u и v в одну вершину, также является k-конструируемым. Эквивалентно, этот граф может быть построен добавлением ребра uv к графу, а затем стягиванием его.
Связь с раскраской
[править | править код]Достаточно просто показать, что любой k-конструируемый граф требует по меньшей мере k цветов для правильной раскраски графа. В самом деле, это совершенно ясно для полного графа Kk, а результат объединения двух несмежных вершин вынуждает раскрасить их в один цвет в любой раскраске, что не уменьшает числа цветов. В самом построении Хайоша новое ребро wy заставляет по меньшей мере одну из двух вершин w и y иметь цвет, отличный от цвета вершины, полученной объединением вершин v and x, так что любая правильная раскраска комбинированного графа приводит к правильной раскраске одного из двух меньших графов, из которых граф был получен, откуда опять получаем необходимость k цветов[2].
Хайош доказал более строгое утверждение, что граф требует по меньшей мере k цветов в любой правильной раскраске тогда и только тогда, когда он содержит k-конструируемый граф в качестве подграфа. Эквивалентно, любой k-критический граф (граф, требующий k цветов, но любой собственный подграф требует меньше цветов) является k-конструируемым[3]. Альтернативно, любой граф, требующий k цветов, может быть образован комбинированием построения Хайоша, операциями объединения двух несмежных вершин и операциями добавления вершин или рёбер к заданному графу, начав с полного графа Kk[4].
Аналогичное построение может быть использовано для предписанной раскраски вместо обычной раскраски[5][6].
Конструируемость критических графов
[править | править код]Для k=3 любой k-критический граф (то есть любой нечётный цикл) может быть построен как k-конструируемый граф таким образом, что все графы, образованные при его построении, являются также k-критическими. Для k=8 это неверно — граф, который нашёл Катлин[7] в качестве контрпримера гипотезе Хадвигера, что k-хроматический граф стягиваем к полному графу Kk, является контрпримером для этой задачи. Впоследствии были найдены k-критические, но не k-конструируемые графы лишь исключительно через k-критические графы, для всех k ≥ 4. Для k=4 один такой пример получается из графа додекаэдра путём добавления нового ребра к каждой паре антиподальных вершин[англ.][8].
Число Хайоша
[править | править код]Поскольку объединение двух несмежных вершин уменьшает число вершин в результирующем графе, число операций, необходимых для представления заданного графа G с использованием операций, определённых Хайошем, не может превзойти числа вершин графа G[9].
Мэнсфилд и Уэлш [10] определяют число Хайоша h(G) k-хроматического графа G как минимальное число шагов, необходимых для построения G из Kk, где на каждом шаге образуется новый граф путём комбинации двух сформированных ранее графов, объединения двух несмежных вершин сформированного ранее графа или добавления ребра к сформированному ранее графу. Они показали, что для графа G с n вершинами и m рёбрами h(G) ≤ 2n2/3 − m + 1 − 1. Если любой граф имеет полиномиальное число Хайоша, отсюда следует, что можно доказать нераскрашиваемость за недетерминированное полиномиальное время, а потому следует, что NP = co-NP, что считают невероятным теоретики сложности алгоритмов[11]. Однако неизвестно, как доказать неполиномиальные нижние границы чисел Хайоша без некоторых предположений о теоретической сложности, и если такие границы будут доказаны, немедленно будет следовать существование неполиномиальных границ некоторых типов систем Фреге[англ.] в математической логике[11].
Минимальный размер дерева выражений[англ.], описывающего построение Хайоша для заданного графа G, может быть существенно больше, чем число Хайоша графа G, поскольку наименьшее выражение для G может использовать повторно те же графы несколько раз (экономия не разрешена в дереве выражений). Существует 3-хроматические графы, для которых наименьшее такое дерево выражений имеет экспоненциальный размер[12].
Другие приложения
[править | править код]Кёстер[13] использовал построение Хайоша для получения бесконечного множества 4-критичных полиэдральных графов, каждый из которых имеет вдвое больше рёбер, чем вершин. Подобным же образом Лю и Чжан[14] использовали построение, начинающееся с графа Грёча, чтобы получить много 4-критичных графов без треугольников, для которых, как они показали, трудно найти раскраску с помощью традиционных алгоритмов поиска с возвратом.
В комбинаторике многогранников Рейнхард Эйлер[15] использовал построение Хайоша для генерации фасет устойчивого множества политопа.
Примечания
[править | править код]- ↑ Hajós, 1961.
- ↑ Перейти обратно: 1 2 Diestel, 2006.
- ↑ Доказательство факта можно также найти у Дистеля (Diestel 2006).
- ↑ Jensen, Toft, 1994, с. 184.
- ↑ Gravier, 1996.
- ↑ Kubale, 2004.
- ↑ Catlin, 1979.
- ↑ Jensen, Royle, 1999.
- ↑ Дистель (Diestel 2006) ссылается на это, когда пишет, что последовательность операций «не всегда короткая». Йенсен и Тофт (Jensen, Toft, 1994, 11.6 Length of Hajós proofs, стр. 184—185), выдвигают в качестве открытой проблемы определение минимального числа шагов для построения любого n-вершинного графа.
- ↑ Mansfield, Welsh, 1982.
- ↑ Перейти обратно: 1 2 Pitassi, Urquhart, 1995.
- ↑ Iwama, Pitassi, 1995.
- ↑ Koester, 1991.
- ↑ Liu, Zhang, 2006.
- ↑ Euler, 2003.
Литература
[править | править код]- P. A. Catlin. Hajós's graph-colouring conjecture: variations and counterexamples // Journal of Combinatorial Theory. — 1979. — Т. 26. — С. 268–274. — doi:10.1016/0095-8956(79)90062-5.
- Reinhard Diestel. Graph Theory. — 3rd. — Springer-Verlag, 2006. — Т. 173. — С. 117–118. — (Graduate Texts in Mathematics). — ISBN 978-3-540-26183-4.
- Reinhardt Euler. Hajós' construction and polytopes // Combinatorial optimization—Eureka, you shrink!. — Berlin: Springer-Verlag, 2003. — Т. 2570. — С. 39–47. — (Lecture Notes in Computer Science). — doi:10.1007/3-540-36478-1_6.
- Sylvain Gravier. A Hajós-like theorem for list coloring // Discrete Mathematics. — 1996. — Т. 152, вып. 1-3. — С. 299–302. — doi:10.1016/0012-365X(95)00350-6.
- G. Hajós. Über eine Konstruktion nicht n-färbbarer Graphen // Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe. — 1961. — Т. 10. — С. 116–117. Как процитировано у Йенсена и Тофта (Jensen, Toft 1994)
- Kazuo Iwama, Toniann Pitassi. Exponential lower bounds for the tree-like Hajós calculus // Information Processing Letters. — 1995. — Т. 54, вып. 5. — С. 289–294. — doi:10.1016/0020-0190(95)00035-B.
- Tommy R. Jensen, Gordon F. Royle. Hajós constructions of critical graphs // Journal of Graph Theory. — 1999. — Т. 30, вып. 1. — С. 37–50. — doi:10.1002/(SICI)1097-0118(199901)30:1<37::AID-JGT5>3.0.CO;2-V.
- Tommy R. Jensen, Bjarne Toft. Graph Coloring Problems. — 2nd. — John Wiley and Sons, 1994. — ISBN 978-0-471-02865-9.
- Gerhard Koester. On 4-critical planar graphs with high edge density // Discrete Mathematics. — 1991. — Т. 98, вып. 2. — С. 147–151. — doi:10.1016/0012-365X(91)90039-5.
- Marek Kubale. Graph Colorings. — American Mathematical Society, 2004. — Т. 352. — (Contemporary Mathematics). — ISBN 978-0-8218-3458-9.
- Sheng Liu, Jian Zhang. Using Hajós’ construction to generate hard graph 3-colorability instances // Artificial Intelligence and Symbolic Computation. — Springer-Verlag, 2006. — Т. 4120. — С. 211–225. — (Lecture Notes in Computer Science). — doi:10.1007/11856290_19.
- A. J. Mansfield, D. J. A. Welsh. Some colouring problems and their complexity // Graph theory (Cambridge, 1981). — Amsterdam: North-Holland, 1982. — Т. 62. — С. 159–170. — (North-Holland Math. Stud.).
- Toniann Pitassi, Alasdair Urquhart. The complexity of the Hajós calculus // SIAM Journal on Discrete Mathematics. — 1995. — Т. 8, вып. 3. — С. 464–483. — doi:10.1137/S089548019224024X.
Для улучшения этой статьи желательно:
|