Perfekt graf - Perfect graph

Den Paleys graf av orden 9, farget med tre farger og viser en klikk av tre toppunkter. I denne grafen og hver av de induserte undergrafene er det kromatiske tallet lik klikkantallet, så det er en perfekt graf.

I grafteori er en perfekt graf en graf der det kromatiske tallet for hver induserte undergraf er lik rekkefølgen til den største klikken i det undergrafen ( klikknummer ). Tilsvarende uttrykt symbolsk er en vilkårlig graf perfekt hvis og bare hvis vi har alt . ${\ displaystyle G = (V, E)}$${\ displaystyle S \ subseteq V}$${\ displaystyle \ chi (G [S]) = \ omega (G [S])}}$

De perfekte grafene inkluderer mange viktige graferfamilier og tjener til å forene resultater knyttet til farger og klikk i disse familiene. For eksempel i alle perfekte grafer kan alle problemene med graffarging , maksimalt klikkproblem og maksimalt uavhengig settproblem løses på polynomtid . I tillegg kan flere viktige min-max-setninger i kombinatorikk , for eksempel Dilworths teorem , uttrykkes i form av perfeksjon av visse tilknyttede grafer.

En graf er 1-perfekt hvis og bare hvis . Da er den perfekt hvis og bare hvis hver subgrafi av er 1-perfekt. ${\ displaystyle G}$${\ displaystyle \ chi (G) = \ omega (G)}$${\ displaystyle G}$${\ displaystyle G}$

Egenskaper

• Ved den perfekte grafsetningen er en graf perfekt hvis og bare hvis komplementet er perfekt.${\ displaystyle G}$ ${\ displaystyle {\ bar {G}}}$
• Ved den sterke perfekte grafteoremet er perfekte grafer det samme som Berge -grafer, som er grafer der verken eller inneholder en indusert syklus med oddslengde 5 eller mer.${\ displaystyle G}$${\ displaystyle G}$${\ displaystyle {\ bar {G}}}$

Se delen nedenfor for mer informasjon.

Historie

Teorien om perfekte grafer utviklet fra et resultat fra Tibor Gallai fra 1958 som i moderne språk kan tolkes slik at det sier at komplementet til en todelt graf er perfekt; dette resultatet kan også sees på som en enkel ekvivalent til Kőnigs teorem , et mye tidligere resultat knyttet til matchninger og toppunktsdeksler i topartede grafer. Den første bruken av uttrykket "perfekt graf" ser ut til å være i et papir fra 1963 fra Claude Berge , som Berge -grafer er oppkalt etter. I denne artikkelen forente han Gallais resultat med flere lignende resultater ved å definere perfekte grafer, og han antok ekvivalensen til den perfekte grafen og Berge -grafdefinisjonene; hans formodning ble bevist i 2002 som den sterke perfekte grafsetningen .

Familier med grafer som er perfekte

Noen av de mer kjente perfekte grafene er:

• Bipartite grafer , som er grafer som kan farges med to farger, inkludert skog (grafer uten sykluser).
• Linjediagrammer over topartsgrafer (se Kőnigs teorem ). Rooks grafer (linjediagrammer over komplette topartsgrafer ) er et spesielt tilfelle.
• Akkordgrafer , grafene der hver syklus med fire eller flere hjørner har en akkord , en kant mellom to hjørner som ikke er sammenhengende i syklusen. Disse inkluderer
  • skog, k -trær (maksimale grafer med en gitt trebredde ),
  • delte grafer (grafer som kan deles i en klikk og et uavhengig sett),
  • blokkgrafer (grafer der hver tokoblet komponent er en klikk),
  • Ptolemaiske grafer (grafer hvis avstander overholder Ptolemaios ulikhet ),
  • intervallgrafer (grafer der hvert toppunkt representerer et intervall på en linje og hver kant representerer et ikke -fritatt kryss mellom to intervaller),
  • trivialt perfekte grafer (intervallgrafer for nestede intervaller), terskelgrafer (grafer der to hjørner ligger ved siden av når totalvekten overstiger en numerisk terskel),
  • vindmøllediagrammer (dannet ved å knytte like klikk til et felles toppunkt),
  • og sterkt akkordgrafer (akkordgrafer der hver jevne syklus med lengde seks eller flere har et merkelig akkord).
• Sammenlignbarhetsgrafer dannet fra delvis ordnede sett ved å koble elementpar med en kant når de er relatert til delordenen. Disse inkluderer:
  • topartsgrafer, komplement av intervallgrafer, trivialt perfekte grafer, terskelgrafer, vindmøllediagrammer,
  • permutasjonsgrafer (grafer der kantene representerer par av elementer som reverseres av en permutasjon),
  • og cographs (grafer dannet ved rekursive operasjoner av usammenhengende forening og komplementering).
