Сильна теорема про досконалі графи

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

За доведення сильної теореми про досконалі графи автори отримали приз $10,000 від Джерарда Корніджолса з університету Карнегі-Меллон [1] та премію Фалкерсона 2009 [3] .

Твердження теореми[ред. | ред. код]

Досконалий граф — це граф, у якому для будь-якого породженого підграфа розмір найбільшої кліки дорівнює найменшому числу кольорів, необхідних для розфарбовування графа. Досконалі графи включають добре відомі класи графів: двочасткові графи, хордальні графи та графи порівнянності. У працях 1961 і 1963 років, визначаючи вперше цей клас графів, Берж[en] зауважив, що досконалі графи не можуть містити непарної діри, породженого підграфа у формі циклу непарної довжини п'ять або більше, оскільки непарні діри мають клікове число два, а хроматичне число три. Аналогічно, він зауважив, що досконалі графи не можуть містити непарних антидір, породжених підграфів, доповнень непарних дір — непарна антидіра з вершинами має клікове число k та хроматичне число що знову ж неможливо для досконалих графів. Графи, які не мають ні непарних дір, ні непарних антидир, стали відомі як графи Бержа.

Берж висловив припущення, що будь-який граф Бержа досконалий, або, еквівалентно, що досконалі графи та графи Бержа визначають той самий клас графів. Це припущення було відомим як сильна гіпотеза про досконалі графи аж до її доведення 2002 року, коли її перейменовано на сильну теорему про досконалі графи.

Зв'язок зі слабкою теоремою про досконалі графи[ред. | ред. код]

Інша гіпотеза Бержа, яку довів 1972 року Ласло Ловас, стверджує, що доповнення будь-якого досконалого графа також досконале. Теорема стала відомою як теорема про досконалі графи або (щоб відрізняти її від сильної гіпотези/теореми про досконалі графи) слабка теорема про досконалі графи. Оскільки характеризування забороненими графами Бержа самодвоїсте, слабка теорема про досконалі графи випливає негайно із сильної теореми про досконалі графи.

Ідеї доведення[ред. | ред. код]

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

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

Чотири типи декомпозиції, розглянутих у цьому доведенні, — це 2-з'єднання, доповнення 2-з'єднань, збалансовані косі розбиття та однорідні пари.

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

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

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

Доведення, що будь-який граф Бержа потрапляє в один із п'яти класів або має один з чотирьох типів декомпозиції, спирається на розбір окремих випадків, згідно з яким існує певна конфігурація у графі — розтяжка, підграф, який можна розкласти на три породжені шляхи згідно з певними додатковими обмеженнями, доповнення розтяжки та власне колесо, конфігурація, пов'язана з колесом, що складається з породженого циклу разом із центральною вершиною, суміжною щонайменше з трьома вершинами обода і задовольняє деяким додатковим обмеженням. Залежно від того, чи існує всередині заданого графа Бержа розтяжка, доповнення розтяжки або власне колесо, можна показати, що граф належить до одного з базових класів, або може бути підданий декомпозиції[20][21]. Цей аналіз випадків завершує доведення.

Примітки[ред. | ред. код]

  1. ↑ а б Mackenzie, 2002.
  2. ↑ Cornuéjols, 2002.
  3. ↑ 2009 Fulkerson Prizes, 2011, с. 1475–1476.
  4. ↑ Cornuéjols, 2002, с. Гіпотеза 5.1.
  5. ↑ Reed, 1986.
  6. ↑ Hougardy, 1991.
  7. ↑ Rusu, 1997.
  8. ↑ Roussel, Rusu, Thuillier, 2009, с. розділ 4.6 The first conjectures.
  9. ↑ Kőnig, 1916.
  10. ↑ Roussel, Rusu, Thuillier, 2009, с. Визначення 4.39.
  11. ↑ Cornuéjols, Cunningham, 1985.
  12. ↑ Cornuéjols, 2002, с. Теорема 3.2 і наслідок 3.3.
  13. ↑ Chvátal, 1985.
  14. ↑ Seymour, 2006.
  15. ↑ Roussel, Rusu, Thuillier, 2009, с. розділ 4.7 The skew partition.
  16. ↑ Cornuéjols, 2002, с. Теореми 4.1 і 4.2.
  17. ↑ Chvátal, Sbihi, 1987.
  18. ↑ Cornuéjols, 2002, с. Теорема 4.10.
  19. ↑ Chudnovsky, 2006.
  20. ↑ Cornuéjols, 2002, с. Теореми 5.4, 5.5, 5.6.
  21. ↑ Roussel, Rusu, Thuillier, 2009, с. Теорема 4.42.

Література[ред. | ред. код]

Посилання[ред. | ред. код]

Отримано з https://uk.wikipedia.org/w/index.php?title=Сильна_теорема_про_досконалі_графи&oldid=36755082