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

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

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

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

Граф является 1-совершенным , если и только если . Тогда идеально тогда и только тогда, когда каждый подграф 1-совершенен. ${\ displaystyle G}$${\ Displaystyle \ чи (G) = \ омега (G)}$${\ displaystyle G}$${\ displaystyle G}$

Характеристики

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

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

История

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

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

Некоторые из наиболее известных идеальных графиков:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Берже, Клод (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.
• Чудновский, Мария ; Корнежоль, Жерар ; Лю, Синьминь; Сеймур, Пол ; Вушкович, Кристина (2005). «Узнавание графов Берже» . Combinatorica . 25 (2): 143–186. DOI : 10.1007 / s00493-005-0012-8 . S2CID  2229369 .
• Чудновский, Мария ; Робертсон, Нил ; Сеймур, Пол ; Томас, Робин (2006). «Сильная теорема о совершенном графе» . Анналы математики . 164 (1): 51–229. arXiv : math / 0212070 . DOI : 10.4007 / анналы.2006.164.51 . S2CID  119151552 .
• Галлай, Тибор (1958). «Максимум-минимум Sätze über Graphen» . Acta Mathematica Academiae Scientiarum Hungaricae . 9 (3–4): 395–434. DOI : 10.1007 / BF02020271 . S2CID  123953062 .
• Голумбик, Мартин Чарльз (1980). Алгоритмическая теория графов и совершенные графы . Академическая пресса. ISBN 0-444-51530-5. Архивировано из оригинала на 2010-05-22 . Проверено 21 ноября 2007 . Второе издание, Annals of Discrete Mathematics 57, Elsevier, 2004.
• Грёчель, Мартин ; Ловас, Ласло ; Шрайвер, Александр (1988). Геометрические алгоритмы и комбинаторная оптимизация . Springer-Verlag. См. Особенно главу 9 «Устойчивые множества в графах», стр. 273–303.
• Ловас, Ласло (1972). «Нормальные гиперграфы и гипотеза идеального графа» . Дискретная математика . 2 (3): 253–267. DOI : 10.1016 / 0012-365X (72) 90006-4 .
• Ловас, Ласло (1972). «Характеристика совершенных графов» . Журнал комбинаторной теории . Серия Б. 13 (2): 95–98. DOI : 10.1016 / 0095-8956 (72) 90045-7 .
• Ловас, Ласло (1983). «Совершенные графики». В Beineke, Lowell W .; Уилсон, Робин Дж. (Ред.). Избранные темы теории графов, Vol. 2 . Академическая пресса. С. 55–87. ISBN 0-12-086202-6.

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

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