Perfekt grafsats - Perfect graph theorem
I grafteorin säger den perfekta grafsatsen för László Lovász ( 1972a , 1972b ) att en oriktad graf är perfekt om och endast om dess komplementgraf också är perfekt. Detta resultat hade gissats av Berge ( 1961 , 1963 ), och det kallas ibland den svaga perfekta grafsatsen för att skilja den från den starka perfekta grafsatsen som kännetecknar perfekta grafer med sina förbjudna inducerade subgrafer .
Påstående
En perfekt graf är en oriktad graf med egenskapen att storleken på den största klicken i var och en av dess inducerade undergrafer är lika med det minsta antalet färger i en färgning av undergrafen. Perfekta grafer innehåller många viktiga grafer, inklusive bipartitgrafer , ackordgrafer och jämförbarhetsgrafer .
Komplementet till en graf har en kant mellan två hörn om och bara om det ursprungliga diagrammet inte har en kant mellan samma två hörn. Således blir en klick i den ursprungliga grafen en oberoende uppsättning i komplementet och en färgning av den ursprungliga grafen blir en klickomslag av komplementet.
Den perfekta grafsatsen säger:
- Komplementet till en perfekt graf är perfekt.
På samma sätt, i en perfekt graf, är storleken på den maximala oberoende uppsättningen lika med det minsta antalet klick i ett klickomslag.
Exempel
Låt G vara en cykeldiagram med udda längd större än tre (ett så kallat "udda hål"). Då kräver G minst tre färger i vilken färg som helst, men har ingen triangel, så det är inte perfekt. Genom den perfekta grafsatsen måste komplementet av G (ett "udda antihål") därför inte heller vara perfekt. Om G är en cykel med fem hörn är den isomorf till dess komplement , men den här egenskapen är inte sant för längre udda cykler, och det är inte lika trivialt att beräkna klickantalet och det kromatiska talet i ett udda antihål som det är i en udda hål. Som den starka perfekta grafsatsen säger, de udda hålen och udda antihålen visar sig vara de minimala förbjudna inducerade subgraferna för de perfekta graferna.
Ansökningar
I en icke-tvådelad bipartitgraf är det optimala antalet färger (per definition) två, och (eftersom bipartitgrafer är triangelfria ) är den maximala klickstorleken också två. Varje inducerad subgraf av en bipartitgraf förblir också bipartit. Därför är tvåpartsgrafer perfekta. I n -vertex bipartita grafer, tar minst klick lock i form av en matchande maximalt tillsammans med en ytterligare klick för varje oöverträffad vertex, med storlek n - M , där M är kardinaliteten för matchningen. I detta fall innebär alltså den perfekta grafsatsen Kőnigs sats att storleken på en maximal oberoende uppsättning i en tvåpartig graf också är n - M , ett resultat som var en stor inspiration för Berges formulering av teorin om perfekta grafer.
Mirskys sats som kännetecknar höjden på en delvis ordnad uppsättning med avseende på partitioner i antikedjor kan formuleras som perfektion i jämförelsegrafen för den delvis ordnade uppsättningen, och Dilworths sats som kännetecknar bredden på en delvis ordnad uppsättning när det gäller partitioner i kedjor kan formuleras som perfektion av komplementen i dessa grafer. Således kan den perfekta grafsatsen användas för att bevisa Dilworths sats från (mycket lättare) bevis på Mirskys sats, eller vice versa.
Lovász bevis
För att bevisa den perfekta grafsatsen använde Lovász en operation för att ersätta hörn i en graf med klick; det var redan känt för Berge att om en graf är perfekt är den graf som bildas av denna ersättningsprocess också perfekt. Varje sådan ersättningsprocess kan delas upp i upprepade steg för att fördubbla en toppunkt. Om det dubbla hörnet hör till en maximal klick i grafen ökar det både klickantalet och det kromatiska talet med en. Om den fördubblade hörnpunkten däremot inte tillhör en maximal klick, bilda en graf H genom att ta bort hörnen med samma färg som den dubblade hörnpunkten (men inte den dubblade hörnpunkten) från en optimal färgning av det givna diagrammet . De borttagna hörnen uppfyller varje maximal klick, så H har klicknummer och kromatiskt tal ett mindre än det för det angivna diagrammet. De borttagna hörnen och den nya kopian av det fördubblade hörnet kan sedan läggas tillbaka som en enda färgklass, vilket visar att dubbleringssteget i detta fall lämnar det kromatiska talet oförändrat. Samma argument visar att fördubbling bevarar likheten mellan klickantalet och det kromatiska talet i varje inducerad delgraf av den givna grafen, så varje fördubblingssteg bevarar grafens perfektion.
Med tanke på en perfekt graf G bildar Lovász en graf G * genom att ersätta varje hörn v med en klick av t v hörn, där t v är antalet distinkta maximala oberoende uppsättningar i G som innehåller v . Det är möjligt att korrespondera var och en av de distinkta maximala oberoende uppsättningarna i G med en av de maximala oberoende uppsättningarna i G *, på ett sådant sätt att de valda maximala oberoende uppsättningarna i G * alla är sammanhängande och varje toppunkt för G * visas i en enda utvald uppsättning; det vill säga G * har en färgning där varje färgklass är en maximal oberoende uppsättning. Denna färgning är nödvändigtvis en optimal färgning av G *. Eftersom G är perfekt, så är G *, och därför har den en maximal klick K * vars storlek är lika med antalet färger i denna färgning, vilket är antalet distinkta maximala oberoende uppsättningar i G ; nödvändigtvis innehåller K * en distinkt representant för var och en av dessa maximala oberoende uppsättningar. Den motsvarande uppsättningen K hörn i G (spetsarna vars expanderade klickarna i G * skär K *) är en klick i G med egenskapen att den skär varje maximala oberoende uppsättning i G . Därför har grafen som bildas från G genom att ta bort K klickomslagsnummer högst ett mindre än klickantalet G , och självständighetsnummer minst ett mindre än självständighetsnumret för G , och resultatet följer genom induktion på detta tal.
Relation till den starka perfekta grafsatsen
Den starka perfekta grafsetningen av Chudnovsky et al. (2006) säger att en graf är perfekt om och endast om ingen av dess inducerade subgrafer är cykler med udda längd större än eller lika med fem, eller deras komplement. Eftersom denna karakterisering inte påverkas av grafkomplementering innebär det omedelbart den svaga perfekta grafsatsen.
Generaliseringar
Cameron, Edmonds & Lovász (1986) bevisade att, om kanterna på en komplett graf delas upp i tre undergrafer på ett sådant sätt att var tredje hörn inducerar en ansluten graf i en av de tre delgraferna, och om två av undergraferna är perfekta , då är den tredje subgrafen också perfekt. Den perfekta grafsatsen är specialfallet för detta resultat när en av de tre delgraferna är den tomma grafen .
Anteckningar
Referenser
- Berge, Claude (1961), "Färbung von Graphen, deren sämtliche beziehungsweise deren ungerade Kreise starr sind", Wissenschaftliche Zeitschrift der Martin-Luther-Universität Halle-Wittenberg, Mathematisch-naturwissenschaftliche Reihe (på tyska), 10 : 114.
- Berge, Claude (1963), "Perfect graphs", Six Papers on Graph Theory , Calcutta: Indian Statistical Institute, s. 1–21.
- Cameron, K .; Edmonds, J .; Lovász, L. (1986), "A note on perfect graphs", Periodica Mathematica Hungarica , 17 (3): 173–175, doi : 10.1007/BF01848646 , MR 0859346.
- Chudnovsky, Maria ; Robertson, Neil ; Seymour, Paul ; Thomas, Robin (2006), "The strong perfect graph theorem", Annals of Mathematics , 164 (1): 51–229, arXiv : math/0212070 , doi : 10.4007/annals.2006.164.51 , MR 2233847.
- Chudnovsky, Maria ; Robertson, Neil ; Seymour, Paul ; Thomas, Robin (2003), "Progress on perfect graphs" (PDF) , Mathematical Programming , Series B., 97 (1–2): 405–422, doi : 10.1007/s10107-003-0449-8 , MR 2004404.
- Gallai, Tibor (1958), "Maximum-minimum Sätze über Graphen", Acta Mathematica Academiae Scientiarum Hungaricae (på tyska), 9 (3–4): 395–434, doi : 10.1007/BF02020271 , MR 0124238
- Golumbic, Martin Charles (1980), "3.2. The perfect graph theorem", Algorithmic Graph Theory and Perfect Graphs , New York: Academic Press, s. 53–58, ISBN 0-12-289260-7, MR 0562306.
- Kőnig, Dénes (1931), "Gráfok és mátrixok", Matematikai és Fizikai Lapok (på ungerska), 38 : 116–119
- Lovász, László (1972a), "Normala hypergrafer och den perfekta grafen", Diskret matematik , 2 (3): 253–267, doi : 10.1016/0012-365X (72) 90006-4.
- Lovász, László (1972b), "A characterization of perfect graphs", Journal of Combinatorial Theory , Series B, 13 (2): 95–98, doi : 10.1016/0095-8956 (72) 90045-7.
- Reed, Bruce A. (2001), "From conjecture to theorem", i Ramírez Alfonsín, Jorge L .; Reed, Bruce A. (red.), Perfect Graphs , Wiley-Interscience Series on Discrete Mathematics and Optimization, Chichester: Wiley, s. 13–24, MR 1861356.