• Perfekt bestillbare grafer , som er grafer som kan bestilles på en slik måte at en grådig fargealgoritme er optimal på alle induserte undergrafer. Disse inkluderer topartsgrafer, akkordgrafer, sammenligningsgrafer,
  • avstandsarvelige grafer (der de korteste baneavstandene i tilkoblede induserte undergrafer er lik dem i hele grafen),
  • og hjulgrafer med et ulikt antall hjørner.
• Trapesformede grafer , som er skjæringsgrafer for trapeser hvis parallelle kantpar ligger på to parallelle linjer. Disse inkluderer intervallgrafer, trivielt perfekte grafer, terskelgrafer, vindmøllediagrammer og permutasjonsgrafer; komplementene deres er en delmengde av sammenligningsgrafene.

Forhold til min-maks teoremer

I alle grafer gir klikketallet en nedre grense for det kromatiske tallet, ettersom alle hjørner i en klikk må tildeles forskjellige farger i enhver riktig farging. De perfekte grafene er de som denne nedre grensen er stram for, ikke bare i selve grafen, men i alle dens induserte undergrafer. For grafer som ikke er perfekte, kan kromatisk tall og klikknummer variere; for eksempel krever en syklus med lengde fem tre farger i riktig farge, men den største klikken har størrelse to.

Et bevis på at en klasse med grafer er perfekt, kan sees på som et min-max-teorem: det minste antallet farger som trengs for disse grafene, tilsvarer den maksimale størrelsen på en klikk. Mange viktige min-max-setninger i kombinatorikk kan uttrykkes i disse begrepene. For eksempel sier Dilworths teorem at minimum antall kjeder i en partisjon av et delvis ordnet sett i kjeder tilsvarer maksimal størrelse på et antikjede , og kan omformuleres slik at det sier at komplementene til sammenligningsgrafer er perfekte. Mirskys teorem sier at minimum antall antikjeder i en partisjon i antikjeder tilsvarer maksimal størrelse på en kjede, og tilsvarer på samme måte perfeksjonen av sammenlignbarhetsgrafer.

Perfeksjonen av permutasjonsgrafer er ekvivalent med utsagnet om at lengden på den lengste synkende undersekvensen i hver sekvens av ordnede elementer tilsvarer minimum antall sekvenser i en partisjon til økende undersekvenser. Den Erdős-Szekeres teorem er en enkel konsekvens av denne uttalelsen.

Kőnigs teorem i grafteori sier at et minimum toppunktdeksel i en todelt graf tilsvarer en maksimal matching , og omvendt; det kan tolkes som perfeksjonen av komplementene til topartsgrafer. En annen teorem om bipartittgrafer, at deres kromatiske indeks er lik deres maksimale grad , tilsvarer perfeksjonen av linjediagrammene for topartige grafer.

Karakteriseringer og de perfekte grafsetningene

I sitt første arbeid med perfekte grafer kom Berge med to viktige formodninger om strukturen som først ble bevist senere.

Den første av disse to setningene var den perfekte grafsetningen til Lovász (1972), og sa at en graf er perfekt hvis og bare hvis komplementet er perfekt. Dermed tilsvarer perfeksjon (definert som likheten mellom maksimal klikkstørrelse og kromatisk tall i hver induserte undergraf) likheten med maksimal uavhengig settstørrelse og klikkedekselnummer.

En syv-toppunktssyklus og dens komplement, som i hvert tilfelle viser en optimal farging og en maksimal klikk (vist med tunge kanter). Siden ingen av grafene bruker et antall farger som tilsvarer klikkstørrelsen, er ingen av dem perfekte.

Den andre setningen, antatt av Berge, ga en forbudt grafkarakterisering av perfekte grafer. En indusert syklus med minst 5 ulik lengde kalles et oddetall . En indusert subgraf som er komplementet til et merkelig hull kalles et merkelig antihull . En merkelig syklus med lengde større enn 3 kan ikke være perfekt, fordi det kromatiske tallet er tre og klikkets tall er to. Tilsvarende kan komplementet til en oddssyklus med lengden 2 k  + 1 ikke være perfekt, fordi det kromatiske tallet er k  + 1 og dets klikknummer er k . (Alternativt følger ufullkommenheten til denne grafen fra den perfekte grafsetningen og ufullkommenheten til den komplementære oddssyklusen). Fordi disse grafene ikke er perfekte, må hver perfekte graf være en Berge -graf, en graf uten merkelige hull og ingen rare antihull. Berge antok det motsatte, at hver Berge -graf er perfekt. Dette ble til slutt bevist som den sterke perfekte grafsetningen til Chudnovsky , Robertson , Seymour og Thomas (2006). Det innebærer trivielt den perfekte grafsetningen, derav navnet.

Den perfekte grafsetningen har et kort bevis, men beviset på den sterke perfekte grafsetningen er lang og teknisk, basert på en dyp strukturell nedbrytning av Berge -grafer. Relaterte dekomponeringsteknikker har også båret frukt i studiet av andre grafklasser, og spesielt for de klofrie grafene .

