Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

Доказательство сильной теоремы о совершенном графе принесло его авторам приз в размере 10 000 долларов от Жерара Корнежоля из Университета Карнеги-Меллона [2] и премию Фулкерсона 2009 года . [3]

Заявление [ править ]

Совершенный график представляет собой график , в котором для каждого индуцированного подграфа , размер максимальной клики равно минимальное количество цветов в окраске графа; Совершенные графы включают в себя множество хорошо известных классов графов, включая двудольные графы , хордовые графы и графы сопоставимости . В своих работах 1961 и 1963 годов, впервые определяющих этот класс графов, Клод Берже заметил, что идеальный граф не может содержать нечетную дыру, индуцированный подграф в форме циклического графа нечетной длины.длины пять или больше, потому что нечетные дырки имеют клику номер два и хроматический номер три. Точно так же он заметил, что совершенные графы не могут содержать нечетные антидыры, индуцированные подграфы, дополняющие нечетные дыры: нечетное антидырка с 2 k  + 1 вершиной имеет номер клики k и хроматическое число k  + 1, что снова невозможно для совершенных графов. Графы, не имеющие ни нечетных дыр, ни нечетных антидор, стали известны как графы Берже.

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

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

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

Идеи доказательства [ править ]

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

Пять основных классов совершенных графов, которые образуют базовый случай этого структурного разложения, - это двудольные графы , линейные графы двудольных графов, дополнительные графы двудольных графов, дополнения линейных графов двудольных графов и двойные расщепленные графы. Легко видеть, что двудольные графы совершенны: в любом нетривиальном индуцированном подграфе кликовое и хроматическое число равны двум и, следовательно, оба равны. Совершенство дополнений к двудольным графам и дополнений к линейным графам двудольных графов эквивалентно теореме Кёнига, связывающей размеры максимальных паросочетаний , максимальных независимых множеств и минимальных покрытий вершин.в двудольных графах. Совершенство линейных графов двудольных графов может быть заявлено эквивалентно как факт, что двудольные графы имеют хроматический индекс, равный их максимальной степени , доказанный Кёнигом (1916) . Таким образом, все четыре этих базовых класса идеальны. Графики с двойным разбиением являются родственниками разбитых графиков, которые также можно показать как идеальные. [6]

В этом доказательстве рассматриваются четыре типа разложений: 2-объединения, дополнения к 2-объединениям, сбалансированные косые разбиения и однородные пары.

2-соединение - это разбиение вершин графа на два подмножества с тем свойством, что ребра, охватывающие разрез между этими двумя подмножествами, образуют два непересекающихся по вершинам полных двудольных графов.. Когда граф имеет 2-соединение, он может быть разложен на индуцированные подграфы, называемые «блоками», путем замены одного из двух подмножеств вершин кратчайшим путем в этом подмножестве, которое соединяет один из двух полных двудольных графов с другим; когда такого пути не существует, вместо этого блок формируется путем замены одного из двух подмножеств вершин двумя вершинами, по одной для каждого полного двудольного подграфа. 2-соединение идеально тогда и только тогда, когда оба его блока идеальны. Следовательно, если минимально несовершенный граф имеет 2-соединение, он должен быть равен одному из его блоков, из чего следует, что это должен быть нечетный цикл, а не цикл Берже. По той же причине минимально несовершенный граф, дополнение которого имеет 2-соединение, не может быть Берже. [7]

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

Однородная пара связана с модульным разбиением графа. Это разбиение графа на три подмножества V 1 , V 2 и V 3 таким образом, что V 1 и V 2 вместе содержат не менее трех вершин, V 3 содержит не менее двух вершин, и для каждой вершины v в V 3 и каждое i в {1,2} либо v смежно со всеми вершинами в V i, либо ни с одной из них. Минимально несовершенный граф не может иметь однородную пару.[9] После доказательства сильной гипотезы о совершенном графе Чудновский (2006) упростил ее, показав, что однородные пары могут быть исключены из множества разложений, используемых в доказательстве.

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

