Построение Хайоша

Перейти к навигацииПерейти к поиску

Построение Хайоша — это операция над графами, названная именем венгерского математика Дьёрдя Хайоша[1], которая может быть использована для построения любого критического графа или любого графа, хроматическое число которого не меньше некоторого заданного порога.

Построение

Применение построения Хайоша для двух копий K4 путём объединения вершин из двух копий графа в одну вершину (показана двумя цветами), удаления вершин, инцидентных объединённой вершине в каждом подграфе (показаны пунктиром) и добавления нового ребра, соединяющего конечные вершины удалённых вершин (показано зелёным цветом), в результате чего получаем веретено Мозера.

Пусть 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] использовал построение Хайоша для генерации фасет устойчивого множества политопа.

Примечания

  1. ↑ Hajós, 1961.
  2. ↑ 1 2 Diestel, 2006.
  3. ↑ Доказательство факта можно также найти у Дистеля (Diestel 2006).
  4. ↑ Jensen, Toft, 1994, с. 184.
  5. ↑ Gravier, 1996.
  6. ↑ Kubale, 2004.
  7. ↑ Catlin, 1979.
  8. ↑ Jensen, Royle, 1999.
  9. ↑ Дистель (Diestel 2006) ссылается на это, когда пишет, что последовательность операций «не всегда короткая». Йенсен и Тофт (Jensen, Toft, 1994, 11.6 Length of Hajós proofs, стр. 184—185), выдвигают в качестве открытой проблемы определение минимального числа шагов для построения любого n-вершинного графа.
  10. ↑ Mansfield, Welsh, 1982.
  11. ↑ 1 2 Pitassi, Urquhart, 1995.
  12. ↑ Iwama, Pitassi, 1995.
  13. ↑ Koester, 1991.
  14. ↑ Liu, Zhang, 2006.
  15. ↑ 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.