Megoszthatja ismereteit fejlesztésével ( hogyan? ) A megfelelő projektek ajánlásai szerint .
A gráfelméletben a tökéletes gráf egy olyan fogalom, amelyet Claude Berge vezetett be 1960-ban. Ez egy olyan gráf, amelynél az egyes indukált részgráfok kromatikus száma és az indukált részgráfok legnagyobb klikkjének mérete megegyezik.
A sejtések megfogalmazásától az erős tétel bizonyításáig folyamatosan nő az érdeklődés a tökéletes gráfok iránt. A bizonyítás közzététele után sem esett vissza, mivel ennek nagyon nagy technikája és hossza reményt adott egy rövidebb bizonyítás létére, amely megerősíti annak megértését.
A tökéletes gráfok tanulmányozásának két fő motivációja a gráfelméleten kívül a poliéder és az algoritmikus . Ez különösen annak köszönhető, hogy a tökéletes gráf másik egyenértékű meghatározása létezik Václav Chvátal miatt :
„A gráf akkor és csak akkor tökéletes, ha stabil politópját a klikk korlátai határozzák meg . "
Ebből az eredményből kiindulva Martin Grötschel , Lovász László és Alexander Schrijver azt mutatják, hogy tökéletes gráfokban polinomiális időben meg tudjuk oldani a gráf színezésének problémáját , amely egyenlő a maximális stabilitás megtalálásának problémájával, és a maximális klikk megtalálásának problémájával. a gyenge tétel.
Claude Berge két sejtést bocsátott ki, amelyek ezeket a tökéletes grafikonokat jellemzik. 1972-ben és 2002- ben bemutatták őket, és tételekké váltak.
Tétel - A gráf akkor és akkor tökéletes, ha a kiegészítése tökéletes.
Ezt a sejtést 1972 -ben Lovász László bizonyította .
Tétel - A gráf akkor és csak akkor tökéletes, ha sem ő, sem annak kiegészítője nem tartalmaz legalább öt hosszú indukált páratlan ciklust
Ezt a sejtést 2002 -ben Maria Chudnovsky , Neil Robertson , Paul Seymour és Robin Thomas bizonyította .
Az erős tétel triviálisan magában foglalja a gyenge tételt. Valójában a „tökéletes gráftételről” beszélünk az erős tétel implicit kijelölésével .
A következő grafikonok tökéletesek: a kétoldalú gráfok , a vonaldiagramok , a grafikonok és a kordaux grafikonok permutációi , különösen a felosztott gráfok , a Ptolemaiosz -gráfok és az örökletes távolsággráfok .