Perfekt graf - Perfect graph

Den Paley graf av ordning 9, färgad med tre färger och visande en klick av tre hörn. I denna graf och var och en av dess inducerade undergrafer är det kromatiska talet lika med klickantalet, så det är en perfekt graf.

I grafteori är en perfekt graf en graf där det kromatiska antalet för varje inducerad subgraf är lika med storleken på den största klicken i den undergrafen ( klicknummer ). Likvärdigt uttryckt i symboliska termer är en godtycklig graf perfekt om och bara om vi har allt .

De perfekta graferna innehåller många viktiga familjer av grafer och tjänar till att förena resultat som rör färgningar och klickningar i dessa familjer. Till exempel, i alla perfekta grafer, kan graffärgningsproblemet , maximalt klickproblem och maximalt oberoende setproblem alla lösas på polynomtid . Dessutom kan flera viktiga min-max-satser i kombinatorik , såsom Dilworths sats , uttryckas i perfektion av vissa associerade grafer.

En graf är 1-perfekt om och bara om . Då är det perfekt om och bara om varje undergraf av är 1-perfekt.

Egenskaper

  • Med den perfekta grafsatsen är en graf perfekt om och bara om dess komplement är perfekt.
  • Med den starka perfekta grafsatsen är perfekta grafer samma som Berge -grafer, som är grafer där varken eller innehåller en inducerad cykel med udda längd 5 eller mer.

Se avsnittet nedan för mer information.

Historia

Teorin om perfekta grafer utvecklades från ett resultat från Tibor Gallai från 1958 som i det moderna språket kan tolkas som att kompletteringen av en tvåpartig graf är perfekt; detta resultat kan också ses som en enkel motsvarighet till Kőnigs sats , ett mycket tidigare resultat som rör matchningar och toppunktsöverdrag i bipartitdiagram. Den första användningen av frasen "perfekt graf" verkar vara i ett 1963 -blad av Claude Berge , efter vilket Berge -grafer är uppkallade. I denna uppsats förenade han Gallais resultat med flera liknande resultat genom att definiera perfekta grafer, och han gissade likvärdigheten mellan den perfekta grafen och Berge -grafdefinitionerna; hans gissning bevisades 2002 som den starka perfekta grafsatsen .

Familjer med grafer som är perfekta

Några av de mer välkända perfekta graferna är:

  • Bipartitgrafer , som är grafer som kan färgläggas med två färger, inklusive skogar (grafer utan cykler).
  • Linjediagram över tvåpartsgrafer (se Kőnigs sats ). Rooks grafer (linjediagram över kompletta bipartitgrafer ) är ett specialfall.
  • Ackordgrafer , graferna där varje cykel med fyra eller flera hörn har ett ackord , en kant mellan två hörn som inte är på varandra följande i cykeln. Dessa inkluderar
  • Jämförbarhetsdiagram som bildas från delvis ordnade uppsättningar genom att ansluta elementpar med en kant när de är relaterade i delordningen. Dessa inkluderar:
    • bipartitgrafer, komplement till intervallgrafer, trivialt perfekta grafer, tröskelgrafer, väderkvarngrafer,
    • permutationsgrafer (grafer där kanterna representerar par av element som är omvända av en permutation),
    • och cographs (grafer som bildas av rekursiva operationer av disjoint union och komplement).
  • Perfekt beställbara grafer , som är grafer som kan ordnas på ett sådant sätt att en girig färgalgoritm är optimal på varje inducerad undergraf. Dessa inkluderar bipartitgraferna, ackordgraferna, jämförbarhetsgraferna,
  • Trapezdiagram , som är skärningsgrafer för trapezoider vars parallella kanterpar ligger på två parallella linjer. Dessa inkluderar intervallgrafer, trivialt perfekta grafer, tröskelgrafer, väderkvarngrafer och permutationsgrafer; deras komplement är en delmängd av jämförbarhetsgraferna.

Relation till min-max satser

I alla grafer ger klicknumret en nedre gräns för det kromatiska numret, eftersom alla hörn i en klick måste tilldelas olika färger i rätt färg. De perfekta graferna är de för vilka denna nedre gräns är tät, inte bara i själva grafen utan i alla dess inducerade subgrafer. För grafer som inte är perfekta kan det kromatiska talet och klickantalet skilja sig åt; till exempel kräver en cykel med längd fem tre färger i rätt färg men dess största klick har storlek två.

Ett bevis på att en klass av grafer är perfekt kan ses som en min-max sats: det minsta antalet färger som behövs för dessa grafer är lika med den maximala storleken på en klick. Många viktiga min-max-satser i kombinatorik kan uttryckas i dessa termer. Till exempel, säger Dilworths sats att det minsta antalet kedjor i en partition av en delvis ordnad uppsättning i kedjor är lika med den maximala storleken på en antikedja , och kan omformuleras som att kompletteringen av jämförbarhetsgrafer är perfekta. Mirskys sats säger att det minsta antalet antikedjor i en partition i antikedjor motsvarar den maximala storleken på en kedja och motsvarar på samma sätt perfektion av jämförbarhetsgrafer.

