Введение
Неориентированный граф является совершенным тогда и только тогда, когда его дополняющий граф также совершенен.
В теории графов теорема о совершенных графах утверждает, что неориентированный граф является совершенным тогда и только тогда, когда его дополняющий граф также совершенен. Этот результат был предложен [имя исследователя], и иногда его называют теоремой о слабо совершенных графах, чтобы отличать его от теоремы о сильно совершенных графах, характеризующей совершенные графы по их запрещенным индуцированным подграфам.
Пример
Пусть G — циклный граф нечётной длины, большей трёх (так называемое «нечётное отверстие»). Тогда для любого раскрашивания графа G требуется не менее трёх цветов, но он не содержит треугольников, поэтому не является совершенным. Согласно теореме о совершенных графах, комплемент графа G («нечётный антиотверстие») также не должен быть совершенным. Если G — цикл из пяти вершин, он изоморфен своему комплементу, но это свойство не выполняется для нечётных циклов большей длины, и вычислить число клики и хроматическое число в нечётном антиотверстии сложнее, чем в нечётном отверстии. Как утверждает теорема о сильных совершенных графах, нечётные отверстия и нечётные антиотверстия оказываются минимальными запрещёнными индуцированными подграфами для совершенных графов.
Приложения
В нетривиальном двудольном графе оптимальное число цветов (по определению) равно двум, и (поскольку двудольные графы не содержат треугольников) максимальный размер клики также равен двум. Кроме того, любой индуцированный подграф двудольного графа остаётся двудольным. Следовательно, двудольные графы являются совершенными. В двудольных графах с n вершинами минимальное кликовое покрытие имеет вид максимального паросочетания вместе с дополнительной кликой для каждой непокрытой вершины, размером n − M, где M — мощность паросочетания. Таким образом, в этом случае теорема о совершенных графах влечёт за собой теорему Кёнига о том, что размер максимального независимого множества в двудольном графе также равен n − M, результат, который послужил основным источником вдохновения для формулировки Бержем теории совершенных графов. Теорема Мирского, характеризующая высоту частично упорядоченного множества в терминах разбиений на антицепи, может быть сформулирована как совершенство графа сопоставимости частично упорядоченного множества, а теорема Дилворта, характеризующая ширину частично упорядоченного множества в терминах разбиений на цепи, может быть сформулирована как совершенство дополнений этих графов. Таким образом, теорему о совершенных графах можно использовать для доказательства теоремы Дилворта из (гораздо более простого) доказательства теоремы Мирского, или наоборот.
Доказательство Ловаша
Для доказательства теоремы о совершенном графе Ловас использовал операцию замены вершин графа на клики; Берге уже знал, что если граф совершенен, то граф, полученный в результате этого процесса замены, также совершенен. Любой такой процесс замены можно разложить на последовательные этапы удвоения вершины. Если удвоенная вершина принадлежит максимальной клике графа, то число клики и хроматическое число увеличиваются на единицу. Если же удвоенная вершина не принадлежит максимальной клике, то построим граф H, удалив из оптимальной раскраски данного графа вершины того же цвета, что и удвоенная вершина (но не саму удвоенную вершину). Удаленные вершины пересекают каждую максимальную клику, поэтому число клики и хроматическое число H на единицу меньше, чем у данного графа. Затем удаленные вершины и новая копия удвоенной вершины можно добавить обратно в виде одного цветового класса, показывая, что в этом случае операция удвоения не изменяет хроматическое число. Тот же аргумент показывает, что удвоение сохраняет равенство числа клики и хроматического числа в каждом индуцированном подграфе данного графа, следовательно, каждый шаг удвоения сохраняет совершенство графа. Для совершенного графа G Ловас строит граф G*, заменяя каждую вершину v на клику из tv вершин, где tv – количество различных максимальных независимых множеств в G, содержащих v. Можно установить соответствие между каждым из различных максимальных независимых множеств в G и одним из максимальных независимых множеств в G* таким образом, чтобы выбранные максимальные независимые множества в G* были непересекающимися, и каждая вершина G* принадлежала ровно одному выбранному множеству; то есть G* имеет раскраску, в которой каждый цветовой класс является максимальным независимым множеством. Неизбежно, эта раскраска является оптимальной раскраской G*. Поскольку G совершенен, то и G* совершенен, и, следовательно, в нем существует максимальная клика K*, размер которой равен числу цветов в этой раскраске, то есть количеству различных максимальных независимых множеств в G; необходимо, чтобы K* содержала различного представителя для каждого из этих максимальных независимых множеств. Соответствующее множество вершин K в G (вершины, чьи расширенные клики в G* пересекают K*) является кликой в G, обладающей свойством пересечения с каждым максимальным независимым множеством в G. Следовательно, граф, полученный из G путем удаления K, имеет число покрытия кликами не более чем на единицу меньше числа клики G, а число независимости – не менее чем на единицу меньше числа независимости G, и результат следует из индукции по этому числу.
Отношение к теореме сильного совершенного графа
Теорема о сильных совершенных графах утверждает, что граф является совершенным тогда и только тогда, когда ни один из его индуцированных подграфов не является циклом нечетной длины, большей или равной пяти, или дополнением к такому циклу. Поскольку эта характеристика инвариантна относительно дополнения графа, она непосредственно влечет теорему о слабых совершенных графах.
Обобщения
Доказано, что если рёбра полного графа разбиты на три подграфа таким образом, что для любых трёх вершин один из трёх подграфов содержит связный граф, и если два из этих подграфов совершенны, то и третий подграф также совершенен. Теорема о совершенных графах является частным случаем этого результата, когда один из трёх подграфов — пустой граф.