Сильная гипотеза о совершенных графах (Vnl,ugx inhkmy[g k vkfyjoyuud] ijgsg])

Перейти к навигации Перейти к поиску

Сильная гипотеза о совершенных графах — это характеризация запрещёнными графами совершенных графов как в точности тех графов, которые не имеют ни нечётных дыр (порождённых циклов нечётной длины), ни нечётных антидыр (дополнений нечётным дырам). Гипотезу высказал Берж[англ.] в 1961. Доказательство Марии Чудновской[англ.], Нейла Робертсона[англ.], Пола Сеймура и Робина Томаса было заявлено в 2002[1][2] и опубликовано ими в 2006.

За доказательство сильной теоремы о совершенных графах авторы получили приз в $10,000, выставленный Джерардом Корниджолс из университета Карнеги — Меллона[1] и премию Фалкерсона 2009 года[3].

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

[править | править код]

Совершенный граф — это граф, в котором для любого порождённого подграфа размер наибольшей клики равен наименьшему числу цветов, необходимых для раскраски графа. Совершенные графы включают хорошо известные классы графов, такие как двудольные графы, хордальные графы и графы сравнимости. В работах 1961 и 1963 годов, определяя впервые эти классы графов, Берж[англ.] заметил, что совершенные графы не могут содержать нечётную дыру, порождённый подграф в форме цикл нечётной длины пять или более, поскольку нечётные дыры имеют кликовое число два, а хроматическое число три. Аналогично, он заметил, что совершенные графы не могут содержать нечётных антидыр, порождённых подграфов, дополнительных нечётным дырам — нечётная антидыра с вершинами имеет кликовое число k и хроматическое число , что снова невозможно для совершенных графов. Графы, не имеющие ни нечётных дыр, ни нечётных антидыр, стали известны как графы Бержа.

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

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

[править | править код]

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

Идеи доказательства

[править | править код]

Доказательство сильной теоремы о совершенных графах Чудновской с соавторами следует наброску, который предложили в 2001 году Конфорти, Корниджолс, Робертсон, Сеймур и Томас. Согласно этому наброску любой граф Бержа либо образует один из пяти типов базовых блоков (специальные классы совершенных графов), либо имеет одну из четырёх других типов структурных декомпозиций на более простые графы. Минимальный несовершенный граф Бержа не может иметь какую-либо из этих декомпозиций, откуда следует, что контрпример теореме не может существовать[4]. Эта идея была основана на гипотезе о структурной декомпозиции подобных типов, из которой следовала бы сильная гипотеза о совершенных графах, но гипотеза не оказалась справедливой[5][6][7][8].

Пять основных классов совершенных графов, образующих основные случаи этой структурной декомпозиции, это двудольные графы, рёберные графы двудольных графов, дополнения двудольных графов, дополнения рёберных графов двудольных графов и двойные расщепляемые графы. Легко видеть, что двудольные графы совершенны — в любом нетривиальном порождённом подграфе, как кликовое число, так и хроматическое число равны двум. Совершенство дополнений двудольных графов и дополнений рёберных графов двудольных графов эквивалентно теореме Кёнига относительно размеров наибольших паросочетаний, наибольших независимых множеств и наибольших вершинных покрытий в двудольных графах. Совершенство рёберных графов двудольных графов может быть сформулировано эквивалентно как факт, что двудольные графы имеют хроматический индекс, равный их наибольшей степени, что доказал Кёниг[9]. Таким образом, все четыре эти базовых класс совершенны. Двойные расщепляемые графы родственны расщепляемым графам в том, что также можно показать их совершенство[10].

Четыре типа декомпозиции, рассматриваемых в этом доказательстве, — это 2-соединения, дополнения 2-соединений, сбалансированные косые разбиения и однородные пары.

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

Косое разбиение — это разбиение вершин графа на два подмножества, одно из которых пoрождает несвязный подграф, а другое имеет несвязное дополнение. Хватал[13] высказал гипотезу, что никакой минимальный контрпример сильной гипотезе о совершенных графах не может иметь косое разбиение. Чудновская и соавторы ввели некоторые технические ограничения на косые разбиения и смогли показать, что гипотеза Хватала верна для получающихся «сбалансированных косых разбиений». Полная гипотеза является следствием сильной теоремы о совершенных графах[14][15][16].

Однородные пары связаны с модульным разложением графа. Это разложение графа на три подмножества , такие, что и вместе содержат по меньшей мере три вершины, содержит по меньшей мере две вершины, а для каждой вершины v из и любого i из {1,2} либо v смежна всем вершинам в , либо ни одной из них. Невозможно для минимального несовершенного графа иметь однородную пару[17][18]. После доказательства сильной гипотезы о совершенных графах Чудновская[19] упростила доказательство, показав, что однородные пары могут быть исключены из набора декомпозиций, используемых в доказательстве.

Доказательство, что любой граф Бержа попадает в один из пяти классов или имеет один из четырёх типов декомпозиции, следует разбору отдельных случаев, согласно которому существует определённая конфигурация в графе — «растяжка», подграф, который может быть разложен на три порождённые пути согласно определённым дополнительным ограничениям, дополнение растяжки и «собственное колесо», конфигурация, связанная с колесом, состоящим из порождённого цикла вместе центральной вершиной, смежной по меньшей мере с тремя вершинами обода и удовлетворяющей некоторые дополнительные ограничения. В зависимости от того, существует ли растяжка, дополнение к растяжке или собственное колесо внутри заданного графа Бержа, можно показать, что граф принадлежит одному из базовых классов, или может быть подвергнут декомпозиции[20][21]. Этот разбор случаев завершает доказательство.

