Совершенный граф

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

Граф Пэли 9-го порядка, покрашенный тремя цветами. На графе выделена клика из трёх вершин. В этом графе и любом его порождённом подграфе хроматическое число равно кликовому числу. Таким образом он является совершенным графом.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Порождённый цикл нечётной длины как минимум 5 называется дырой нечётной длины. Порождённый подграф, дополнительный нечётной дыре называется нечётной антидырой. Нечётный цикл длины больше 3 не может быть совершенным, поскольку его хроматическое число равно трём, а кликовое число равно двум. Похожим образом, дополнительный граф нечётного цикла длины 2k + 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.
• Chudnovsky, Maria;, Robertson, Neil;, Пол Сеймур, и Робин Томас Vušković, Kristina. Recognizing Berge graphs // Combinatorica. — 2005. — Т. 25, вып. 2. — С. 143—186. — doi:10.1007/s00493-005-0012-8.
• Chudnovsky, Maria;, Robertson, Neil;, Пол Сеймур, и Робин Томас. The strong perfect graph theorem // Annals of Mathematics. — 2006. — Т. 164, вып. 1. — С. 51—229. — doi:10.4007/annals.2006.164.51.
• Gallai, Tibor. Maximum-minimum Sätze über Graphen // Acta Math. Acad. Sci. Hungar. — 1958. — Т. 9, вып. 3—4. — С. 395—434. — doi:10.1007/BF02020271.
• Golumbic, Martin Charles. Algorithmic Graph Theory and Perfect Graphs. — Academic Press, 1980. Архивировано 22 мая 2010 года.
• Lovász, László. Normal hypergraphs and the perfect graph conjecture // Discrete Mathematics. — 1972. — Т. 2, вып. 3. — С. 253—267. — doi:10.1016/0012-365X(72)90006-4.
• Lovász, László. A characterization of perfect graphs // Journal of Combinatorial Theory, Series B. — 1972. — Т. 13, вып. 2. — С. 95—98. — doi:10.1016/0095-8956(72)90045-7.

Ссылки

• The Strong Perfect Graph Theorem страница Вацлава Хватала.
• Open problems on perfect graphs, поддерживается Американским Институтом Математики.
• Perfect Problems, поддерживается Вацлавом Хваталом.
• Information System on Graph Class Inclusions: perfect graph