В теории графов теорема о совершенном графе Ласло Ловаса (1972a, 1972b) утверждает, что неориентированный граф совершенен тогда и только тогда, когда его дополнительный граф также совершенен. Этот результат был выдвинут Берже (1961, 1963), и его иногда называют слабой теоремой о совершенном графе, чтобы отличать ее от сильной теоремы о совершенном графе [1], характеризующей совершенные графы с помощью их запрещенных индуцированных подграфов .
Совершенный граф — это неориентированный граф со свойством, что в каждом из его индуцированных подграфов размер наибольшей клики равен минимальному числу цветов в раскраске подграфа. Совершенные графы включают в себя множество важных классов графов, включая двудольные графы , хордовые графы и графы сравнимости .
Дополнение графа имеет ребро между двумя вершинами тогда и только тогда, когда исходный граф не имеет ребра между теми же двумя вершинами. Таким образом, клика в исходном графе становится независимым множеством в дополнении, а раскраска исходного графа становится покрытием кликой дополнения.
Теорема об идеальном графе гласит:
Эквивалентно, в идеальном графе размер максимального независимого множества равен минимальному числу клик в покрытии клик.
Пусть G — граф-цикл нечетной длины , большей трех (так называемая «нечетная дыра»). Тогда G требует по крайней мере трех цветов в любой раскраске, но не имеет треугольников, поэтому он не является совершенным. По теореме о совершенном графе дополнение G («нечетная антидыра») также должно быть несовершенным. Если G — цикл из пяти вершин, он изоморфен своему дополнению , но это свойство неверно для более длинных нечетных циклов, и вычислить число клик и хроматическое число в нечетной антидыре не так тривиально, как в нечетной дыре. Как гласит сильная теорема о совершенном графе , нечетные дыры и нечетные антидыры оказываются минимальными запрещенными индуцированными подграфами для совершенных графов.
В нетривиальном двудольном графе оптимальное количество цветов (по определению) равно двум, и (поскольку двудольные графы не содержат треугольников ) максимальный размер клики также равен двум. Кроме того, любой индуцированный подграф двудольного графа остается двудольным. Поэтому двудольные графы являются совершенными. В двудольных графах с n вершинами минимальное покрытие кликой принимает форму максимального паросочетания вместе с дополнительной кликой для каждой непарной вершины с размером n − M , где M — мощность паросочетания. Таким образом, в этом случае теорема о совершенном графе подразумевает теорему Кёнига о том, что размер максимального независимого множества в двудольном графе также равен n − M , [2] результат, который послужил основным источником вдохновения для формулировки Берже теории совершенных графов.
Теорема Мирского, характеризующая высоту частично упорядоченного множества в терминах разбиений на антицепи, может быть сформулирована как совершенство графа сравнимости частично упорядоченного множества, а теорема Дилворта, характеризующая ширину частично упорядоченного множества в терминах разбиений на цепи, может быть сформулирована как совершенство дополнений этих графов. Таким образом, теорема о совершенном графе может быть использована для доказательства теоремы Дилворта из (гораздо более простого) доказательства теоремы Мирского, или наоборот. [3]
Для доказательства теоремы о совершенном графе Ловас использовал операцию замены вершин в графе кликами; Берге уже знал, что если граф совершенен, то граф, образованный этим процессом замены, также совершенен. [4] Любой такой процесс замены можно разбить на повторяющиеся шаги удвоения вершины. Если удвоенная вершина принадлежит максимальной клике графа, она увеличивает как кликовое число, так и хроматическое число на единицу. Если, с другой стороны, удвоенная вершина не принадлежит максимальной клике, сформируйте граф H, удалив вершины того же цвета, что и удвоенная вершина (но не сама удвоенная вершина) из оптимальной раскраски данного графа. Удаленные вершины встречаются с каждой максимальной кликой, поэтому H имеет кликовое число и хроматическое число на единицу меньше, чем у данного графа. Удаленные вершины и новая копия удвоенной вершины затем могут быть добавлены обратно как один цветовой класс, показывая, что в этом случае шаг удвоения оставляет хроматическое число неизменным. Тот же аргумент показывает, что удвоение сохраняет равенство числа клики и хроматического числа в каждом индуцированном подграфе данного графа, поэтому каждый шаг удвоения сохраняет совершенство графа. [5]
Учитывая совершенный граф 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 , и результат следует индукцией по этому числу. [6]
Сильная теорема о совершенном графе Чудновского и др. (2006) утверждает, что граф является совершенным тогда и только тогда, когда ни один из его индуцированных подграфов не является циклом нечетной длины, большей или равной пяти, или их дополнением. Поскольку эта характеристика не зависит от дополнения графа, она немедленно влечет слабую теорему о совершенном графе.
Кэмерон, Эдмондс и Ловас (1986) доказали, что если ребра полного графа разбиты на три подграфа таким образом, что каждые три вершины индуцируют связный граф в одном из трех подграфов, и если два из подграфов являются совершенными, то третий подграф также является совершенным. Теорема о совершенном графе является частным случаем этого результата, когда один из трех подграфов является пустым графом .