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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Матрицы, многогранники и целочисленное программирование

Совершенные графы тесно связаны с теорией линейного и целочисленного программирования . И линейные программы, и целочисленные программы выражаются в канонической форме как поиск вектора который максимизирует линейную целевую функцию , при линейных ограничениях и . Здесь, А задается в виде матрицы , и и представлены двумя векторами. Хотя линейные программы и целочисленные программы задаются таким же образом, они отличаются тем, что в линейной программе вектор решения может иметь произвольные действительные числа в качестве коэффициентов, тогда как в целочисленной программе эти неизвестные коэффициенты должны быть целыми числами. Это очень сильно влияет на вычислительную сложность этих задач: линейное программирование можно решить за полиномиальное время , а целочисленное программирование — NP-сложно .

Когда одни и те же заданные значения А ,b , исиспользуются для определения как линейной программы, так и целочисленной программы, они обычно имеют разные оптимальные решения. Линейная программа называется интегральной линейной программой , если оптимальное решение целочисленной программы также является оптимальным для линейной программы. (В противном случае отношение между двумя значениями решения называется разрывом целочисленности и важно при анализе алгоритмов аппроксимации для целочисленной программы.) Совершенные графы могут использоваться для характеристики матриц (0, 1). А (то есть матрицы, где все коэффициенты равны 0 или 1) со следующим свойством: если является вектором всех единиц , то для всех вариантовсполученная линейная программа является интегральной.

Как доказал Вацлав Хватал , каждая матрица А с этим свойством является (с точностью до удаления нерелевантных «доминирующих» строк) максимальной кликой и матрицей инцидентности вершин идеального графа. Эта матрица имеет столбец для каждой вершины графа и строку для каждой максимальной клики с коэффициентом, равным единице в столбцах вершин, принадлежащих клике, и нулю в остальных столбцах. Интегральные линейные программы, закодированные этой матрицей, ищут независимый набор максимального веса данного графа с весами, заданными вектором с .

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

Связанные концепции

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

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

Тривиально совершенный граф

Тривиально совершенный граф — это граф со свойством, что в каждом его порожденном подграфе размер наибольшего (по размеру) независимого множества равен числу наибольших клик . Тривиально совершенные графы первым изучал Волк , но название дал Голумбик . Голумбик писал, что «это название выбрано ввиду тривиальности доказательства, что такие графы совершенны » . Тривиально совершенные графы известны также как графы сравнимости деревьев , древовидные графы сравнимости и квазипороговые графы .

Реберно-совершенный граф

Реберно-совершенный граф — это граф, реберный граф которого совершен . Эквивалентно это графы, в которых каждый простой цикл нечетной длины является треугольником .

Граф является реберно совершенным тогда и только тогда , когда любой из его двухсвязных компонентов является двухчастным графом , полным графом. или книгой треугольников . Поскольку эти три типа двухсвязных компонент сами являются совершенными графами, любой реберно совершенный граф сам совершенен . По той же причине любой реберно совершенный граф является графом четности , графом Мейнеля и вполне упорядоченным графом .

Реберно-совершенные графы обобщают двухчастные графы и разделяют с ними свойства, что наибольшее сопряжение и наименьшее вершинное покрытие имеют одинаковые размеры, а хроматический индекс равен наибольшей степени

Вау!! 😲 Ты еще не читал? Это зря!

• Тривиально совершенный граф
• Реберно-совершенный граф
• Косое разбиение
• Граф Мейнеля
• Сильная теорема о совершенных графах
• Теорема о совершенных графах
• Сжатый граф - граф, в котором любой периферийный цикл является треугольником
• Граф Мейнеля

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