I grafteori er en perfekt graf en graf , hvor det kromatiske tal for enhver genereret undergraf er lig med størrelsen af den maksimale klik i denne undergraf. Takket være den strenge perfekte grafsætning har det været kendt siden 2002, at perfekte grafer er det samme som Berge-grafer . En graf G er en Berge-graf, hvis hverken G eller dens komplement har genereret cyklusser med ulige længder (5 eller flere kanter).
Perfekte grafer inkluderer mange vigtige familier af grafer og giver ensartethed af resultaterne forbundet med farvelægning og kliker af disse familier. For eksempel, i alle perfekte grafer , kan farveproblemet , det maksimale klikproblem og det maksimale uafhængige sæt-problem løses i polynomisk tid . Derudover kan nogle vigtige minimax-sætninger for kombinatorik , såsom Dilworths sætning , angives i form af perfekte grafer og nogle relaterede grafer.
Teorien om perfekte grafer er blevet udviklet siden arbejdet i 1958 af Tibor Galai , hvilket i moderne sprog kan tolkes som udsagnet om, at komplementet af en todelt graf er en perfekt graf. Dette resultat kan ses som en simpel ækvivalent til Königs teorem , et meget tidligere resultat på matchninger og toppunktsdækninger i todelte grafer. Den første brug af udtrykket " perfekt graf " dukkede op i 1963 i et papir af Claudy Berge , hvorfra navnet "Berge grafer" kommer. I denne artikel kombinerede han Galais resultat med nogle lignende resultater ved at definere perfekte grafer og formodede, at perfekte grafer og Berge-grafer er ækvivalente. Formodningen blev bevist i 2002 som en stærk perfekt grafsætning .
Nogle af de velkendte perfekte grafer er:
I alle grafer giver kliktallet minimumsgrænsen for det kromatiske tal, da alle hjørner i en klike skal farves i forskellige farver. Perfekte grafer er dem, hvis nedre grænse ikke kun er nøjagtig for hele grafen, men også for alle dens genererede undergrafer. For grafer, der ikke er perfekte, kan det kromatiske tal og kliknummeret afvige. Så for eksempel, for en cyklus med længde 5, er der brug for 3 malinger, og den maksimale klike har en størrelse på 2.
Beviset for, at en graf er perfekt, kan ses som minimax-sætningen - det mindste antal farver, der kræves for at farve disse grafer, er lig med størrelsen af den maksimale klike. Mange vigtige minimakssætninger i kombinatorik kan udtrykkes i disse termer. For eksempel angiver Dilworths teorem , at det mindste antal kæder, når man deler et delvist ordnet sæt i kæder, er lig med den maksimale størrelse af antikæder , og kan omformuleres som at angive, at komplementerne af sammenlignelighedsgrafer er perfekte. Mirskys teorem siger, at det mindste antal antistrenge, når de opdeles i antistrenge, er lig med den maksimale størrelse af kæder og svarer på samme måde til perfektionen af sammenlignelighedsgrafer.
Permutationsgrafernes perfektion svarer til at sige, at i enhver sekvens af ordnede elementer er længden af den største faldende undersekvens lig med det mindste antal sekvenser, når den er opdelt i stigende undersekvenser. Erdős-Szekeres-sætningen kan let udledes af denne erklæring.
Königs teorem i grafteori siger, at det mindste toppunktsdækning af en todelt graf svarer til den maksimale matchning og omvendt. Det kan tolkes som perfektionen af komplementerne af todelte grafer. En anden sætning om todelte grafer, at det kromatiske indeks er lig med den maksimale grad af grafen, svarer til perfektionen af linjegrafen for todelte grafer.
I sit første arbejde med perfekte grafer fremsatte Berge to vigtige formodninger om deres struktur, og de blev bevist senere.
Den første af disse sætninger var Laszlo Lovas 'perfekte grafsætning (1972), der sagde, at en graf er perfekt, hvis og kun hvis dens komplement er perfekt. Således er perfektion (defineret som ligheden mellem størrelsen af den maksimale klike og det kromatiske tal i enhver genereret undergraf) ækvivalent med den maksimale størrelse af det uafhængige sæt og antallet af klikomslag.
Den anden sætning, angivet af Berge som en formodning, gav en karakterisering af forbudte grafer for en perfekt graf.
En genereret cyklus med en ulige længde på mindst 5 kaldes et hul med ulige længder . Den genererede undergraf, der er komplementær til et ulige hul, kaldes et ulige antihul . En ulige cyklus af længde større end 3 kan ikke være perfekt, da dens kromatiske tal er tre og dens kliknummer er to. På samme måde kan en yderligere ulige cyklusgraf med længden 2k + 1 ikke være perfekt, fordi dens kromatiske tal er k + 1 og dens kliknummer er k . (Eller ufuldkommenheden af denne graf følger af den perfekte grafsætning og ufuldkommenheden af komplementer til ulige cyklusser). Da disse grafer ikke er perfekte, skal enhver perfekt graf være en Berge -graf, en graf uden ulige huller og uden ulige antihuller. Berge formodede, at hver Berge-graf er perfekt. Dette er endelig bevist af den strenge perfekte grafsætning af Chudnovskaya , Robertson , Semur og Thomas (2006).
Den perfekte grafsætning har et kort bevis, men beviset for den stærke perfekte grafsætning er langt og teknisk vanskeligt. Den er baseret på den strukturelle nedbrydning af Berge-grafer. Beslægtede metoder til nedbrydning blev også født som et resultat af undersøgelsen af andre klasser af grafer, især grafer uden kløer .
For alle perfekte grafer kan graffarveproblemet , det maksimale klikproblem og det maksimale uafhængige sætproblem løses i polynomisk tid (Grötschel, Lovász, Schrijver, 1988) [1] . Den generelle case-algoritme bruger ellipsoidmetoden til lineær programmering , men kombinatoriske algoritmer kendt for mange specielle tilfælde er mere effektive.
I mange år forblev spørgsmålet om den beregningsmæssige kompleksitet ved at genkende Berge-grafer og perfekte grafer åbent. Af definitionen af Berge-grafer følger det umiddelbart, at deres genkendelse er en opgave fra co-NP-klassen [2] . Endelig, efter at have bevist den stærke perfekte grafsætning, blev en polynomiel algoritme fundet.