Примечания

[править | править код]
  1. ↑ 1 2 Mackenzie, 2002.
  2. ↑ Cornuéjols, 2002.
  3. ↑ 2009 Fulkerson Prizes, 2011, с. 1475–1476.
  4. ↑ Cornuéjols, 2002, с. Conjecture 5.1.
  5. ↑ Reed, 1986.
  6. ↑ Hougardy, 1991.
  7. ↑ Rusu, 1997.
  8. ↑ Roussel, Rusu, Thuillier, 2009, с. section 4.6 The first conjectures.
  9. ↑ Kőnig, 1916.
  10. ↑ Roussel, Rusu, Thuillier, 2009, с. Definition 4.39.
  11. ↑ Cornuéjols, Cunningham, 1985.
  12. ↑ Cornuéjols, 2002, с. Theorem 3.2 and Corollary 3.3.
  13. ↑ Chvátal, 1985.
  14. ↑ Seymour, 2006.
  15. ↑ Roussel, Rusu, Thuillier, 2009, с. section 4.7 The skew partition.
  16. ↑ Cornuéjols, 2002, с. Theorems 4.1 and 4.2.
  17. ↑ Chvátal, Sbihi, 1987.
  18. ↑ Cornuéjols, 2002, с. Theorem 4.10.
  19. ↑ Chudnovsky, 2006.
  20. ↑ Cornuéjols, 2002, с. Theorems 5.4, 5.5, 5.6.
  21. ↑ Roussel, Rusu, Thuillier, 2009, с. Theorem 4.42.

Литература

[править | править код]
  • 2009 Fulkerson Prizes // Notices of the American Mathematical Society. — 2011. — Декабрь (т. 57, № 11). — С. 1475–1476. — ISSN 0002-9920.
  • Claude Berge. Färbung von Graphen, deren sämtliche bzw. deren ungerade Kreise starr sind // Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe. — 1961. — Т. 10. — С. 114..
  • Claude Berge. Perfect graphs // Six Papers on Graph Theory. — Calcutta: Indian Statistical Institute, 1963. — С. 1–21.
  • Maria Chudnovsky. Berge trigraphs // Journal of Graph Theory. — 2006. — Т. 53, вып. 1. — С. 1–55. — doi:10.1002/jgt.20165.
  • Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas. The strong // Annals of Mathematics. — 2006. — Т. 164, вып. 1. — С. 51–229. — doi:10.4007/annals.2006.164.51. — arXiv:math/0212070.
  • 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.
  • Václav Chvátal. Star-cutsets and perfect graphs // Journal of Combinatorial Theory. — 1985. — Т. 39, вып. 3. — С. 189–199. — doi:10.1016/0095-8956(85)90049-8..
  • Václav Chvátal, Najiba Sbihi. Bull-free Berge graphs are perfect // Graphs and Combinatorics. — 1987. — Т. 3, вып. 2. — С. 127–139. — doi:10.1007/BF01788536..
  • Gérard Cornuéjols. The strong perfect graph conjecture // Proceedings of the International Congress of Mathematicians, Vol. III (Beijing, 2002). — Beijing: Higher Ed. Press, 2002. — С. 547–559. Архивная копия от 7 апреля 2014 на Wayback Machine
  • Gérard Cornuéjols, Cunningham W. H. Compositions for perfect graphs // Discrete Mathematics. — 1985. — Т. 55, вып. 3. — С. 245–254. — doi:10.1016/S0012-365X(85)80001-7.
  • Hougardy S. Counterexamples to three conjectures concerning perfect graphs. — Grenoble, France: Laboratoire Artemis-IMAG, Universitá Joseph Fourier, 1991. — (Technical Report RR870-M).. Как процитировано в статье Roussel, Rusu, Thuillier (2009).
  • Dénes Kőnig. Gráfok és alkalmazásuk a determinánsok és a halmazok elméletére // Matematikai és Természettudományi Értesítő. — 1916. — Т. 34. — С. 104–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.
  • Dana Mackenzie. Mathematics: Graph theory uncovers the roots of perfection // Science. — 2002. — Июль (т. 297, вып. 5578). — С. 38. — doi:10.1126/science.297.5578.38. — PMID 12098683.
  • Bruce A. Reed. A semi-strong perfect graph theorem. — Montréal, Québec, Canada: Department of Computer Science, McGill University, 1986. — (Ph.D. thesis).. Как процитировано в статье Roussel, Rusu, Thuillier (2009).
  • Roussel F., Rusu I., Thuillier H. The strong perfect graph conjecture: 40 years of attempts, and its resolution // Discrete Mathematics. — 2009. — Т. 309, вып. 20. — С. 6092–6113. — doi:10.1016/j.disc.2009.05.024.
  • Irena Rusu. Building counterexamples // Discrete Mathematics. — 1997. — Т. 171, вып. 1–3. — С. 213–227. — doi:10.1016/S0012-365X(96)00081-7.
  • Paul Seymour. How the proof of the strong perfect graph conjecture was found // Gazette des Mathématiciens. — 2006. — Вып. 109. — С. 69–83.

Ссылки

[править | править код]
Источник — https://ru.wikipedia.org/w/index.php?title=Сильная_гипотеза_о_совершенных_графах&oldid=138734969