Теорема о совершенных графах

Теорема о совершенных графах Ловаша утверждает, что неориентированный граф является совершенным тогда и только тогда, когда его дополнение также совершенно. Это утверждение высказал в виде гипотезы Берж и утверждение называют иногда слабой теоремой о совершенных графах, чтобы не смешивать со строгой теоремой о совершенных графах, описывающей совершенные графы их запрещёнными порождёнными подграфами.

Утверждение теоремы

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

Дополнение графа имеет ребро между двумя вершинами тогда и только тогда, когда исходный граф такого ребра не имеет. Таким образом, клика в исходном графе становится независимым множеством в дополнении и раскраска исходного графа становится кликовым покрытием дополнения.

Теорема о совершенных графах утверждает:

Дополнение совершенного графа совершенно.

Эквивалентная формулировка: В совершенном графе размер наибольшего независимого множества равен минимальному числу клик в кликовом покрытии.

Пример

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

Пусть G — граф-цикл нечётной длины, большей трёх (так называемая «нечётная дыра»). Тогда требуется для любой раскраски G по меньшей мере три цвета, но нет ни одного треугольника, так что граф не совершенен. По теореме о совершенных графах, дополнение графа G («нечётная антидыра») должно поэтому также быть несовершенным. Если граф G является циклом из пяти вершин, он изоморфен своему дополнению, но это неверно для более длинных циклов. Нетривиальной задачей является вычисление кликового числа и хроматического числа в нечётной антидыре и нечётной дыре. Как утверждает строгая теорема о совершенных графах, нечётные дыры и нечётные антидыры оказываются минимальными запрещёнными порождёнными подграфами совершенных графов.

Приложения

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

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

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

Для доказательства теоремы о совершенных графах Ловаш использовал операцию замены вершин в графе кликами. Уже Бержу было известно, что если граф совершенен, полученный такой заменой граф также будет совершенным. Любой такой процесс замены может быть разбит на повторяющиеся шаги дублирования вершин. Если дублируемая вершина принадлежит наибольшей клике графа, она увеличивает кликовое число и хроматическое число на единицу. Если, с другой стороны, дублируемая вершина не принадлежит наибольшей клике, образуем граф H путём удаления вершин того же цвета, что и у дублируемой (но не саму дублируемую вершину) из оптимальной раскраски графа. Удаляемые вершины входят во все наибольшие клики, так что H имеет число клик и хроматическое число на единицу меньше, чем в исходном графе. Удалённые вершины и новые копии задублированных вершин могут быть добавлены в единый класс цвета, что показывает, что шаг дублирования не меняет хроматическое число. Те же доводы показывают, что удвоение сохраняет равенство числа клик хроматическому числу в каждом порождённом подграфе данного графа, так что каждый шаг удвоения сохраняет совершенство графа.

Если задан совершенный граф G, Ловаш образует граф G* путём замены каждой вершины v кликой с t_v вершинами, где t_v является числом различных максимальных различных множеств в G, содержащих v. Можно сопоставить каждой из различных максимальных независимых множеств из G максимальное независимое множество в G* таким образом, что независимые множества в G* все не будут пересекаться и каждая вершина G* появляется в единственном выбранном множестве. То есть G* имеет раскраску, в которой каждый класс цвета является максимальным независимым множеством. Необходимым образом эта раскраска будет оптимальной раскраской G*. Поскольку G совершенен, таковым является и G*, а тогда он имеет максимальную клику K*, размер которой равен числу цветов в этой раскраске, что равно числу различных максимальных независимых множеств в G. Необходимым образом K* содержит различные представления для каждого из этих максимальных множеств. Соответствующее множество K вершин в G (вершин, расширенные клики которых в G* пересекают K*) является кликой в G со свойством, что оно пересекает любое максимальное независимое множество в G. Таким образом, граф, образованный из G путём удаления K, имеет число кликового покрытия, не превосходящее кликового числа графа G без единицы, а число независимости по меньшей мере на единицу меньше числа независимости графа G. Результат следует из индукции по этому числу

Отношение к теореме о строгой теореме о совершенных графах

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

Обобщения

Камерон, Эдмондс и Ловаш доказали, что если рёбра полного графа разбиты на три подграфа таким образом, что любые три вершины порождают связный граф в одном из трёх подграфов, и если два из подграфов совершенны, то третий подграф тоже совершенный. Теорема о совершенном графе является частным случаем этого результата, когда один из трёх графов является пустым графом.