Perfektion av permutationsgrafer motsvarar påståendet att längden på den längsta minskande undersekvensen i varje sekvens av ordnade element är lika med det minsta antalet sekvenser i en partition till ökande undersekvenser. Den Erdős-Szekeres teorem är en enkel följd av detta uttalande.

Kőnigs sats i grafteori säger att ett minimalt toppunktsskydd i en tvåpartig graf motsvarar en maximal matchning , och vice versa; det kan tolkas som perfektion av komplementen från tvåpartsdiagram. En annan sats om tvåpartsgrafer, att deras kromatiska index är lika med deras maximala grad , motsvarar perfektion av linjediagrammen för tvåpartsgrafer.

Karakteriseringar och de perfekta grafsatser

I sitt första arbete med perfekta grafer gjorde Berge två viktiga gissningar om deras struktur som först bevisades senare.

Den första av dessa två satser var den perfekta grafsatsen från Lovász (1972), som anger att en graf är perfekt om och bara om dess komplement är perfekt. Således är perfektion (definierad som jämlikheten mellan maximal klickstorlek och kromatiskt tal i varje inducerad subgraf) lika med maximal oberoende uppsättningsstorlek och klickomslag.

En cykel med sju hörn och dess komplement, som i varje fall visar en optimal färgning och en maximal klick (visas med tunga kanter). Eftersom ingen av graferna använder ett antal färger som är lika med dess klickstorlek, är ingen av dem perfekt.

Den andra satsen, gissad av Berge, gav en förbjuden grafkarakterisering av perfekta grafer. En inducerad cykel med udda längd minst 5 kallas ett udda hål . En inducerad subgraf som är komplementet till ett udda hål kallas ett udda antihål . En udda cykel med en längd större än 3 kan inte vara perfekt, eftersom dess kromatiska tal är tre och dess klicknummer är två. På samma sätt kan komplementet för en udda cykel med längden 2 k  + 1 inte vara perfekt, eftersom dess kromatiska tal är k  + 1 och dess klicknummer är k . (Alternativt följer ofullkomligheten i denna graf från den perfekta grafsatsen och ofullkomligheten i den kompletterande udda cykeln). Eftersom dessa grafer inte är perfekta måste varje perfekt graf vara en Berge -graf , en graf utan udda hål och inga udda antihål. Berge gissade det motsatta, att varje Berge -graf är perfekt. Detta bevisades slutligen som den starka perfekta grafsatsen för Chudnovsky , Robertson , Seymour och Thomas (2006). Det innebär trivialt den perfekta grafsatsen, därav namnet.

Den perfekta grafsatsen har ett kort bevis, men beviset för den starka perfekta grafsatsen är lång och teknisk, baserad på en djup strukturell sönderdelning av Berge -grafer. Relaterade sönderdelningstekniker har också burit frukt i studiet av andra grafflasser, och i synnerhet för de klofria graferna .

Det finns en tredje sats, igen på grund av Lovász, som ursprungligen föreslogs av Hajnal . Den säger att en graf är perfekt om storleken på den största klicken och den största oberoende uppsättningen, när de multipliceras tillsammans, är lika med eller överstiger antalet hörn i grafen, och samma sak gäller för alla inducerade subgrafer. Det är en lätt följd av den starka perfekta grafsatsen, medan den perfekta grafsatsen är en lätt följd av den.

Hajnal -karakteriseringen möts inte av udda n -cykler eller deras komplement för n > 3 : udda cykeln på n > 3 hörn har klicknummer 2 och oberoende nummer ( n -1)/2 . Det omvända gäller komplementet, så i båda fallen är produkten n - 1 .

Algoritmer på perfekta grafer

I alla perfekta grafer kan problem med graffärgning , maximalt klickproblem och maximalt oberoende setproblem lösas på polynomtid ( Grötschel, Lovász & Schrijver 1988 ). Algoritmen för det allmänna fallet innefattar Lovász -antalet för dessa grafer, som (för komplementet till en given graf) ligger mellan det kromatiska talet och klicknumret. Att beräkna Lovász -talet kan formuleras som ett semidefinitprogram och approximeras numeriskt i polynomtid med hjälp av ellipsoidmetoden för linjär programmering . För perfekta grafer ger avrundning av denna approximation till ett heltal kromatiskt tal och klickantal i polynomtid; den maximala oberoende uppsättningen kan hittas genom att använda samma tillvägagångssätt för komplementet till grafen. Denna metod är emellertid komplicerad och har en hög polynomexponent. Mer effektiva kombinatoriska algoritmer är kända för många specialfall.

Under många år var komplexiteten att känna igen Berge -grafer och perfekta grafer öppen. Av definitionen av Berge-grafer följer det omedelbart att deras erkännande är i co-NP (Lovász 1983). Slutligen, efter beviset för den starka perfekta grafteoremet, upptäcktes en polynomisk tidsalgoritm av Chudnovsky, Cornuéjols, Liu, Seymour och Vušković.

Referenser

externa länkar