Теорема Галлаи — Хассе — Роя — Витавера

Теорема Галлаи – Хассе – Роя – Витавера — это вид двойственности между раскрасками вершин заданного неориентированного графа и ориентациями его рёбер. Теорема утверждает, что минимальное число красок, необходимых для правильной раскраски любого графа G, на единицу больше длины максимального пути в ориентации графа G, в которой эта длина пути минимальна[1]. В ориентации, в которых путь максимальной длины имеет минимальную длину, всегда входит по меньшей мере одна ациклическая ориентация[2].

Четыре различные ориентации цикла с 5 вершинами, показывающие максимальные ацикличные подграфы каждой ориентации (сплошные дуги) и раскраска вершин по длине максимального входящего пути в этом подграфе. Ориентация с кратчайшими путями слева даёт оптимальную раскраску графа.

Альтернативная формулировка той же теоремы утверждает, что любая ориентация графа с хроматическим числом k содержит простой ориентированный путь с k вершинами[3]. Можно наложить условия, чтобы путь начинался в любой вершине, и чтобы из этой вершины можно было достичь любую другую вершину ориентированного графа[4][5].

Примеры

Двудольный граф можно ориентировать с одной доли в другую. Самый длинный путь в такой ориентации имеет только две вершины. Обратно, если ориентация в графе не содержит пути длины три, то любая вершина должна быть либо источником (нет входящих дуг), либо стоком (нет исходящих дуг), а разбиение вершин на источник и стоки показывает, что этот граф является двудольным.

В любой ориентации графа-цикла нечётной длины невозможно придать всем соседним рёбрам разные направления, так что два последовательных ребра образуют путь с тремя вершинами. Соответственно, хроматическое число нечётных циклов равно трём.

Доказательство

Чтобы доказать, что хроматическое число больше либо равно минимальной длине максимального пути, предположим, что граф раскрашен в k цветов для некоторого k. Тогда граф можно ациклично ориентировать путём нумерации цветов, а каждому ребру придать направление от цвета с меньшим индексом к большему. В этой ориентации индексы цветов строго возрастают вдоль любого ориентированного пути, так что каждый путь содержит не более одной вершины каждого цвета, а общее число вершин пути не может превосходить k (числа цветов).

Чтобы доказать, что хроматическое число меньше либо равно минимальной длине максимального пути, допустим, что граф имеет ориентацию, в которой не более k вершин в любом ориентированном пути для некоторого k. Вершины графа можно раскрасить в k цветов путём выбора максимального ацикличного подграфа ориентации с последующей раскраской каждой вершины цветом с индексом, равным длине максимального по длине пути, идущего в данную вершину. При такой раскраске каждое ребро подграфа ориентировано из вершины с меньшим индексом в вершину с большим индексом, а потому раскраска будет правильной. Для каждого ребра, не принадлежащего подграфу, должен существовать ориентированный путь внутри подграфа, соединяющий эти две вершины в противоположном направлении, в противном случае ребро попало бы в подграф. Таким образом, ребро ориентировано от большего номера к меньшему и не нарушает правильности раскраски[6].

Доказательство этой теоремы использовал Юрий Владимирович Матиясевич в качестве тестового случая для предлагаемой схемы доказательства в дискретной математике[7].

Интерпретация в смысле категорий

Теорема имеет естественную интерпретацию в категориях ориентированных графов и гомоморфизмах графов. Гомоморфизм — это отображение вершин одного графа в вершины другого графа, при котором смежные вершины остаются смежными в образе. Тогда k-раскраска неориентированного графа G может быть описана гомоморфизмом графа G в полный граф Kk. Если в полном графе задать ориентацию, он становится турниром, и эту ориентацию можно использовать для задания ориентации в графе G. В частности, раскраска, заданная длиной наибольшего пути, соответствует гомоморфизму в транзитивный турнир (ациклически ориентированный полный граф), и любая раскраска может быть описана таким гомоморфизмом в транзитивный турнир.

Если рассматривать гомоморфизмы в другом направлении, в G, не из G, ориентированный граф G ацикличен и имеет не более k вершин в самом длинном пути тогда и только тогда, когда не существует гомоморфизма пути Pk + 1 в граф G.

