Идеальный график - Perfect graph

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

В теория графов, а идеальный график это график в которой хроматическое число каждого индуцированный подграф равен порядку наибольшего клика этого подграфа (номер клики ). Эквивалентно выраженный в символических терминах произвольный граф ${\displaystyle G=(V,E)}$ идеально тогда и только тогда, когда для всех ${\displaystyle S\subseteq V}$ у нас есть ${\displaystyle \chi (G[S])=\omega (G[S])}$.

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

Свойства

• Посредством теорема о совершенном графе, график ${\displaystyle G}$ идеально тогда и только тогда, когда его дополнять ${\displaystyle {\bar {G}}}$ идеально.
• Посредством сильная теорема о совершенном графе, совершенные графы такие же, как Графы Берже, какие графики ${\displaystyle G}$ где ни ${\displaystyle G}$ ни ${\displaystyle {\bar {G}}}$ содержит индуцированный цикл нечетной длины 5 и более.

См. Более подробную информацию в разделе ниже.

История

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

Семейства идеальных графов

Некоторые из наиболее известных совершенных графов:^[1]

• Двудольные графы, которые являются графами, которые могут быть цветной с двумя цветами, в том числе леса (графики без циклов).
• Линейные графики двудольных графов (см. Теорема Кёнига ). Графики ладьи (линейные графики полные двудольные графы ) являются частным случаем.
• Хордовые графы, графы, в которых каждый цикл из четырех и более вершин имеет аккорд, ребро между двумя вершинами, которые не идут подряд в цикле. Они включают
  • леса k-деревья (максимальные графы с заданной ширина дерева ),
  • разделить графики (графы, которые можно разбить на клику и независимое множество),
  • блочные графики (графы, в которых каждый двусвязный компонент является кликой),
  • Птолемеевы графы (графики, расстояния которых подчиняются Неравенство Птолемея ),
  • интервальные графики (графики, в которых каждая вершина представляет собой интервал прямой, а каждое ребро представляет собой непустое пересечение двух интервалов),
  • тривиально совершенные графы (интервальные графики для вложенных интервалов), пороговые графики (графы, в которых две вершины смежны, если их общий вес превышает числовой порог),
  • графики ветряных мельниц (образуется объединением равных клик в общей вершине),
  • и сильно хордовые графы (хордовые графы, в которых каждый четный цикл длины шесть и более имеет нечетную хорду).
• Графики сопоставимости сформированный из частично упорядоченные наборы соединяя пары элементов ребром, когда они связаны в частичном порядке. Они включают:
  • двудольные графы, дополнения к интервальным графам, тривиально совершенные графы, пороговые графы, графы ветряных мельниц,
  • графы перестановок (графы, в которых ребра представляют пары элементов, обращенных перестановкой),
  • и кографы (графы, образованные рекурсивными операциями дизъюнктного объединения и дополнения).
• Идеально упорядочиваемые графики, которые представляют собой графы, которые можно упорядочить таким образом, что жадная окраска алгоритм оптимален на каждом индуцированном подграфе. К ним относятся двудольные графы, хордовые графы, графы сопоставимости,
  • дистанционно-наследственные графы (в котором кратчайшие пути в связных индуцированных подграфах равны таковым во всем графе),
  • и колесные графики с нечетным числом вершин.
• Графики трапеции, которые графы пересечений из трапеции чьи параллельные пары ребер лежат на двух параллельных прямых. К ним относятся интервальные графы, тривиально совершенные графы, пороговые графы, графы ветряных мельниц и графы перестановок; их дополнения - это подмножество графиков сопоставимости.

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

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

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

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

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

Характеризации и теоремы об идеальных графах

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

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

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

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

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

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

Характеристика Хайнала не встречает странного п-циклы или их комплектующие для п > 3: нечетный цикл на п > 3 вершины имеют номер клики 2 и число независимости (п − 1)/2. Обратное верно для дополнения, поэтому в обоих случаях продукт п − 1.

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

Во всех совершенных графах задача раскраски графа, проблема максимальной клики, и задача о максимальном независимом множестве все можно решить в полиномиальное время (Грётшель, Ловас и Шрайвер, 1988 г. ). Алгоритм для общего случая включает Число Ловаса этих графов, который (для дополнения данного графа) зажат между хроматическим числом и кликовым числом. Вычисление числа Ловаса можно сформулировать как полуопределенная программа и аппроксимированы численно в полиномиальное время с использованием эллипсоидный метод для линейное программирование. Для идеальных графиков округление этого приближения до целого числа дает хроматическое число и кликовое число за полиномиальное время; максимальное независимое множество можно найти, применив тот же подход к дополнению графа, однако этот метод сложен и имеет высокий полиномиальный показатель. Более эффективные комбинаторные алгоритмы известны во многих частных случаях.

В течение многих лет проблема распознавания графов Берже и совершенных графов оставалась открытой. Из определения графов Берже сразу следует, что их распознавание находится в со-НП (Ловас, 1983). Наконец, после доказательства сильной теоремы о совершенном графе, алгоритм с полиномиальным временем был открыт Чудновским, Корнуейолсом, Лю, Сеймуром и Вушковичем.

использованная литература

1. Уэст, Дуглас Брент, автор. (2017-02-14). Введение в теорию графов. ISBN  9780131437371. OCLC  966410137.

• Берже, Клод (1961). "Färbung von Graphen, deren sämtliche bzw. deren ungerade Kreise starr sind". Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Рейхе. 10: 114.
• Берже, Клод (1963). «Совершенные графики». Шесть статей по теории графов. Калькутта: Индийский статистический институт. С. 1–21.
• Чудновский, Мария; Cornuéjols, Жерар; Лю, Синьминь; Сеймур, Пол; Вушкович, Кристина (2005). «Узнавание графов Берже». Комбинаторика. 25 (2): 143–186. Дои:10.1007 / s00493-005-0012-8.
• Чудновский, Мария; Робертсон, Нил; Сеймур, Пол; Томас, Робин (2006). «Сильная теорема о совершенном графе». Анналы математики. 164 (1): 51–229. arXiv:математика / 0212070. Дои:10.4007 / анналы.2006.164.51.
• Галлай, Тибор (1958). «Максимум-минимум Sätze über Graphen». Acta Math. Акад. Sci. Повесили. 9 (3–4): 395–434. Дои:10.1007 / BF02020271.
• Голумбик, Мартин Чарльз (1980). Алгоритмическая теория графов и совершенные графы. Академическая пресса. ISBN  0-444-51530-5. Архивировано из оригинал на 2010-05-22. Получено 2007-11-21. Второе издание, Annals of Discrete Mathematics 57, Elsevier, 2004.
• Грётшель, Мартин; Ловас, Ласло; Шрайвер, Александр (1988). Геометрические алгоритмы и комбинаторная оптимизация. Springer-Verlag. См. Особенно главу 9 «Устойчивые множества в графах», стр. 273–303.
• Ловас, Ласло (1972). «Нормальные гиперграфы и гипотеза идеального графа». Дискретная математика. 2 (3): 253–267. Дои:10.1016 / 0012-365X (72) 90006-4.
• Ловас, Ласло (1972). «Характеристика совершенных графов». Журнал комбинаторной теории. Серия Б. 13 (2): 95–98. Дои:10.1016/0095-8956(72)90045-7.
• Ловас, Ласло (1983). «Совершенные графики». В Beineke, Lowell W .; Уилсон, Робин Дж. (Ред.). Избранные темы теории графов, Vol. 2. Академическая пресса. С. 55–87. ISBN  0-12-086202-6.

внешние ссылки

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