Савршен граф

У теорији графова, савршен граф је граф, чији је хроматски број сваког индукованог подграфа једнак величини највеће клике тог подграфа. По јакој теореми о савршеном графу, савршени графови су исто што и Бержови графови. Граф G је Бержов ако ни G ни његов комплемент немају индуковани циклус непарне дужине (5 или више).

Савршени графови укључују многе важне фамилије графова, а служе да се обједине резултати везани за бојење и клике графова тих фамилија. На пример, у свим савршеним графовима, проблем бојења графова, проблем највеће клике и проблем највећег независног скупа могу се решити у полиномијалном времену. Поред тога, неколико важних минимум-максимум теорема из комбинаторике, као што је Дилвортова теорема, могу се изразити преко савршенства одређених графова.

Теорија савршених графова је развијена из резултата рада Тибор Галаја (1958) која се на савременом језику може тумачити као тврдња да је комплемент бипартитивног графа савршен; овај резултат се такође може посматрати као једноставан еквивалент Конигове теореме, много ранијег резултата који се односи на поклапања и покривање чворова у бипартитивним графовима. Прва употреба термина "савршен граф" се наизглед појављује у чланку Клода Бержа из 1963, након кога су и Бержови графови добили име. У овом документу он је објединио Галлаиев резултат са неколико сличних резултата кроз дефинисање савршених графова, и претпоставио је еквивалентност дефиниција савршеног графа и Бержовог графа; Бержова претпоставка је доказана 2002. године као јака теорема о савршеном графу.

Неки од познатијих примера савршених графова:

• Бипартитивни графови, графови који могу бити обојени са две боје, укључујући шуме, графове без циклуса.
• Линијски графови бипартитивних графова (Конигова теорема). Рукови графови (линијски графови комплетних бипартитивних графова) су специјалан случај.
• Тетивни графови, графови код којих сваки циклус од четири или више чвора има тетиву, грану између два чвора који нису суседни у циклусу. У њих спадају шуме, к-дрва, сплит графови (графови који могу бити исечени у клику и независни скуп), блок графови (графови у којима је свака двоструко повезана компонента клика), интервал графови (графови код којих сваки чвор представља интервал линије и свака грана представља непразан пресек два интервала), тривијално савршени графови (интервал графови за угњеждене интервале), праг графови (графови код којих су два чвора суседна када њихова укупна тежина прелази нумерички праг), ветрењача графови (формирани спајањем једнаких клика на заједничком чвору), и јако тетивни графови (тетивни графови у којима сваки парни циклус дужине шест или више има непарну тетиву).
• Упоредни графови формирани од парцијално уређених скупова спајањем парова елемената граном кад год су они у парцијалном уређењу. Они укључују бипартитивне графове, комплементе интервал графова, тривијално савршене графове, праг графове, ветрењача графове, графове пермутација (графови у којима гране представљају парове елемената који су преокренути пермутацијом), и кографови (графови формирани рекурзивним операцијама раздвојене уније и комплементације).
• Перфектно уредиви графови, графови који могу бити уређени тако да алгоритам похлепног бојења буде оптималан за сваки индуковани подграф. Они укључују бипартитивне графове, тетивне графове, упоредне графове, раздаљина-наследне графове (код којих је најкраћа путања у повезаном индукованом подграфу једнака оној у целом графу), и точак графове који имају непаран број чворова.
• Трапезни графови, графови пресека трапеза чији паралелни парови грана леже на две паралелне линије. Они укључују интервал графове, тривијално савршене граофве, праг графове, ветрењача графове и графове пермутација; њихови комплементи су подскуп упоредних графова.

Код свих графова, број клике обезбеђује доњу границу хроматског броја, јер свим чворовима у клики морају бити додељене различите боје. Савршен граф је онај код кога је ова доња граница мала, не само за граф него и за све његове индуковане подграфове. За граф који није савршен, хроматски број и број клике се могу разликовати; на пример, циклус дужине пет захтева три боје за свако право бојење али његова највећа клика је величине два.

Доказ да је класа графова савршена се може посматрати као минимум-максимум теорема; минимални број боја потребан за ове графове једнак је максималној величини клике. Многе важне минимум-максимум теореме у комбинаторици могу бити изражене на овај начин. На пример, Дилвортова теорема тврди да је минимални број ланаца у партицији парцијално уређеног скупа у ланцима једнак максималној величини антиланца, а тврђење се може изразити и овако: комплементи упоредних графова су савршени. Мирскијева теорема тврди да је минимални број антиланаца у партицији једнак највећој величини ланца, и односи се на исти начин са савршеношћу упоредних графова.

Конигова теорема у теорији графова тврди да минимално покривање чворова у бипартитивном графу одговара максималном поклапању и обратно; може бити посматрано као савршеност комплемената бипартитивних графова. Друга теорама о бипартитивним графовима, где њихов хроматски индекс одговара максималном степену, јесте еквивалент савршености линијских графова бипартитивних графова. 

