WikiDer > Теорема Галлаи – Хассе – Роя – Витавера.

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

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

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

Примеры

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

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

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

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

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

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

Теоретико-категориальная интерпретация

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

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

Таким образом, теорема Галлаи – Хассе – Роя – Витавера может быть эквивалентно сформулирована следующим образом:[2]

Для каждого ориентированного графа граммсуществует гомоморфизм из грамм к k-вершинный транзитивный турнир тогда и только тогда, когда нет гомоморфизма из (k + 1) -вершинный путь к грамм.

В случае, если грамм является ациклическим, это также можно рассматривать как форму Теорема Мирского что самая длинная цепочка в частично заказанный набор равно минимальному количеству антицепей, на которые может быть разбито множество.[7] Это утверждение можно обобщить от путей к другим ориентированным графам: для каждого многодерево п есть дуально ориентированный граф D такое, что для любого ориентированного графа граммсуществует гомоморфизм из грамм к D тогда и только тогда, когда нет гомоморфизма из п к грамм.[8]

История

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

Рекомендации

  1. ^ а б Сюй, Лих-Син; Лин, Ченг-Куан (2009), "Теорема 8.5", Теория графов и сети взаимосвязей, Бока-Ратон, Флорида: CRC Press, стр. 129–130, ISBN 978-1-4200-4481-2, МИСТЕР 2454502.
  2. ^ а б c Нешетржил, Ярослав; Оссона де Мендес, Патрис (2012), «Теорема 3.13», Разреженность: графики, структуры и алгоритмы, Алгоритмы и комбинаторика, 28, Гейдельберг: Springer, стр. 42, Дои:10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, МИСТЕР 2920058.
  3. ^ Чартран, Гэри; Чжан, Пин (2009), «Теорема 7.17 (Теорема Галлаи – Роя – Витавера)», Теория хроматических графов, Дискретная математика и ее приложения, Бока-Ратон, Флорида: CRC Press, ISBN 978-1-58488-800-0, МИСТЕР 2450569.
  4. ^ Ли, Хао (2001), "Обобщение теоремы Галлаи – Роя", Графы и комбинаторика, 17 (4): 681–685, Дои:10.1007 / PL00007256, МИСТЕР 1876576.
  5. ^ Чанг, Джерард Дж .; Тонг, Ли-Да; Ян, Цзин-Хо; Yeh, Hong-Gwa (2002), "Примечание к теореме Галлаи – Роя – Витавера", Дискретная математика, 256 (1–2): 441–444, Дои:10.1016 / S0012-365X (02) 00386-2, МИСТЕР 1927565.
  6. ^ Матиясевич, Ю. В. (1974), "Одна схема доказательств в дискретной математике" [Некоторая схема доказательств в дискретной математике], Исследования по конструктивной математике и математической логике [Исследования по конструктивной математике и математической логике. Часть VI. Посвящается А.А. Маркову к 70-летию со дня рождения.], Записки научных семинаров Ленинградского отделения Математического института им. В.А. Стеклова Академии Наук СССР (ЛОМИ), 40, стр. 94–100, МИСТЕР 0363823.
  7. ^ Мирский Леон (1971), «Двойственная теорема Дилворта о разложении», Американский математический ежемесячный журнал, 78 (8): 876–877, Дои:10.2307/2316481, JSTOR 2316481.
  8. ^ Нешетржил, Ярослав; Тардиф, Клод (2008), «Дуалистический подход к ограничению хроматического числа графа», Европейский журнал комбинаторики, 29 (1): 254–260, Дои:10.1016 / j.ejc.2003.09.024, МИСТЕР 2368632.
  9. ^ Галлай, Тибор (1968), «О ориентированных графах и схемах», Теория графов (материалы коллоквиума, состоявшегося в Тихани, 1966 г.), Будапешт: Akadémiai Kiadó, стр. 115–118..
  10. ^ Хассе, Мария (1965), "Zur algebraischen Begründung der Graphentheorie. I", Mathematische Nachrichten (на немецком), 28 (5–6): 275–290, Дои:10.1002 / мана.19650280503, МИСТЕР 0179105.
  11. ^ а б Рой, Б. (1967), "Nombre chromatique et plus longs chemins d'un graphe" (PDF), Rev. Française Informat. Recherche Opérationnelle (На французском), 1 (5): 129–132, Дои:10,1051 / м2ан / 1967010501291, МИСТЕР 0225683.
  12. ^ Витавер, Л. М. (1962), «Нахождение минимальных красок вершин графа с помощью булевых степеней матрицы множеств [Определение минимальной раскраски вершин графа с помощью булевых степеней матрицы инцидентности]», Доклады Академии Наук СССР (на русском), 147: 758–759, МИСТЕР 0145509.