Заметки [ править ]

  1. ↑ Mackenzie (2002) ; Cornuéjols (2002) .
  2. Перейти ↑ Mackenzie (2002) .
  3. ^ «Премии Фулкерсона 2009» (PDF) , Уведомления Американского математического общества : 1475–1476, декабрь 2011 г..
  4. ^ Cornuéjols (2002) , гипотеза 5.1.
  5. ^ Рид (1986) ; Хугарди (1991) ; Русу (1997) ; Руссель, Русу и Тюилье (2009) , раздел 4.6 «Первые предположения».
  6. ^ Руссель, Рус и Thuillier (2009) , определение 4,39.
  7. ^ Cornuéjols & Cunningham (1985) ; Cornuéjols (2002) , теорема 3.2 и следствие 3.3.
  8. ^ Сеймур (2006) ; Руссель, Русу и Тюилье (2009) , раздел 4.7 «Косая перегородка»; Cornuéjols (2002) , теоремы 4.1 и 4.2.
  9. ^ Chvátal & Sbihi (1987) ; Cornuéjols (2002) , теорема 4.10.
  10. ^ Cornuéjols (2002) , теоремы 5.4, 5.5 и 5.6; Руссель, Русу и Тюилье (2009) , теорема 4.42.

Ссылки [ править ]

  • Берге, Клод (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..
  • Чудновский, Мария (2006), "Berge триграфы", Журнал теории графов , 53 (1): 1-55, DOI : 10.1002 / jgt.20165 , MR  2245543.
  • Чудновский, Мария ; Робертсон, Нил ; Сеймур, Пол ; Томас, Робин (2006), "Сильная совершенная теорема графа" , Анналы математики , 164 (1): 51-229, Arxiv : математика / 0212070 , DOI : 10,4007 / annals.2006.164.51 , MR  2233847.
  • Чудновский, Мария ; Робертсон, Нил ; Сеймур, Пол ; Томас, Робин (2003), "Прогресс в области совершенных графов", математическое программирование , серия Б., 97 (1-2): 405-422, CiteSeerX  10.1.1.137.3013 , DOI : 10.1007 / s10107-003-0449-8 , MR  2004404.
  • Chvátal, Вацлав (1985), «Звездные сечения и совершенные графы», Журнал комбинаторной теории , серия B, 39 (3): 189–199, DOI : 10.1016 / 0095-8956 (85) 90049-8 , MR  0815391.
  • Хватал, Вацлав ; Sbihi, Наджиб (1987), "Bull свободных графы Berge идеальны", графы и комбинаторика , 3 (2): 127-139, DOI : 10.1007 / BF01788536 , МР  0932129.
  • Корнежоль, Жерар (2002), "Сильная гипотеза совершенного графа", Труды Международного конгресса математиков, Vol. III (Пекин, 2002) (PDF) , Пекин: Высшее изд. Press, стр. 547–559, MR  1957560.
  • Cornuéjols, G .; Cunningham, WH (1985), "Композиция для совершенных графов", Дискретная математика , 55 (3): 245-254, DOI : 10.1016 / S0012-365X (85) 80001-7 , MR  0802663.
  • Hougardy, S. (1991), Контрпримеры к трем гипотезам относительно совершенных графов , Технический отчет RR870-M, Гренобль, Франция: Laboratoire Artemis-IMAG, Universitá Joseph Fourier. Цитируется Roussel, Rusu & Thuillier (2009) .
  • Knig, Dénes (1916), "Gráfok és alkalmazásuk aterminánsok és Halmazok elméletére", Matematikai és Természettudományi Értesítő , 34 : 104–119.
  • Ловас, Ласло (1972a), «Нормальные гиперграфы и гипотеза идеального графа», Дискретная математика , 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.
  • Mackenzie, Дана (5 июля 2002), "Математика: Теория графов раскрывает корни совершенства", Science , 297 (5578): 38, DOI : 10.1126 / science.297.5578.38 , PMID  12098683.
  • Рид, Б.А. (1986), Полусильная теорема о совершенном графе , доктор философии. диссертация, Монреаль, Квебек, Канада: Департамент компьютерных наук, Университет Макгилла. Цитируется Roussel, Rusu & Thuillier (2009) .
  • Руссель, Ф .; Rusu, I .; Thuillier, Х. (2009), "Сильная совершенный граф гипотеза: 40 лет попыток, а его разрешение", дискретная математика , 309 (20): 6092-6113, DOI : 10.1016 / j.disc.2009.05.024 , М.Р.  2552645.
  • Русу, Ирена (1997), "Строительные контрпримеры", дискретная математика , 171 (1-3): 213-227, DOI : 10.1016 / S0012-365X (96) 00081-7 , МР  1454452.
  • Сеймур, Пол (2006), «Как было найдено доказательство сильной гипотезы о совершенном графе» (PDF) , Gazette des Mathématiciens (109): 69–83, MR  2245898.

Внешние ссылки [ править ]

  • Сильная теорема о совершенном графе , Вацлав Хватал
  • Вайсштейн, Эрик В. «Сильная теорема о совершенном графе» . MathWorld .