A gráfelméletben a tökéletes gráf olyan gráf , amelyben bármely generált részgráf kromatikus száma megegyezik az adott részgráf maximális klikkjének méretével . A szigorú tökéletes gráftételnek köszönhetően 2002 óta ismert, hogy a tökéletes gráfok megegyeznek a Berge-gráfokkal . A G gráf Berge-gráf, ha sem G, sem komplementere nem generált páratlan hosszúságú ciklusokat (5 vagy több él).
A tökéletes grafikonok sok fontos grafikoncsaládot tartalmaznak, és egyesítik az e családok színezésével és klikkjeivel kapcsolatos eredményeket. Például az összes tökéletes gráfban a színezési probléma , a maximális klikk és a maximális független halmaz probléma megoldható polinomiális időben . Ezenkívül a kombinatorika néhány fontos minimax tétele , mint például a Dilworth -tétel , tökéletes gráfok és néhány kapcsolódó gráf formájában is megfogalmazható.
A tökéletes gráfok elméletét Galai Tibor 1958-as munkája óta fejlesztette ki , amely a mai nyelven úgy is értelmezhető, hogy a kétrészes gráf komplementere tökéletes gráf. Ez az eredmény König tételének egyszerű megfelelőjének tekinthető , amely egy sokkal korábbi eredmény a bipartit gráfok illesztéseire és csúcslefedésére. A „ tökéletes grafikon ” kifejezés első használata 1963 -ban jelent meg Claudy Berge cikkében , innen származik a „Berge graphs” elnevezés is. Ebben a cikkben egyesítette Galai eredményét néhány hasonló eredménnyel tökéletes gráfok meghatározásával, és azt sejtette, hogy a tökéletes gráfok és a Berge-gráfok egyenértékűek. A sejtést 2002 - ben erős tökéletes gráftételként bizonyították .
Néhány jól ismert tökéletes gráf:
Minden gráfban a klikkszám adja meg a kromatikus szám minimális korlátját, mivel egy klikkben minden csúcsot különböző színnel kell kiszínezni. A tökéletes gráfok azok, amelyek alsó korlátja nem csak a teljes gráfra, hanem az összes generált részgráfjára is pontos. A nem tökéletes grafikonok esetében a kromatikus szám és a klikkszám eltérhet. Tehát például egy 5 hosszúságú ciklushoz 3 festékre van szükség, és a maximális kattintás mérete 2.
A gráf tökéletességének bizonyítéka a minimax tételként fogható fel – a grafikonok színezéséhez szükséges minimális színek száma megegyezik a maximális klikk méretével. A kombinatorika számos fontos minimax-tétele kifejezhető ezekkel a kifejezésekkel. Például Dilworth tétele kimondja, hogy a láncok minimális száma, amikor egy részlegesen rendezett halmazt láncokra osztunk, megegyezik az antiláncok maximális méretével , és átfogalmazható úgy, hogy az összehasonlíthatósági gráfok komplementerei tökéletesek. tétele kimondja, hogy az antisztringek minimális száma antisztringekre osztáskor egyenlő a láncok maximális méretével, és ugyanúgy megfelel az összehasonlíthatósági gráfok tökéletességének.
A permutációs gráfok tökéletessége egyenértékű azzal, hogy a rendezett elemek bármely sorozatában a legnagyobb csökkenő részsorozat hossza egyenlő a sorozatok minimális számával, ha növekvő részsorozatokra osztjuk. Ebből az állításból könnyen levezethető az Erdős-Szekeres tétel .
König tétele a gráfelméletben kimondja, hogy egy bipartit gráf minimális csúcsfedése megfelel a maximális illeszkedésnek és fordítva. Kétrészes gráfok komplementereinek tökéletességeként értelmezhető. A bipartit gráfokra vonatkozó másik tétel, miszerint a kromatikus index egyenlő a gráf maximális fokával, ekvivalens a bipartit gráfok vonalgráfjának tökéletességével.
A tökéletes gráfokról szóló első munkájában Berge két fontos sejtést fogalmazott meg a szerkezetükről, amelyeket később be is igazoltak.
Az első tétel Lovas László tökéletes gráftétele volt (1972), amely szerint a gráf akkor és csak akkor tökéletes, ha a komplementere tökéletes. Így a tökéletesség (amelyet a maximális klikk méretének és a kromatikus számnak az egyenlősége bármely generált részgráfban) ekvivalens a független halmaz maximális méretével és a klikkfedő számával.
A Berge által sejtésként megfogalmazott második tétel a tiltott gráfok jellemzését adta tökéletes gráfhoz.
A legalább 5 páratlan hosszúságú generált ciklust páratlan hosszúságú lyuknak nevezzük . A páratlan lyukkal komplementer generált részgráfot páratlan antilyuknak nevezzük . Egy 3-nál hosszabb páratlan ciklus nem lehet tökéletes, mivel kromatikus száma három, klikkszáma pedig kettő. Hasonlóképpen, egy további 2k + 1 hosszúságú páratlan ciklusú gráf nem lehet tökéletes, mert kromatikus száma k + 1, klikkszáma pedig k . (Vagy ennek a gráfnak a tökéletlensége a tökéletes gráftételből és a páratlan ciklusok komplementereinek tökéletlenségéből következik). Mivel ezek a gráfok nem tökéletesek, minden tökéletes gráfnak Berge -gráfnak kell lennie, páratlan lyukak és páratlan antilyukak nélküli gráfnak. Berge úgy sejtette, hogy minden Berge-gráf tökéletes. Ezt végül Chudnovskaya , Robertson , Semur és Thomas (2006) szigorú tökéletes gráftétele bizonyítja.
A tökéletes gráftételnek van egy rövid bizonyítása, de az erős tökéletes gráftétel bizonyítása hosszú és technikailag nehéz. A Berge-gráfok szerkezeti dekompozícióján alapul. Más gráfosztályok, különösen a karmok nélküli gráfok tanulmányozása eredményeként születtek ehhez kapcsolódó dekompozíciós módszerek is .
Minden tökéletes gráf esetén a gráf színezési probléma , a maximális klikk probléma és a maximális független halmaz probléma megoldható polinomiális időben (Grötschel, Lovász, Schrijver, 1988) [1] . Az általános esetalgoritmus az ellipszoid módszert használja a lineáris programozáshoz , de a sok speciális esetre ismert kombinatorikus algoritmusok hatékonyabbak.
Sok éven át nyitva maradt a Berge-gráfok és a tökéletes gráfok felismerésének számítási bonyolultságának kérdése. A Berge-gráfok definíciójából azonnal következik, hogy felismerésük a co-NP osztály feladata [2] . Végül az erős tökéletes gráftétel bizonyítása után egy polinomiális algoritmust találtunk.