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

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

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

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

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

Семейства совершенных графов[править | править вики-текст]

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

Связь с теоремами минимакса[править | править вики-текст]

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

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

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

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

Характеристики и теоремы о совершенных графах[править | править вики-текст]

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

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

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

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

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

Алгоритмы на совершенных графах[править | править вики-текст]

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

Многие годы вопрос о вычислительной сложности распознавания графов Бержа и совершенных графов оставался открытым. Из определения графов Бержа немедленно следует, что их распознавание является co-NP сложной задачей (Lovász 1983)[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.

Внешние ссылки[править | править вики-текст]