Det er en tredje teorem, igjen på grunn av Lovász, som opprinnelig ble foreslått av Hajnal . Den sier at en graf er perfekt hvis størrelsene på den største klikken og det største uavhengige settet, når de multipliseres sammen, er like eller overstiger antallet hjørner i grafen, og det samme gjelder for alle induserte undergrafer. Det er en enkel konsekvens av den sterke perfekte grafsetningen, mens den perfekte grafsetningen er en enkel konsekvens av den.

Hajnal -karakteriseringen oppfylles ikke av odd n -sykler eller komplementene deres for n > 3 : oddssyklusen på n > 3 hjørner har klikk nummer 2 og uavhengighetsnummer ( n -1 )/2 . Det motsatte gjelder for komplementet, så i begge tilfeller er produktet n - 1 .

Algoritmer på perfekte grafer

I alle perfekt grafer, den kurve som fargestoffer problem , maksimal klikken problem , og maksimum uavhengig sett problem kan alle løses i polynomtid ( Grötschel, Lovász og Schrijver 1988 ). Algoritmen for det generelle tilfellet involverer Lovász -tallet til disse grafene, som (for komplementet til en gitt graf) er klemt mellom det kromatiske tallet og klikketallet. Beregning av Lovász -tallet kan formuleres som et semidefinitt program og tilnærmes numerisk i polynomtid ved hjelp av ellipsoidmetoden for lineær programmering . For perfekte grafer gir avrunding av denne tilnærmingen til et heltall det kromatiske tallet og klikketallet i polynomtid; det maksimale uavhengige settet kan bli funnet ved å bruke den samme tilnærmingen til komplementet til grafen. Imidlertid er denne metoden komplisert og har en høy polynomeksponent. Mer effektive kombinatoriske algoritmer er kjent for mange spesielle tilfeller.

I mange år var kompleksiteten ved å gjenkjenne Berge -grafer og perfekte grafer åpen. Fra definisjonen av Berge-grafer følger det umiddelbart at anerkjennelsen deres er i co-NP (Lovász 1983). Til slutt, etter beviset på den sterke perfekte grafteoremet, ble en polynomisk tidsalgoritme oppdaget av Chudnovsky, Cornuéjols, Liu, Seymour og Vušković.

Referanser

• Berge, Claude (1961). "Färbung von Graphen, deren sämtliche bzw. deren ungerade Kreise starr sind". Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe . 10 : 114.
• Berge, Claude (1963). "Perfekte grafer". Seks artikler om grafteori . Calcutta: Indian Statistical Institute. s. 1–21.
• Chudnovsky, Maria ; Cornuéjols, Gérard ; Liu, Xinming; Seymour, Paul ; Vušković, Kristina (2005). "Gjenkjenne Berge -grafer" . Combinatorica . 25 (2): 143–186. doi : 10.1007/s00493-005-0012-8 . S2CID  2229369 .
• Chudnovsky, Maria ; Robertson, Neil ; Seymour, Paul ; Thomas, Robin (2006). "Den sterke perfekte grafsetningen" . Annals of Mathematics . 164 (1): 51–229. arXiv : matematikk/0212070 . doi : 10.4007/annals.2006.164.51 . S2CID  119151552 .
• Gallai, Tibor (1958). "Maksimum-minimum Sätze über Graphen" . Acta Mathematica Academiae Scientiarum Hungaricae . 9 (3–4): 395–434. doi : 10.1007/BF02020271 . S2CID  123953062 .
• Golumbic, Martin Charles (1980). Algoritmisk grafteori og perfekte grafer . Academic Press. ISBN 0-444-51530-5. Arkivert fra originalen 2010-05-22 . Hentet 2007-11-21 . Andre utgave, Annals of Discrete Mathematics 57, Elsevier, 2004.
• Grötschel, Martin ; Lovász, László ; Schrijver, Alexander (1988). Geometriske algoritmer og kombinatorisk optimalisering . Springer-Verlag. Se spesielt kapittel 9, "Stabile sett i grafer", s. 273–303.
• Lovász, László (1972). "Normale hypergrafer og den perfekte grafformelen" . Diskret matematikk . 2 (3): 253–267. doi : 10.1016/0012-365X (72) 90006-4 .
• Lovász, László (1972). "En karakterisering av perfekte grafer" . Journal of Combinatorial Theory . Serie B. 13 (2): 95–98. doi : 10.1016/0095-8956 (72) 90045-7 .
• Lovász, László (1983). "Perfekte grafer". I Beineke, Lowell W .; Wilson, Robin J. (red.). Utvalgte emner i grafteori, bind. 2 . Academic Press. s. 55–87. ISBN 0-12-086202-6.

Eksterne linker

• The Strong Perfect Graph Theorem av Václav Chvátal .
• Åpne problemer på perfekte grafer , vedlikeholdt av American Institute of Mathematics .
• Perfekte problemer , vedlikeholdt av Václav Chvátal.
• Informasjonssystem for grafklasseinneslutninger : perfekt graf