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

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

Теория совершенных графов развивается с работы 1958-го года (англ.) ( , которая на современном языке может быть интерпретирована как утверждение, что дополнение двудольного графа есть совершенный граф. Этот результат можно рассматривать как простой эквивалент теоремы Кёнига , значительно более ранний результат относительно паросочетаний и вершинных покрытий в двудольных графах. Первое применение термина « совершенный граф » появилось в 1963 году в статье (англ.) ( , откуда и появилось название «графы Бержа». В этой статье он объединил результат Галаи с некоторыми похожими результатами путём определения совершенных графов и высказал гипотезу об эквивалентности совершенных графов и графов Бержа. Гипотеза доказана в 2002 году как строгая теорема о совершенных графах .

Семейства совершенных графов

Некоторые из хорошо известных совершенных графов:

• Двудольные графы — граф, который может быть раскрашен в два цвета. Семейство включает леса , графы без циклов.
• Рёберные графы двудольных графов (смотри теорему Кёнига ). Ладейные графы (рёберные графы полных двудольных графов ) являются частным случаем.
• Хордальные графы — графы, у которых любой цикл длины 4 и более вершин имеет хорду , то есть ребро между двумя вершинами цикла, которое не входит в цикл. Этот класс включает леса, "k"-деревья (максимальные графы с заданной древесной шириной ), расщепляемые графы (графы, которые могут быть разделены на клику и независимое множество), блоковые графы (графы, у которых любая компонента двусвязности есть клика), интервальные графы (графы, у которых каждая вершина соответствует отрезку на прямой, а каждое ребро — непустое пересечение отрезков), тривиально совершенные графы (интервальные графы для вложенных интервалов), пороговые графы (графы, в которых две вершины смежны когда их суммарный вес превосходит некий порог), мельницы (образованы объединением одинаковых клик и имеющих одну общую для всех клик точку) и строго хордальные графы (хордальные графы, в которых каждый цикл длины шесть или больше имеет нечётную хорду).
• Граф сравнимости , образованный из частично упорядоченных множеств путём соединения пар элементов ребром, если они связаны частичным порядком. Это семейство включает в себя двудольные графы, дополнения интервальных графов, тривиально совершенные графы, пороговые графы, мельницы, графы перестановки (графы, в которых рёбра соответствуют парам элементов, идущих в обратном порядке) и кографы (графы, образованные рекурсивными операциями объединения непересекающихся графов и дополнением).
• Идеально упорядочиваемые графы — графы, которые можно упорядочить таким образом, что алгоритм жадной раскраски является оптимальным для любого порождённого продграфа. Это семейство включает двудольные графы, хордальные графы, графы сравнимости, дистанционно-наследуемые графы (в которых кратчайшее расстояние в связных порождённых подграфах равно кратчайшему расстоянию в самом графе) и ветряные мельницы , имеющие нечётное число вершин.
• Трапецеидальные графы — графы пересечений трапеций , у которых основания лежат на двух параллельных прямых. Это семейство включает интервальные графы, тривиально совершенные графы, поровые графы, мельницы и графы перестановок. Множество дополнений к этим графам является подмножеством графов сравнимости.

Связь с теоремами минимакса

Во всех графах кликовое число даёт минимальную границу хроматического числа, поскольку в клике все вершины должны быть раскрашены в разные цвета. Совершенные графы – это те, у которых нижняя граница точна не только для всего графа, но и для всех его порождённых подграфов. Для графов, не являющихся совершенными, хроматическое число и кликовое число могут различаться. Так, например, для цикла длины 5 необходимо 3 краски, а максимальная клика имеет размер 2.

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

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

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

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

В своей первой работе о совершенных графах Берж высказал две важные гипотезы об их структуре, и они были доказаны позже.

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

Вторая теорема, высказанная Бержем как гипотеза, обеспечивала характеризацию запрещённых графов для совершенного графа.

Порождённый цикл нечётной длины как минимум 5 называется дырой нечётной длины . Порождённый подграф, дополнительный нечётной дыре называется нечётной антидырой . Нечётный цикл длины больше 3 не может быть совершенным, поскольку его хроматическое число равно трём, а кликовое число равно двум. Похожим образом, дополнительный граф нечётного цикла длины 2 k + 1 не может быть совершенным, поскольку его хроматическое число равно k + 1, а его кликовое число равно k . (Или несовершенство этого графа следует из теоремы о совершенных графах и несовершенства дополнений нечётным циклам). Поскольку эти графы не совершенны, каждый совершенный граф должен быть графом Бержа , графом без нечётных дыр и без нечётных антидыр. Берж высказал обратную гипотезу, что любой граф Бержа совершенен. Это окончательно доказано строгой теоремой о совершенных графах , , Семура , и Томаса (2006).

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

Алгоритмы на совершенных графах

Для всех совершенных графов задача о раскраске графа , задача о максимальной клике и задача о максимальном независимом множестве могут быть решены за полиномиальное время (Grötschel, Lovász, Schrijver, 1988) . Алгоритм для общего случая использует метод эллипсоидов для линейного программирования , но более эффективны комбинаторные алгоритмы, известные для многих специальных случаев.

Многие годы вопрос о вычислительной сложности распознавания графов Бержа и совершенных графов оставался открытым. Из определения графов Бержа немедленно следует, что их распознавание является задачей из класса co-NP . Наконец, после доказательства сильной теоремы о совершенных графах, был найден полиномиальный алгоритм.

Примечания

Литература

• Berge, Claude. Färbung von Graphen, deren sämtliche bzw. deren ungerade Kreise starr sind // Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe. — 1961. — Т. 10 . — С. 114 .
• Berge, Claude. Perfect graphs. — Calcutta: Indian Statistical Institute, 1963. — С. 1—21 .
• , , Пол Сеймур , и Робин Томас Vušković, Kristina. Recognizing Berge graphs // Combinatorica. — 2005. — Т. 25 , вып. 2 . — С. 143—186 . — doi : .
• , , Пол Сеймур , и Робин Томас . // Annals of Mathematics . — 2006. — Т. 164 , вып. 1 . — С. 51—229 . — doi : .
• Gallai, Tibor. Maximum-minimum Sätze über Graphen // Acta Math. Acad. Sci. Hungar. — 1958. — Т. 9 , вып. 3—4 . — С. 395—434 . — doi : .
• Golumbic, Martin Charles. . — Academic Press, 1980. 22 мая 2010 года.
• Lovász, László. Normal hypergraphs and the perfect graph conjecture // Discrete Mathematics . — 1972. — Т. 2 , вып. 3 . — С. 253—267 . — doi : .
• Lovász, László. A characterization of perfect graphs // Journal of Combinatorial Theory, Series B. — 1972. — Т. 13 , вып. 2 . — С. 95—98 . — doi : .

Ссылки

• страница Вацлава Хватала .
• , поддерживается Американским Институтом Математики .
• , поддерживается Вацлавом Хваталом.
• :