Dokonalá věta o grafu - Perfect graph theorem

v teorie grafů, dokonalá věta o grafu z László Lovász  (1972a, 1972b ) uvádí, že an neorientovaný graf je perfektní jen a jen pokud doplňkový graf je také perfektní. Tento výsledek byl domněnkou Berge  (1961, 1963 ), a někdy se tomu říká slabá dokonalá věta grafu, aby se odlišil od silná dokonalá věta o grafu[1] charakterizovat dokonalé grafy podle jejich zakázané indukované podgrafy.

Prohlášení

A perfektní graf je neorientovaný graf s vlastností, kterou v každé své indukované podgrafy, velikost největšího klika se rovná minimálnímu počtu barev v a zbarvení podgrafu. Dokonalé grafy zahrnují mnoho důležitých tříd grafů včetně bipartitní grafy, chordální grafy, a srovnatelné grafy.

Doplněk grafu má hranu mezi dvěma vrcholy právě tehdy, pokud původní graf nemá hranu mezi stejnými dvěma vrcholy. Klika v původním grafu se tak stává nezávislá sada v doplňku a vybarvení původního grafu se změní na klikový obal doplňku.

Dokonalá věta o grafu uvádí:

Doplněk dokonalého grafu je perfektní.

Ekvivalentně se v dokonalém grafu velikost maximální nezávislé množiny rovná minimálnímu počtu klik v krytu klik.

Příklad

Cyklus sedmi vrcholů a jejich doplněk, antihole sedm vrcholů, zobrazující v každém případě optimální zbarvení a maximální kliku (znázorněnou silnými okraji). Vzhledem k tomu, že žádný z grafů nepoužívá stejný počet barev jako jeho velikost kliky, není ani jeden dokonalý.

Nechat G být graf cyklu liché délky větší než tři (tzv. „lichá díra“). Pak G vyžaduje alespoň tři barvy v jakémkoli zbarvení, ale nemá trojúhelník, takže to není dokonalé. Dokonalou větou grafu, doplněním G („zvláštní antihole“) proto také nesmí být dokonalý. Li G je cyklus pěti vrcholů, to je je isomorfní se svým doplňkem, ale tato vlastnost neplatí pro delší liché cykly a není tak triviální počítat číslo kliky a chromatické číslo v liché antihole jako v liché díře. Jako silná dokonalá věta o grafu stavech se liché díry a liché antiholy ukázaly jako minimální zakázané indukované podgrafy pro perfektní grafy.

Aplikace

V netriviální bipartitní graf, optimální počet barev je (podle definice) dvě a (protože bipartitní grafy jsou bez trojúhelníků ) maximální velikost kliky jsou také dvě. Jakýkoli indukovaný podgraf bipartitního grafu zůstává bipartitní. Proto jsou bipartitní grafy dokonalé. v n-vertexové bipartitní grafy, minimální kryt kliky má formu a maximální shoda společně s další klikou pro každý bezkonkurenční vrchol s velikostí n − M, kde M je mohutnost shody. V tomto případě tedy implikuje věta o dokonalém grafu Kőnigova věta že velikost maximální nezávislé množiny v bipartitním grafu je také n − M,[2] výsledek, který byl hlavní inspirací pro Bergeovu formulaci teorie dokonalých grafů.

Mirskyho věta charakterizující výšku a částečně objednaná sada pokud jde o oddíly do antichains lze formulovat jako dokonalost srovnávací graf částečně objednané sady a Dilworthova věta charakterizaci šířky částečně uspořádané množiny z hlediska oddílů do řetězců lze formulovat jako dokonalost doplňků těchto grafů. Dokonalá věta o grafu tedy může být použita k prokázání Dilworthovy věty z (mnohem jednoduššího) důkazu Mirského věty nebo naopak.[3]

Lovászův důkaz

K prokázání dokonalé věty o grafu použil Lovász operaci nahrazení vrcholů v grafu klikami; Berge už věděl, že pokud je graf dokonalý, je také dokonalý graf vytvořený tímto procesem nahrazení.[4] Jakýkoli takový proces nahrazení lze rozdělit na opakované kroky zdvojnásobení vrcholu. Pokud zdvojený vrchol patří do maximální kliky grafu, zvyšuje se jak číslo kliky, tak chromatické číslo o jednu. Pokud naopak zdvojený vrchol nepatří do maximální kliky, vytvořte graf H odstraněním vrcholů se stejnou barvou jako zdvojený vrchol (ale nikoli samotný zdvojený vrchol) z optimálního vybarvení daného grafu. Odstraněné vrcholy splňují všechny maximální kliky, takže H má číslo kliky a chromatické číslo o jedno menší než číslo daného grafu. Odebrané vrcholy a nová kopie zdvojeného vrcholu pak mohou být přidány zpět jako jedna barevná třída, což ukazuje, že v tomto případě krok zdvojení ponechává chromatické číslo beze změny. Stejný argument ukazuje, že zdvojnásobení zachovává rovnost čísla kliky a chromatické číslo v každém indukovaném podgrafu daného grafu, takže každý zdvojnásobení zachovává dokonalost grafu.[5]

