Теорема об идеальном графе

Два взаимодополняющих совершенных графа

В теории графов теорема совершенных графах о Ласло Ловаса ( 1972a , 1972b ) утверждает, что граф совершенен неориентированный тогда и только тогда, когда его граф-дополнение также совершенен. Этот результат был выдвинут Берже ( 1961 , 1963 ), и его иногда называют теоремой о слабом идеальном графе, чтобы отличить его от сильной теоремы о совершенном графе. характеризующие совершенные графы их запрещенными порожденными подграфами .

Заявление

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

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

Теорема об идеальном графе гласит:

Дополнение идеального графа совершенно.

Аналогично, в идеальном графе размер максимального независимого множества равен минимальному количеству клик в кликовом покрытии.

Пример

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

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

Приложения

В нетривиальном двудольном графе оптимальное количество цветов (по определению) равно двум, и (поскольку двудольные графы не содержат треугольников ) максимальный размер клики также равен двум. Кроме того, любой индуцированный подграф двудольного графа остается двудольным. Следовательно, двудольные графы идеальны. В двудольных графах с n - вершинами минимальное кликовое покрытие принимает форму максимального паросочетания вместе с дополнительной кликой для каждой несовпадающей вершины размером n - M , где M - мощность паросочетания. Таким образом, в этом случае из теоремы о совершенном графе следует теорема Кенига о том, что размер максимального независимого множества в двудольном графе также равен n − M , результат, который послужил главным источником вдохновения для формулировки Берже теории совершенных графов.

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

Доказательство Ловаса

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

Учитывая совершенный граф G , Ловас формирует граф G *, заменяя каждую вершину v кликой из t _v вершин, где t _v — количество различных максимальных независимых множеств в G , содержащих v . Можно сопоставить каждое из различных максимальных независимых множеств в G с одним из максимальных независимых множеств в G * таким образом, что все выбранные максимальные независимые множества в G * не пересекаются и каждая вершина G * появляется в единственный выбранный набор; то есть G * имеет раскраску, в которой каждый цветовой класс представляет собой максимально независимое множество. Обязательно эта раскраска является оптимальной раскраской G *. Поскольку G совершенен, то же самое относится и к G *, и, следовательно, он имеет максимальную клику K *, размер которой равен количеству цветов в этой раскраске, что представляет собой количество различных максимальных независимых множеств в G ; обязательно K * содержит отдельного представителя для каждого из этих максимальных независимых множеств. Соответствующее множество K вершин в G (вершины, расширенные клики которых в G * пересекают K *) является кликой в ​​G, обладающей тем свойством, что она пересекает каждое максимальное независимое множество в Г . Следовательно, граф, сформированный из G путем удаления K, имеет число кликового покрытия не более чем на единицу меньше, чем кликовое число G , и число независимости как минимум на одно меньше числа независимости G , и результат следует индукцией по этому числу.

с сильной теоремой о

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

Обобщения

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

Ссылки

• Берге, Клод (1961), «Раскраска графов, все или нечетные круги которых являются жесткими», Научный журнал Университета Мартина Лютера в Галле-Виттенберге, Серия математических и естественных наук (на немецком языке), 10 : 114 .
• Берге, Клод (1963), «Идеальные графики», Шесть статей по теории графов , Калькутта: Индийский статистический институт, стр. 1–21 .
• Кэмерон, К.; Эдмондс, Дж .; Ловас, Л. (1986), «Заметки об идеальных графах», Periodica Mathematica Hungarica , 17 (3): 173–175, doi : 10.1007/BF01848646 , MR   0859346 , S2CID   121018903 .
• Чудновская Мария ; Робертсон, Нил ; Сеймур, Пол ; Томас, Робин (2006), «Сильная теорема о совершенном графе», Annals of Mathematics , 164 (1): 51–229, arXiv : math/0212070 , doi : 10.4007/annals.2006.164.51 , MR   2233847 , S2CID   119151552 .
• Чудновская Мария ; Робертсон, Нил ; Сеймур, Пол ; Томас, Робин (2003), «Прогресс в создании идеальных графов» (PDF) , Mathematical Programming , Series B., 97 (1–2): 405–422, doi : 10.1007/s10107-003-0449-8 , MR   2004404 .
• Галлай, Тибор (1958), «Максимум-минимум Sätze über Graphen», Математический журнал Венгерской академии наук (на немецком языке), 9 (3–4): 395–434, doi : 10.1007/BF02020271 , MR   0124238
• Голумбик, Мартин Чарльз (1980), «3.2. Теорема о совершенном графе», Алгоритмическая теория графов и совершенные графы , Нью-Йорк: Academic Press, стр. 53–58, ISBN  0-12-289260-7 , МР   0562306 .
• Кениг, Денес (1931), «Графики и матрицы», Математические и физические статьи (на венгерском языке), 38 : 116–119.
• Ловас, Ласло (1972a), «Нормальные гиперграфы и гипотеза идеального графа», Discrete Mathematics , 2 (3): 253–267, doi : 10.1016/0012-365X(72)90006-4 .
• Ловас, Ласло (1972b), «Характеристика совершенных графов», Журнал комбинаторной теории , серия B, 13 (2): 95–98, doi : 10.1016/0095-8956(72)90045-7 .
• Рид, Брюс А. (2001), «От гипотезы к теореме», Рамирес Альфонсин, Хорхе Л.; Рид, Брюс А. (ред.), Perfect Graphs , Серия Wiley-Interscience по дискретной математике и оптимизации, Чичестер: Wiley, стр. 13–24, MR   1861356 .