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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

  1. Martin Grötschel, László Lovász, Alexander Schrijver. Geometric Algorithms and Combinatorial Optimization. — Springer-Verlag, 1988. — С. 273—303.. Смотрите главу 9, «Stable Sets in Graphs»
  2. Lovász, László. Selected Topics in Graph Theory, Vol. 2 / Beineke, Lowell W.; Wilson, Robin J. (Eds.). — Academic Press, 1983. — С. 55—87.

Литература

Ссылки