Vzhledem k dokonalému grafu G, Lovász tvoří graf G* nahrazením každého vrcholu proti klikou na tproti vrcholy, kde tproti je počet různých maximálních nezávislých sad v G které obsahují proti. Je možné odpovídat každé z odlišných maximálních nezávislých sad G s jedním z maximálních nezávislých souborů v G* takovým způsobem, aby se nastavila zvolená maximální nezávislost G* jsou všechny disjunktní a každý vrchol G* se objeví v jedné vybrané sadě; to je G* má zbarvení, ve kterém je každá barevná třída maximálně nezávislou sadou. Toto zbarvení je nezbytně optimální zbarvení G*. Protože G je perfektní, tak je G*, a proto má maximální kliku K.* jehož velikost se rovná počtu barev v tomto zbarvení, což je počet odlišných maximálních nezávislých sad G; nezbytně, K.* obsahuje zřetelného zástupce pro každou z těchto maximálně nezávislých sad. Odpovídající sada K. vrcholů v G (vrcholy, jejichž rozšířené kliky jsou v G* protínají K.*) je klika G s vlastností, že protíná každou maximální nezávislou množinu G. Proto se graf vytvořil z G odstraněním K. má číslo krytu kliky maximálně o jedno menší než číslo kliky Ga číslo nezávislosti alespoň o jedno menší než číslo nezávislosti G, a výsledek následuje indukcí tohoto čísla.[6]

Vztah k silné teorému dokonalého grafu

The silná dokonalá věta o grafu z Chudnovsky a kol. (2006) uvádí, že graf je dokonalý, právě když žádný z jeho indukovaných podgrafů nejsou cykly liché délky větší nebo rovné pěti nebo jejich doplňky. Protože tato charakterizace není ovlivněna doplňováním grafů, okamžitě implikuje teorém o slabém dokonalém grafu.

Zobecnění

Cameron, Edmonds & Lovász (1986) dokázal, že pokud hrany a kompletní graf jsou rozděleny do tří podgrafů takovým způsobem, že každé tři vrcholy indukují spojený graf v jednom ze tří podgrafů, a pokud jsou dva z podgrafů dokonalé, pak je dokonalý i třetí podgraf. Věta o dokonalém grafu je zvláštním případem tohoto výsledku, když je jedním ze tří podgrafů prázdný graf.

Poznámky

  1. ^ To také předpokládal Berge, ale to se ukázalo až mnohem později Chudnovsky a kol. (2006).
  2. ^ Kőnig (1931), později znovu objeven Gallai (1958).
  3. ^ Golumbic (1980), Sekce 5.7, „Barvení a další problémy na grafech srovnatelnosti“, s. 132–135.
  4. ^ Vidět Golumbic (1980), Lemma 3.1 (i) a Reed (2001), Dodatek 2.21.
  5. ^ Reed (2001), Lemma 2.20.
  6. ^ Sledujeme zde výklad důkazu od Reed (2001). Golumbic (1980) konstatuje, že velká část tohoto uvažování byla rychle rekonstruována D. R. Fulkerson po vyslechnutí Lovászova výsledku, ale neviděl jeho důkaz.

Reference

  • 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 (v němčině), 10: 114.
  • Berge, Claude (1963), „Perfect graphs“, Šest článků o teorii grafů, Kalkata: Indický statistický institut, s. 1–21.
  • Cameron, K .; Edmonds, J.; Lovász, L. (1986), „Poznámka k dokonalým grafům“, Periodica Mathematica Hungarica, 17 (3): 173–175, doi:10.1007 / BF01848646, PAN  0859346.
  • Chudnovský, Maria; Robertson, Neil; Seymour, Paule; Thomas, Robin (2006), „The strong perfect graph theorem“, Annals of Mathematics, 164 (1): 51–229, arXiv:matematika / 0212070, doi:10.4007 / annals.2006.164.51, PAN  2233847.
  • Chudnovský, Maria; Robertson, Neil; Seymour, Paule; Thomas, Robin (2003), „Pokrok v dokonalých grafech“ (PDF), Matematické programování, Řada B., 97 (1–2): 405–422, doi:10.1007 / s10107-003-0449-8, PAN  2004404.
  • Gallai, Tibor (1958), „Maximum-minimum Sätze über Graphen“, Acta Mathematica Academiae Scientiarum Hungaricae (v němčině), 9 (3–4): 395–434, doi:10.1007 / BF02020271, PAN  0124238
  • Golumbic, Martin Charles (1980), "3.2. The Perfect Graph Theorem", Algoritmická teorie grafů a dokonalé grafy, New York: Academic Press, s. 53–58, ISBN  0-12-289260-7, PAN  0562306.
  • Kőnig, Dénes (1931), „Gráfok és mátrixok“, Matematikai a Fizikai Lapok (v maďarštině), 38: 116–119
  • Lovász, László (1972a), „Normální hypergrafy a dokonalá domněnka grafu“, Diskrétní matematika, 2 (3): 253–267, doi:10.1016 / 0012-365X (72) 90006-4.
  • Lovász, László (1972b), „Charakterizace dokonalých grafů“, Journal of Combinatorial Theory, Řada B, 13 (2): 95–98, doi:10.1016/0095-8956(72)90045-7.
  • Reed, Bruce A. (2001), „Od domněnky k teorému“, v Ramírez Alfonsín, Jorge L .; Reed, Bruce A. (eds.), Perfektní grafy, Wiley-Interscience Series on Discrete Mathematics and Optimization, Chichester: Wiley, str. 13–24, PAN  1861356.