Loading AI tools
Из Википедии, свободной энциклопедии
Теорема Галлаи – Хассе – Роя – Витавера — это вид двойственности между раскрасками вершин заданного неориентированного графа и ориентациями его рёбер. Теорема утверждает, что минимальное число красок, необходимых для правильной раскраски любого графа 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].
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
