PROFILPELAJAR.COM

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

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

Примеры

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

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

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

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

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

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

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

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

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

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

История

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

Примечания

↑ Hsu, Lin, 2009, с. 129–130.
↑ ¹ ² ³ Nešetřil, Ossona de Mendez, 2012, с. 42.
↑ Chartrand, Zhang, 2009.
↑ Li, 2001, с. 681–685.
↑ Chang, Tong, Yan, Yeh, 2002, с. 441–444.
↑ Hsu, Lin, 2009, pp. 129—130.
↑ Матиясевич, 1974, с. 94–100.
↑ Mirsky, 1971, с. 876–877.
↑ Nešetřil, Tardif, 2008, с. 254–260.
↑ Gallai, 1968, с. 115–118.
↑ Hasse, 1965, с. 275–290.
↑ ¹ ² Roy, 1967, с. 129–132.
↑ Витавер, 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.

[_c7279f61862defba-1] Hsu, Lin, 2009, с. 129–130.

[_96e67061dab06b56-2] ¹ ² ³ Nešetřil, Ossona de Mendez, 2012, с. 42.

[_648beae43dae0955-3] Chartrand, Zhang, 2009.

[_b3d247a6643eb29c-4] Li, 2001, с. 681–685.

[_a94dd1072e371014-5] Chang, Tong, Yan, Yeh, 2002, с. 441–444.

[_e1f70261959958e3-6] Hsu, Lin, 2009, pp. 129—130.

[_e9e1c1adb2f95d9b-7] Матиясевич, 1974, с. 94–100.

[_5bf608d3365aef14-8] Mirsky, 1971, с. 876–877.

[_4283eb5a00d9cc52-9] Nešetřil, Tardif, 2008, с. 254–260.

[_250a67f774761a6f-10] Gallai, 1968, с. 115–118.

[_dbb5e7b22f0b8726-11] Hasse, 1965, с. 275–290.

[_ea6dfa3dede0a1b5-12] ¹ ² Roy, 1967, с. 129–132.

[_8816a3f3870ab640-13] Витавер, 1962, с. 758–759.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

PROFILPELAJAR.COM

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

Содержание

Примеры

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

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

История

Примечания

Литература

Read other articles:

QRSAM

Sejarah Malang Raya

Синелобый амазон

Roda pendaratan

North Jutlandic Island

コルク

Prunus simonii

36e division de grenadiers

Atticus Ross

约翰斯顿环礁

Tiong-tikus

John Garrett (comics)

Scott Report

昆陽之戰

Potawatomi language

Morane-Saulnier MS.603

Deconstruction

Nadia Bouras

Cluj-Napoca

Мінаківський Болеслав Людвикович