Теорема Галлаи — Хассе — Роя — Витавера (Mykjybg Igllgn — }gvvy — Jkx — Fnmgfyjg)

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

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

Альтернативная формулировка той же теоремы утверждает, что любая ориентация графа с хроматическим числом 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. ↑ 1 2 3 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. ↑ 1 2 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. — JSTOR 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.
Источник — https://ru.wikipedia.org/w/index.php?title=Теорема_Галлаи_—_Хассе_—_Роя_—_Витавера&oldid=134511982