В теории графовсовершенным графом называется граф, в котором хроматическое число любого порождённого подграфа равно размеру максимальной клики этого подграфа. Благодаря строгой теореме о совершенных графах, с 2002 года известно, что совершенные графы — это то же самое, что и графы Бержа. Граф G является графом Бержа если ни G, ни его дополнение не имеет порождённых циклов нечётной длины 5 и более рёбер.
Совершенные графы включают много важных семейств графов и обеспечивают унификацию результатов, связанных с раскраской и кликами этих семейств. Например, во всех совершенных графах задача раскраски, задача о максимальной клике и задача о максимальном независимом множестве могут быть решены за полиномиальное время. Вдобавок, некоторые важные минимаксные теоремы комбинаторики, такие как теорема Дилуорса, могут быть сформулированы в терминах совершенных и некоторых связанных с ними графов.
Теория совершенных графов развивается с работы 1958 года Тибора Галаи[англ.], которая на современном языке может быть интерпретирована как утверждение, что дополнениедвудольного графа есть совершенный граф. Этот результат можно рассматривать как простой эквивалент теоремы Кёнига, значительно более ранний результат относительно паросочетаний и вершинных покрытий в двудольных графах. Первое применение термина «совершенный граф» появилось в 1963 году в статье Клода Бержа[англ.], откуда и появилось название «графы Бержа». В этой статье он объединил результат Галаи с некоторыми похожими результатами путём определения совершенных графов и высказал гипотезу об эквивалентности совершенных графов и графов Бержа. Гипотеза доказана в 2002 году как строгая теорема о совершенных графах.
Семейства совершенных графов
Некоторые из хорошо известных совершенных графов:
- Двудольные графы — граф, который может быть раскрашен в два цвета. Семейство включает леса, графы без циклов.
- Рёберные графы двудольных графов (смотри теорему Кёнига). Ладейные графы (рёберные графы полных двудольных графов) являются частным случаем.
- Хордальные графы — графы, у которых любой цикл длины 4 и более вершин имеет хорду , то есть ребро между двумя вершинами цикла, которое не входит в цикл. Этот класс включает леса, "k"-деревья (максимальные графы с заданной древовидной шириной), расщепляемые графы (графы, которые могут быть разделены на клику и независимое множество), блоковые графы (графы, у которых любая компонента двусвязности есть клика), интервальные графы (графы, у которых каждая вершина соответствует отрезку на прямой, а каждое ребро — непустое пересечение отрезков), тривиально совершенные графы (интервальные графы для вложенных интервалов), пороговые графы (графы, в которых две вершины смежны когда их суммарный вес превосходит некий порог), мельницы (образованы объединением одинаковых клик и имеющих одну общую для всех клик точку) и строго хордальные графы (хордальные графы, в которых каждый цикл длины шесть или больше имеет нечётную хорду).
- Граф сравнимости, образованный из частично упорядоченных множеств путём соединения пар элементов ребром, если они связаны частичным порядком. Это семейство включает в себя двудольные графы, дополнения интервальных графов, тривиально совершенные графы, пороговые графы, мельницы, графы перестановки (графы, в которых рёбра соответствуют парам элементов, идущих в обратном порядке) и кографы (графы, образованные рекурсивными операциями объединения непересекающихся графов и дополнением).
- Идеально упорядочиваемые графы — графы, которые можно упорядочить таким образом, что алгоритм жадной раскраски является оптимальным для любого порождённого продграфа. Это семейство включает двудольные графы, хордальные графы, графы сравнимости, дистанционно-наследуемые графы (в которых кратчайшее расстояние в связных порождённых подграфах равно кратчайшему расстоянию в самом графе) и ветряные мельницы, имеющие нечётное число вершин.
- Трапецеидальные графы — графы пересеченийтрапеций, у которых основания лежат на двух параллельных прямых. Это семейство включает интервальные графы, тривиально совершенные графы, поровые графы, мельницы и графы перестановок. Множество дополнений к этим графам является подмножеством графов сравнимости.
Связь с теоремами минимакса
Во всех графах кликовое число даёт минимальную границу хроматического числа, поскольку в клике все вершины должны быть раскрашены в разные цвета. Совершенные графы – это те, у которых нижняя граница точна не только для всего графа, но и для всех его порождённых подграфов. Для графов, не являющихся совершенными, хроматическое число и кликовое число могут различаться. Так, например, для цикла длины 5 необходимо 3 краски, а максимальная клика имеет размер 2.
Доказательство, что граф совершенен можно рассматривать как теорему минимакса — минимальное число цветов, требуемых для раскраски этих графов, равно размеру максимальной клики. Множество важных минимаксных теорем комбинаторики можно выразить в этих терминах. Например, теорема Дилуорса утверждает, что минимальное число цепей при делении частично упорядоченного множества на цепи равно максимальному размеру антицепей, и может быть перефразирован как утверждение, что дополнения графов сравнимости совершенны. Теорема Мирского утверждает, что минимальное число антицепочек при разделении на антицепочки равно максимальному размеру цепочек и соответствует тем же самым образом совершенству графов сравнимости.
Совершенство графов перестановки эквивалентно утверждению, что в любой последовательности упорядоченных элементов длина наибольшей убывающей подпоследовательности равна минимальному числу последовательностей при разделении на возрастающие подпоследовательности. Теорема Эрдёша — Секереша легко выводится из этого утверждения.
Теорема Кёнига в теории графов утверждает, что минимальное вершинное покрытие двудольного графа соответствует максимальному паросочетанию и наоборот. Её можно интерпретировать как совершенство дополнений двудольных графов. Другая теорема о двудольных графах, о том что хроматический индексравен максимальной степени графа, эквивалентна совершенству рёберного графа двудольных графов.
Характеристики и теоремы о совершенных графах
В своей первой работе о совершенных графах Берж высказал две важные гипотезы об их структуре, и они были доказаны позже.
Первая из этих теорем была теорема о совершенных графахЛасло Ловаса (1972) утверждающая, что граф совершенен тогда и только тогда, когда его дополнение совершенно. Таким образом, совершенство (определённое как равенство размера максимальной клики и хроматического числа в любом порождённом подграфе) эквивалентно максимуму размера независимого множества и числа кликового покрытия.
Вторая теорема, высказанная Бержем как гипотеза, обеспечивала характеризацию запрещённых графов для совершенного графа.
Порождённый цикл нечётной длины как минимум 5 называется дырой нечётной длины. Порождённый подграф, дополнительный нечётной дыре называется нечётной антидырой. Нечётный цикл длины больше 3 не может быть совершенным, поскольку его хроматическое число равно трём, а кликовое число равно двум. Похожим образом, дополнительный граф нечётного цикла длины 2k + 1 не может быть совершенным, поскольку его хроматическое число равно k + 1, а его кликовое число равно k. (Или несовершенство этого графа следует из теоремы о совершенных графах и несовершенства дополнений нечётным циклам). Поскольку эти графы не совершенны, каждый совершенный граф должен быть графом Бержа, графом без нечётных дыр и без нечётных антидыр. Берж высказал обратную гипотезу, что любой граф Бержа совершенен. Это окончательно доказано строгой теоремой о совершенных графахЧудновской[англ.], Робертсона[англ.], Семура, и Томаса (2006).
Теорема о совершенных графах имеет короткое доказательство, но доказательство сильной теоремы о совершенных графах длинно и технически сложно. Оно основывается на структурной декомпозиции графов Бержа. Близкие методы декомпозиции родились также в результате изучения других классов графов, в частности, графов без клешней.
Алгоритмы на совершенных графах
Для всех совершенных графов задача о раскраске графа, задача о максимальной клике и задача о максимальном независимом множестве могут быть решены за полиномиальное время (Grötschel, Lovász, Schrijver, 1988)[1]. Алгоритм для общего случая использует метод эллипсоидов для линейного программирования, но более эффективны комбинаторные алгоритмы, известные для многих специальных случаев.
Многие годы вопрос о вычислительной сложности распознавания графов Бержа и совершенных графов оставался открытым. Из определения графов Бержа немедленно следует, что их распознавание является задачей из класса co-NP[2]. Наконец, после доказательства сильной теоремы о совершенных графах, был найден полиномиальный алгоритм.
Примечания
- ↑Martin Grötschel, László Lovász, Alexander Schrijver.Geometric Algorithms and Combinatorial Optimization. — Springer-Verlag, 1988. — С. 273—303.. Смотрите главу 9, «Stable Sets in Graphs»
- ↑Lovász, László. Selected Topics in Graph Theory, Vol. 2 / Beineke, Lowell W.; Wilson, Robin J. (Eds.). — Academic Press, 1983. — С. 55—87.
Литература
- 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
