I grafteorin är en perfekt graf en graf där det kromatiska numret för en genererad subgraf är lika med storleken på den maximala klicken i denna subgraf. Tack vare den rigorösa perfekta grafsatsen har det varit känt sedan 2002 att perfekta grafer är samma sak som Berge-grafer . En graf G är en Berge-graf om varken G eller dess komplement har genererat cykler med udda längd (5 eller fler kanter).
Perfekta grafer inkluderar många viktiga graffamiljer och ger en enhetlighet av de resultat som är förknippade med färgläggning och klick av dessa familjer. Till exempel, i alla perfekta grafer , kan färgningsproblemet , det maximala klickproblemet och det maximala oberoende uppsättningsproblemet lösas i polynomtid . Dessutom kan några viktiga minimaxsatser för kombinatorik , såsom Dilworths teorem , anges i termer av perfekta grafer och några relaterade grafer.
Teorin om perfekta grafer har utvecklats sedan arbetet 1958 av Tibor Galai , vilket i modernt språk kan tolkas som påståendet att komplementet till en tvådelad graf är en perfekt graf. Detta resultat kan ses som en enkel motsvarighet till Königs teorem , ett mycket tidigare resultat på matchningar och vertextäckningar i tvådelade grafer. Den första användningen av termen " perfekt graf " dök upp 1963 i en artikel av Claudy Berge , vilket är varifrån namnet "Berge grafer" kommer. I den här artikeln kombinerade han Galais resultat med några liknande resultat genom att definiera perfekta grafer och förmodade att perfekta grafer och Berge-grafer är likvärdiga. Gissningen bevisades 2002 som en stark perfekt grafsats .
Några av de välkända perfekta graferna är:
I alla grafer ger klicktalet minimigränsen för det kromatiska talet, eftersom i en klick måste alla hörn färgas i olika färger. Perfekta grafer är de vars nedre gräns är exakt inte bara för hela grafen utan också för alla dess genererade subgrafer. För grafer som inte är perfekta kan det kromatiska numret och klicknumret skilja sig åt. Så, till exempel, för en cykel med längd 5, behövs 3 färger, och den maximala klicken har en storlek på 2.
Beviset på att en graf är perfekt kan ses som minimaxsatsen - det minsta antalet färger som krävs för att färga dessa grafer är lika med storleken på den maximala klicken. Många viktiga minimaxsatser inom kombinatorik kan uttryckas i dessa termer. Dilworths teorem säger till exempel att det minsta antalet kedjor när man delar upp en delvis ordnad uppsättning i kedjor är lika med den maximala storleken på antikedjor , och kan omformuleras som att komplementen till jämförbarhetsgrafer är perfekta. Mirskys teorem säger att det minsta antalet antisträngar vid uppdelning i antisträngar är lika med den maximala storleken på kedjor och motsvarar på samma sätt perfektionen av jämförbarhetsgrafer.
Permutationsgrafernas perfektion motsvarar att säga att i vilken sekvens av ordnade element som helst är längden på den största minskande undersekvensen lika med det minsta antalet sekvenser när de är uppdelade i ökande undersekvenser. Erdős-Szekeres sats kan lätt härledas från detta påstående.
Königs teorem i grafteori säger att det minsta vertextäcket för en tvådelad graf motsvarar maximal matchning och vice versa. Det kan tolkas som perfektionen av komplementen till tvådelade grafer. Ett annat teorem om tvådelade grafer, att det kromatiska indexet är lika med den maximala graden av grafen, är ekvivalent med perfektionen av linjegrafen för tvådelade grafer.
I sitt första arbete med perfekta grafer gjorde Berge två viktiga gissningar om deras struktur, och de bevisades senare.
Den första av dessa satser var Laszlo Lovas perfekta grafsats (1972) som påstod att en graf är perfekt om och endast om dess komplement är perfekt. Således är perfektion (definierad som likheten mellan storleken på den maximala klicken och det kromatiska numret i varje genererad subgraf) ekvivalent med den maximala storleken på den oberoende uppsättningen och antalet klickomslag.
Den andra satsen, angiven av Berge som en gissning, gav en karakterisering av förbjudna grafer för en perfekt graf.
En genererad cykel med en udda längd på minst 5 kallas ett udda hål . Den genererade subgrafen som är komplementär till ett udda hål kallas ett udda antihål . En udda cykel med längd större än 3 kan inte vara perfekt, eftersom dess kromatiska nummer är tre och dess klicknummer är två. På liknande sätt kan en ytterligare udda cykelgraf med längden 2k + 1 inte vara perfekt eftersom dess kromatiska nummer är k + 1 och dess klicknummer är k . (Eller imperfektionen i denna graf följer av den perfekta grafsatsen och ofullkomligheten hos komplement till udda cykler). Eftersom dessa grafer inte är perfekta måste varje perfekt graf vara en Berge- graf, en graf utan udda hål och utan udda antihål. Berge förmodade att varje Berge-graf är perfekt. Detta bevisas slutligen av den rigorösa perfekta grafsatsen av Chudnovskaya , Robertson , Semur och Thomas (2006).
Den perfekta grafsatsen har ett kort bevis, men beviset för den starka perfekta grafsatsen är långt och tekniskt svårt. Den är baserad på den strukturella nedbrytningen av Berge-grafer. Besläktade metoder för nedbrytning föddes också som ett resultat av studier av andra klasser av grafer, i synnerhet grafer utan klor .
För alla perfekta grafer kan graffärgningsproblemet , problemet med maximal klick och det maximala oberoende uppsättningsproblemet lösas i polynomtid (Grötschel, Lovász, Schrijver, 1988) [1] . Den allmänna fallalgoritmen använder ellipsoidmetoden för linjär programmering , men kombinatoriska algoritmer kända för många specialfall är mer effektiva.
Under många år förblev frågan om den beräkningsmässiga komplexiteten i att känna igen Berge-grafer och perfekta grafer öppen. Av definitionen av Berge-grafer följer omedelbart att deras igenkänning är en uppgift från co-NP-klassen [2] . Slutligen, efter att ha bevisat den starka perfekta grafsatsen, hittades en polynomalgoritm.