Теорема о совершенных графах

Теорема о совершенных графах Ловаша[1][2] утверждает, что неориентированный граф является совершенным тогда и только тогда, когда его дополнение также совершенно. Это утверждение высказал в виде гипотезы Берж[3][4] и утверждение называют иногда слабой теоремой о совершенных графах, чтобы не смешивать со строгой теоремой о совершенных графах[5], описывающей совершенные графы их запрещёнными порождёнными подграфами.

Утверждение теоремы

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

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

Теорема о совершенных графах утверждает:

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

Эквивалентная формулировка: В совершенном графе размер наибольшего независимого множества равен минимальному числу клик в кликовом покрытии.

Пример

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

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

Приложения

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

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

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

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

Если задан совершенный граф G, Ловаш образует граф G* путём замены каждой вершины v кликой с tv вершинами, где tv является числом различных максимальных различных множеств в G, содержащих v. Можно сопоставить каждой из различных максимальных независимых множеств из G максимальное независимое множество в G* таким образом, что независимые множества в G* все не будут пересекаться и каждая вершина G* появляется в единственном выбранном множестве. То есть G* имеет раскраску, в которой каждый класс цвета является максимальным независимым множеством. Необходимым образом эта раскраска будет оптимальной раскраской G*. Поскольку G совершенен, таковым является и G*, а тогда он имеет максимальную клику K*, размер которой равен числу цветов в этой раскраске, что равно числу различных максимальных независимых множеств в G. Необходимым образом K* содержит различные представления для каждого из этих максимальных множеств. Соответствующее множество K вершин в G (вершин, расширенные клики которых в G* пересекают K*) является кликой в G со свойством, что оно пересекает любое максимальное независимое множество в G. Таким образом, граф, образованный из G путём удаления K, имеет число кликового покрытия, не превосходящее кликового числа графа G без единицы, а число независимости по меньшей мере на единицу меньше числа независимости графа G. Результат следует из индукции по этому числу [10]

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

Сильная теорема о совершенных графах Чудновской, Робертсона, Сеймура и Томаса[11] утверждает, что граф является совершенным тогда и только тогда, когда ни один из порождённых подграфов не является циклом нечётной длины, большей либо равной пяти, а также не является дополнением такого цикла. Поскольку такое описание нечувствительно к операции дополнения графа, отсюда немедленно следует слабая теорема о совершенных графах.

Обобщения

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

Примечания

  1. ↑ Lovász, 1972a.
  2. ↑ Lovász, 1972b.
  3. ↑ Berge, 1961.
  4. ↑ Berge, 1963.
  5. ↑ Её сформулировал в виде гипотезы также Берж, но доказана она была много позже Чудновской, Робертсоном, Сеймуром и Томасом (Chudnovsky, Robertson, Seymour, Thomas 2006).
  6. ↑ Kőnig, 1931; Позднее теорему переоткрыл Галаи Gallai, 1958.
  7. ↑ Golumbic, 1980, с. 132–135, Section 5.7, "Coloring and other problems on comparability graphs".
  8. ↑ См. книгу Колумбика (Golumbic 1980), Lemma 3.1(i), и Рида (Reed 2001), Corollary 2.21.
  9. ↑ Reed, 2001, с. Lemma 2.20.
  10. ↑ Мы изложили доказательство согласно Риду (Reed 2001). Колумбик (Golumbic 1980) заметил, что большинство из приведённых доводов были быстро получены Фулкерсоном, когда он прослушал доклад Ловаша, но даже не видел его доказательство.
  11. ↑ Chudnovsky, Robertson, Seymour, Thomas, 2006.
  12. ↑ Cameron, Edmonds, Lovász, 1986.

Литература

  • Claude Berge. Färbung von Graphen, deren sämtliche beziehungsweise deren ungerade Kreise starr sind (нем.) // Wissenschaftliche Zeitschrift der Martin-Luther-Universität Halle-Wittenberg, Mathematisch-naturwissenschaftliche Reihe. — 1961. — Bd. 10. — S. 114.
  • Claude Berge. Perfect graphs // Six Papers on Graph Theory. — Calcutta: Indian Statistical Institute, 1963. — С. 1–21.
  • K. Cameron, J. Edmonds, L. Lovász. A note on perfect graphs // Periodica Mathematica Hungarica. — 1986. — Т. 17, вып. 3. — С. 173–175. — doi:10.1007/BF01848646.
  • Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas. The strong perfect graph theorem // Annals of Mathematics. — 2006. — Т. 164, вып. 1. — С. 51–229. — doi:10.4007/annals.2006.164.51.
  • Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas. Progress on perfect graphs // Mathematical Programming. — 2003. — Т. 97, вып. 1-2. — С. 405–422. — doi:10.1007/s10107-003-0449-8.
  • Tibor Gallai. Maximum-minimum Sätze über Graphen (нем.) // Acta Mathematica Academiae Scientiarum Hungarica. — 1958. — Bd. 9, H. 3-4. — S. 395–434. — doi:10.1007/BF02020271.
  • Martin Charles Golumbic. 3.2. The perfect graph theorem // Algorithmic Graph Theory and Perfect Graphs. — New York: Academic Press, 1980. — С. 53–58. — ISBN 0-12-289260-7.
  • Dénes Kőnig. Gráfok és mátrixok (венг.) // Matematikai és Fizikai Lapok. — 1931. — Köt. 38. — O. 116–119.
  • László Lovász. Normal hypergraphs and the perfect graph conjecture // Discrete Mathematics. — 1972a. — Т. 2, вып. 3. — С. 253–267. — doi:10.1016/0012-365X(72)90006-4.
  • László Lovász. A characterization of perfect graphs // Journal of Combinatorial Theory. — 1972b. — Т. 13, вып. 2. — С. 95–98. — doi:10.1016/0095-8956(72)90045-7.
  • Bruce Reed. From conjecture to theorem // Perfect Graphs / Jorge L. Ramírez Alfonsín, Bruce A. Reed. — Chichester: Wiley, 2001. — С. 13–24. — (Wiley-Interscience Series on Discrete Mathematics and Optimization).