У свом почетном раду над савршеним графовима, Берж је изнео две важне претпоставке о њиховој структури које су тек касније доказане.

Прва од две теореме била је теорема савршеног графа Ловаса (1972), која тврди да је граф савршен ако и само ако је његов комплемент савршен. Стога, савршеност (дефинисана као једнакост величине највеће клике и хроматског броја у сваком индукованом подграфу) јесте еквивалент једнакости величине максималног независног скупа и броја покривања клике.

Друга теорема, која је изнета као Бержова претпоставка, омогућила је забрањену карактеризацију графа савршених графова. Индуковани циклус непарне дужине (минимум 5) назива се непарна рупа. Индуковани подграф који је комплемент непарне рупе назива се непарна антирупа. Непарни циклус дужине веће од 3 не може бити савршен, јер је његов хроматски број три а број његове клике је два. Слично, комплемент непарног циклуса дужине 2k + 1 не може бити савршен, јер је његов хроматски број k + 1, а број његове клике је k. (Алтернативно, несавршеност овог графа следи из теорије савршеног графа и несавршености комплементарног непарног циклуса). Како ови графови нису савршени, сваки савршен граф мора бити Бержов граф, граф без непарних рупа и без непарних антирупа. Берж је претпоставио супротно, да је сваки Бержов граф савршен. Ово је коначно доказано као јака теорема о савршеним графовима Чудновске, Робертсона, Симора и Томаса (2006).

Теорема савршеног графа има кратак доказ, али доказ јаке теореме о савршеним графовима је дуга и техничка, заснована на дубокој структуралној декомпозицији Бержових графова. Сличне технике декомпозиције су такође уродиле плодом у студијама о другим класама графова, нарочито графовима без клешта.

Код свих савршених графова, проблем бојења графа, проблем максималне клике и проблем максималног независног скупа могу бити решени у полиномијалном времену (Гротшел, Ловас и Шривер 1988). Алгоритам у општем случају подразумева употребу елипсоидног метода линеарног програмирања, али ефикаснији комбинаторни елементи су познати за многе специјалне случајеве.

Много година комплексност препознавања Бержових графова и савршених графова је била отворена. Из дефиниције Бержових графова, следи њихово препознавање у co-NP (Ловас 1983). Коначно, након доказа јаке теореме савршених графова, откривен је алгоритам полиномијалног времена (Чудновски, Корнуејолс, Лиу, Симор и Вушковић).

• Berge, Claude (1961). „Färbung von Graphen, deren sämtliche bzw. deren ungerade Kreise starr sind”. Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe. 10: 114. 
• Berge, Claude (1963). „Perfect graphs”. Six Papers on Graph Theory. Calcutta: Indian Statistical Institute. стр. 1—21. 
• Chudnovsky, Maria; Cornuéjols, Gérard; Liu, Xinming; Seymour, Paul; Vušković, Kristina (2005). „Recognizing Berge graphs”. Combinatorica. 25 (2): 143—186. doi:10.1007/s00493-005-0012-8. 
• Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (2006). „The strong perfect graph theorem”. Annals of Mathematics. 164 (1): 51—229. doi:10.4007/annals.2006.164.51. 
• Gallai, Tibor (1958). „Maximum-minimum Sätze über Graphen”. Acta Math. Acad. Sci. Hungar. 9 (3-4): 395—434. doi:10.1007/BF02020271. 
• Golumbic, Martin Charles (1980). „Algorithmic Graph Theory and Perfect Graphs”. Academic Press. ISBN 978-0-444-51530-8. Архивирано из оригинала 22. 05. 2010. г. Приступљено 19. 05. 2016.  Second edition, Annals of Discrete Mathematics 57, Elsevier, 2004.
• Grötschel, Martin; Lovász, László; Schrijver, Alexander (1988). „Geometric Algorithms and Combinatorial Optimization”. Springer-Verlag. . See especially chapter 9, "Stable Sets in Graphs". стр. 273–303.
• Lovász, László (1972). „Normal hypergraphs and the perfect graph conjecture”. Discrete Mathematics. 2 (3): 253—267. doi:10.1016/0012-365X(72)90006-4. 
• Lovász, László (1972). „A characterization of perfect graphs”. Journal of Combinatorial Theory, Series B. 13 (2): 95—98. doi:10.1016/0095-8956(72)90045-7. 
• Lovász, László (1983). „Perfect graphs”. Ур.: Beineke, Lowell W.; Wilson, Robin J. Selected Topics in Graph Theory, Vol. 2. Academic Press. стр. 55—87. ISBN 978-0-12-086202-3. 

• The Strong Perfect Graph Theorem by Václav Chvátal.
• Open problems on perfect graphs, maintained by the American Institute of Mathematics.
• Perfect Problems, maintained by Václav Chvátal.
• Information System on Graph Class Inclusions: perfect graph