В теории графов сильная теорема о совершенных графах представляет собой запрещенную характеристику идеальных графов как графов, которые не имеют ни нечетных дыр ( индуцированных циклов нечетной длины длиной не менее 5), ни нечетных антидыр (дополнений к нечетным дырам). Гипотеза была высказана Клодом Берже в 1961 году. Доказательство Марии Чудновской , Нила Робертсона , Пола Сеймура и Робина Томаса было анонсировано в 2002 году [1] и опубликовано ими в 2006 году.
Доказательство сильной теоремы о совершенном графе принесло ее авторам премию в размере 10 000 долларов, предложенную Жераром Корнюжолем из Университета Карнеги-Меллона [2], и премию Фулкерсона 2009 года . [3]
Идеальный граф — это граф, в котором для каждого индуцированного подграфа размер максимальной клики равен минимальному количеству цветов в раскраске графа; К совершенным графам относятся многие известные классы графов, в том числе двудольные графы , хордальные графы и графы сравнимости . В своих работах 1961 и 1963 годов, впервые определивших этот класс графов, Клод Берже заметил, что идеальный граф не может содержать нечетную дыру, индуцированный подграф в форме графа циклов нечетной длины длины пять или Более того, потому что нечетные дырки имеют клику номер два и хроматический номер три. Точно так же он заметил, что совершенные графы не могут содержать нечетные антидыры, индуцированные подграфы, дополнительные к нечетным дыркам: нечетная антидыра с 2 k + 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] Анализ данного случая завершает доказательство.