Таким образом, теорема Галлаи – Хассе – Роя – Витавера эквивалентна теореме, что для любого ориентированного графа G тогда и только тогда существует гомоморфизм в транзитивный турнир с k вершинами, когда не существует гомоморфизма из пути с (k + 1) вершинами[2]. В случае, когда граф G ацикличен, утверждение можно рассматривать как форму теоремы Мирского, что самая длинная цепочка в частично упорядоченном множестве равно минимальному числу антицепочек, на которые можно разбить множество[8]. Утверждение можно обобщить от путей к другим ориентированным графам — для любого полидерева P существует двойственный ориентированный граф D, такой, что для любого ориентированного графа G существует гомоморфизм из G в D тогда и только тогда, когда не существует изоморфизма из P в G[9].

История

Теорема Галлаи – Хассе – Роя – Витавера неоднократно переоткрывалась[2]. Название теорема получила от отдельных публикаций Т. Галлаи[10], М. Хассе[11], Б. Роя[12] и Л. М. Витавера[13]. Рой приписывает формулировку теоремы Клоду Бержу, высказавшему её в виде гипотезы в книге по теории графов в 1958[12].

Примечания
  1. Hsu, Lin, 2009, с. 129–130.
  2. Nešetřil, Ossona de Mendez, 2012, с. 42.
  3. Chartrand, Zhang, 2009.
  4. Li, 2001, с. 681–685.
  5. Chang, Tong, Yan, Yeh, 2002, с. 441–444.
  6. Hsu, Lin, 2009, pp. 129—130.
  7. Матиясевич, 1974, с. 94–100.
  8. Mirsky, 1971, с. 876–877.
  9. Nešetřil, Tardif, 2008, с. 254–260.
  10. Gallai, 1968, с. 115–118.
  11. Hasse, 1965, с. 275–290.
  12. Roy, 1967, с. 129–132.
  13. Витавер, 1962, с. 758–759.

Литература
  • Lih-Hsing Hsu, Cheng-Kuan Lin. Graph Theory and Interconnection Networks. — Boca Raton, FL: CRC Press, 2009. — С. 129–130. — ISBN 978-1-4200-4481-2.
  • Jaroslav Nešetřil, Patrice Ossona de Mendez. Sparsity: Graphs, Structures, and Algorithms. — Heidelberg: Springer, 2012. — Т. 28. — С. 42. — (Algorithms and Combinatorics). — ISBN 978-3-642-27874-7. — doi:10.1007/978-3-642-27875-4.
  • Gary Chartrand, Ping Zhang. Chromatic Graph Theory. — Boca Raton, FL: CRC Press, 2009. — (Discrete Mathematics and its Applications). — ISBN 978-1-58488-800-0.
  • Hao Li. A generalization of the Gallai–Roy theorem // Graphs and Combinatorics. — 2001. — Т. 17, вып. 4. — С. 681–685. — doi:10.1007/PL00007256.
  • Gerard J. Chang, Li-Da Tong, Jing-Ho Yan, Hong-Gwa Yeh. A note on the Gallai–Roy–Vitaver theorem // Discrete Mathematics. — 2002. — Т. 256, вып. 1-2. — С. 441–444. — doi:10.1016/S0012-365X(02)00386-2.
  • Ю. В. Матиясевич. Исследования по конструктивной математике и математической логике. VI. — 1974. — Т. 40. — С. 94–100. — (Записки научных семинаров Ленинградского отделения Математического института им. В.А.Стеклова АН СССР (ЛОМИ)).
  • Leon Mirsky. A dual of Dilworth's decomposition theorem // American Mathematical Monthly. — 1971. — Т. 78, вып. 8. — С. 876–877. — doi:10.2307/2316481. — .
  • Jaroslav Nešetřil, Claude Tardif. A dualistic approach to bounding the chromatic number of a graph // European Journal of Combinatorics. — 2008. — Т. 29, вып. 1. — С. 254–260. — doi:10.1016/j.ejc.2003.09.024.
  • Tibor Gallai. Theory of Graphs (Proceedings of the Colloquium Tihany 1966). — New York: Academic Press, 1968. — С. 115–118. Как процитировано в статье (Nešetřil, Ossona de Mendez 2012)
  • Maria Hasse. Zur algebraischen Begründung der Graphentheorie. I (нем.) // Mathematische Nachrichten. — 1965. — Bd. 28, H. 5–6. — S. 275–290. — doi:10.1002/mana.19650280503.
  • B. Roy. Nombre chromatique et plus longs chemins d'un graphe (фр.) // Rev. Française Informat. Recherche Opérationnelle. — 1967. — Vol. 1, livr. 5. — P. 129–132.
  • Л. М.Витавер. Нахождение минимальных раскрасок вершин графа с помощью булевых степеней матрицы смежностей] // Доклады Академии наук. — 1962. — Т. 147. — С. 758–759.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.