В теории графов сильная теорема о совершенном графе — это запрещённая графовая характеристика совершенных графов как в точности тех графов, которые не имеют ни нечётных дыр ( индуцированных циклов нечётной длины длиной не менее 5), ни нечётных антидыр (дополнений нечётных дыр). Она была выдвинута Клодом Берже в 1961 году. Доказательство Марии Чудновской , Нила Робертсона , Пола Сеймура и Робина Томаса было объявлено в 2002 году [1] и опубликовано ими в 2006 году.
Доказательство сильной теоремы о совершенном графе принесло ее авторам премию в размере 10 000 долларов, предоставленную Жераром Корнуэжолем из Университета Карнеги — Меллона [2], а также премию Фулкерсона 2009 года . [3]
Совершенный граф — это граф, в котором для каждого индуцированного подграфа размер максимальной клики равен минимальному числу цветов в раскраске графа; совершенные графы включают в себя многие известные классы графов, включая двудольные графы , хордовые графы и графы сравнимости . В своих работах 1961 и 1963 годов, впервые определяющих этот класс графов, Клод Берже заметил, что для совершенного графа невозможно содержать нечетную дыру, индуцированный подграф в форме графа цикла нечетной длины длиной пять или более, потому что нечетные дыры имеют кликовое число два и хроматическое число три. Аналогично он заметил, что совершенные графы не могут содержать нечетные антидыры, индуцированные подграфы, дополнительные к нечетным дырам: нечетная антидыра с 2k + 1 вершинами имеет кликовое число k и хроматическое число k + 1, что снова невозможно для совершенных графов. Графы, не имеющие ни нечетных дыр, ни нечетных антидыр, стали известны как графы Берже.
Берже предположил, что каждый граф Берже является совершенным, или, что эквивалентно, что совершенные графы и графы Берже определяют один и тот же класс графов. Это стало известно как гипотеза о сильном совершенном графе, до ее доказательства в 2002 году, когда она была переименована в теорему о сильном совершенном графе.
Другая гипотеза Берже, доказанная в 1972 году Ласло Ловасом , заключается в том, что дополнение каждого совершенного графа также является совершенным. Это стало известно как теорема о совершенном графе или (чтобы отличить ее от сильной гипотезы/теоремы о совершенном графе) слабая теорема о совершенном графе. Поскольку характеристика запрещенного графа Берже является самодополнительной, слабая теорема о совершенном графе немедленно следует из сильной теоремы о совершенном графе.
Доказательство теоремы о сильном совершенном графе Чудновского и др. следует схеме, выдвинутой в 2001 году Конфорти, Корнуэжолем, Робертсоном, Сеймуром и Томасом, согласно которой каждый граф Берже либо образует один из пяти типов базовых строительных блоков (специальные классы совершенных графов), либо имеет один из четырех различных типов структурной декомпозиции на более простые графы. Минимально несовершенный граф Берже не может иметь ни одного из этих декомпозиций, из чего следует, что контрпример к теореме не может существовать. [4] Эта идея была основана на предыдущих предполагаемых структурных декомпозициях подобного типа, которые подразумевали бы гипотезу о сильном совершенном графе, но оказались ложными. [5]
Пять основных классов совершенных графов, которые образуют базовый случай этой структурной декомпозиции, — это двудольные графы, линейные графы двудольных графов, дополнительные графы двудольных графов, дополнения линейных графов двудольных графов и графы двойного разделения. Легко видеть, что двудольные графы совершенны: в любом нетривиальном индуцированном подграфе число клик и хроматическое число оба равны двум и, следовательно, равны. Совершенство дополнений двудольных графов и дополнений линейных графов двудольных графов эквивалентно теореме Кёнига , связывающей размеры максимальных паросочетаний , максимальных независимых множеств и минимальных вершинных покрытий в двудольных графах. Совершенство линейных графов двудольных графов может быть эквивалентно сформулировано как тот факт, что двудольные графы имеют хроматический индекс , равный их максимальной степени , что было доказано Кёнигом (1916). Таким образом, все четыре из этих основных классов совершенны. Графы двойного разделения являются родственниками графов разделения , которые также можно считать идеальными. [6]
В этом доказательстве рассматриваются четыре типа разложений: 2-соединения, дополнения 2-соединений, сбалансированные косые разбиения и однородные пары.
2-соединение — это разбиение вершин графа на два подмножества, обладающее тем свойством, что ребра, охватывающие разрез между этими двумя подмножествами, образуют два непересекающихся по вершинам полных двудольных графа . Когда граф имеет 2-соединение, его можно разложить на индуцированные подграфы, называемые «блоками», заменив одно из двух подмножеств вершин кратчайшим путем внутри этого подмножества, который соединяет один из двух полных двудольных графов с другим; когда такого пути не существует, блок формируется вместо этого заменой одного из двух подмножеств вершин двумя вершинами, по одной для каждого полного двудольного подграфа. 2-соединение является совершенным тогда и только тогда, когда оба его блока являются совершенными. Следовательно, если минимально несовершенный граф имеет 2-соединение, оно должно быть равно одному из его блоков, из чего следует, что это должен быть нечетный цикл, а не цикл Бержа. По той же причине минимально несовершенный граф, дополнение которого имеет 2-соединение, не может быть графом Бержа. [7]
Косое разбиение — это разбиение вершин графа на два подмножества, одно из которых индуцирует несвязный подграф, а другое имеет несвязное дополнение; Хватал (1985) предположил, что никакой минимальный контрпример к сильной гипотезе о совершенном графе не может иметь косого разбиения. Чудновский и др. ввели некоторые технические ограничения на косые разбиения и смогли показать, что гипотеза Хватала верна для полученных «сбалансированных косых разбиений». Полная гипотеза является следствием сильной теоремы о совершенном графе. [8]
Однородная пара связана с модульным разложением графа. Это разбиение графа на три подмножества V 1 , V 2 и V 3 такое, что V 1 и V 2 вместе содержат не менее трех вершин, V 3 содержит не менее двух вершин, и для каждой вершины v в V 3 и каждого i в {1,2} либо v смежна со всеми вершинами в V i , либо ни с одной из них. Для минимально несовершенного графа невозможно иметь однородную пару. [9] После доказательства сильной гипотезы о совершенном графе Чудновский (2006) упростил ее, показав, что однородные пары могут быть исключены из набора разложений, используемых в доказательстве.
Доказательство того, что каждый граф Берже попадает в один из пяти основных классов или имеет один из четырех типов разложения, следует за анализом случаев в соответствии с тем, существуют ли определенные конфигурации внутри графа: «растяжитель», подграф, который может быть разложен на три индуцированных пути, подчиняющихся определенным дополнительным ограничениям, дополнение растяжителя и «собственное колесо», конфигурация, связанная с графом колеса , состоящая из индуцированного цикла вместе с вершиной концентратора, смежной по крайней мере с тремя вершинами цикла и подчиняющаяся нескольким дополнительным ограничениям. Для каждого возможного выбора того, существует ли растяжитель или его дополнение или собственное колесо внутри данного графа Берже, можно показать, что граф находится в одном из основных классов или является разложимым. [10] Этот анализ случаев завершает доказательство.