Теорема Могла – Хассе – Роя – Витавера.

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

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

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

Примеры

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

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

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

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

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

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

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

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

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

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

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

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

История и связанные результаты

Теорема Галлаи–Хассе–Роя–Витавера неоднократно переоткрывалась . Он назван в честь отдельных публикаций Тибора Галлаи , Мария Хассе , Б. Рой, и Л.М. Витавер. Рой приписывает формулировку теоремы гипотезе из учебника по теории графов 1958 года Клода Бержа . Это обобщение гораздо более старой теоремы Ласло Редеи 1934 года о том, что каждый турнир (ориентированный полный граф) содержит направленный гамильтонов путь . Теорема Редеи непосредственно следует из теоремы Галлаи–Хассе–Роя–Витавера, примененной к неориентированному полному графу.

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