Теорема о совершенном графе - Perfect graph theorem

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

утверждение

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

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

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

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

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

пример

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

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

Приложения

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

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

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

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

Учитывая идеальный график г, Ловас образует граф г* заменяя каждую вершину v кликой тv вершины, где тv - количество различных максимальных независимых множеств в г которые содержат v. Возможно соответствие каждому из отдельных максимальных независимых множеств в г с одним из максимальных независимых множеств в г*, таким образом, чтобы выбранный максимальный независимый набор г* все не пересекаются, и каждая вершина г* появляется в единственном выбранном наборе; это, г* имеет расцветку, в которой каждый цветовой класс является максимально независимым набором. Обязательно такая раскраска является оптимальной раскраской г*. Потому что г идеально, так же г*, поэтому имеет максимальную клику K* чей размер равен количеству цветов в этой раскраске, то есть количеству различных максимальных независимых наборов в г; обязательно, K* содержит отдельного представителя для каждого из этих максимальных независимых наборов. Соответствующий набор K вершин в г (вершины, развернутые клики которых в г* пересекаться K*) - это клика в г со свойством, что он пересекает каждое максимальное независимое множество в г. Следовательно, граф, сформированный из г путем удаления K имеет номер покрытия клики не более чем на единицу меньше, чем номер клики г, и число независимости как минимум на единицу меньше числа независимости г, и результат следует индукцией по этому числу.[6]

Связь с сильной теоремой о совершенном графе

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

Обобщения

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

Заметки

  1. ^ Это предположение также было высказано Берже, но доказано лишь много позже Чудновский и др. (2006).
  2. ^ Кениг (1931), позже заново открытый Галлай (1958).
  3. ^ Голумбик (1980), Раздел 5.7, «Раскраска и другие задачи на графах сопоставимости», стр. 132–135.
  4. ^ Увидеть Голумбик (1980), Лемма 3.1 (i) и Рид (2001), Следствие 2.21.
  5. ^ Рид (2001), Лемма 2.20.
  6. ^ Мы следуем здесь изложению доказательства Рид (2001). Голумбик (1980) отмечает, что многие из этих рассуждений были быстро реконструированы Д. Р. Фулкерсон после того, как услышал о результате Ловаса, но не увидел его доказательства.

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