Perfektní graf - Perfect graph

v teorie grafů, a perfektní graf je graf ve kterém chromatické číslo ze všech indukovaný podgraf se rovná pořadí největšího klika toho podgrafu (číslo kliky ). Ekvivalentně uvedeno symbolicky libovolný graf je perfektní, jen a jen pro všechny my máme .
Dokonalé grafy obsahují mnoho důležitých skupin grafů a slouží ke sjednocení souvisejících výsledků barviva a kliky v těchto rodinách. Například ve všech dokonalých grafech je problém zbarvení grafu, maximální problém s klikou, a problém maximálně nezávislé množiny vše lze vyřešit v polynomiální čas. Kromě toho několik důležitých min-max vět v kombinatorika, jako Dilworthova věta, lze vyjádřit z hlediska dokonalosti určitých souvisejících grafů.
Vlastnosti
- Podle dokonalá věta o grafu, graf je perfektní, právě když je doplněk je perfektní.
- Podle silná dokonalá věta o grafu, dokonalé grafy jsou stejné jako Berge grafy, což jsou grafy kde ani jeden ani obsahuje indukovaný cyklus liché délky 5 nebo více.
Další podrobnosti naleznete níže.
Dějiny
Teorie dokonalých grafů se vyvinula z roku 1958 Tibor Gallai že v moderním jazyce lze interpretovat jako konstatování, že doplněk a bipartitní graf je perfektní; tento výsledek lze také považovat za jednoduchý ekvivalent Kőnigova věta, mnohem dřívější výsledek týkající se shody a vrcholů v bipartitních grafech. První použití výrazu „dokonalý graf“ se zdá být v dokumentu z roku 1963 Claude Berge, podle nichž jsou pojmenovány grafy Berge. V tomto příspěvku sjednotil Gallaiho výsledek s několika podobnými výsledky definováním dokonalých grafů a předpokládal rovnocennost definic dokonalého grafu a Bergeova grafu; jeho domněnka byla prokázána v roce 2002 jako silná dokonalá věta o grafu.
Rodiny grafů, které jsou perfektní
Mezi nejznámější dokonalé grafy patří:[1]
- Bipartitní grafy, což jsou grafy, které mohou být barevný se dvěma barvami, včetně lesy (grafy bez cyklů).
- Čárové grafy bipartitních grafů (viz Kőnigova věta ). Rookovy grafy (spojnicové grafy kompletní bipartitní grafy ) jsou zvláštní případ.
- Chordální grafy, grafy, ve kterých má každý cyklus čtyř nebo více vrcholů a akord, hrana mezi dvěma vrcholy, které nejsou v cyklu za sebou. Tyto zahrnují
- lesy, k-stromy (maximální grafy s daným šířka stromu ),
- rozdělené grafy (grafy, které lze rozdělit do kliky a nezávislé sady),
- blokové grafy (grafy, ve kterých je každá vzájemně propojená součást klikou),
- Ptolemaiovské grafy (grafy, jejichž vzdálenosti se řídí Ptolemaiova nerovnost ),
- intervalové grafy (grafy, ve kterých každý vrchol představuje interval úsečky a každá hrana představuje neprázdný průnik mezi dvěma intervaly),
- triviálně dokonalé grafy (intervalové grafy pro vnořené intervaly), prahové grafy (grafy, ve kterých sousedí dva vrcholy, pokud jejich celková hmotnost přesáhne číselnou mez),
- větrný mlýn grafy (vytvořeno spojením stejných klik na společném vrcholu),
- a silně chordální grafy (akordové grafy, ve kterých má každý sudý cyklus délky šest a více lichý akord).
- Srovnatelné grafy vytvořen z částečně objednané sady spojením párů prvků hranou, kdykoli jsou příbuzné v částečném pořadí. Tyto zahrnují:
- bipartitní grafy, doplňky intervalových grafů, triviálně dokonalé grafy, prahové grafy, grafy větrných mlýnů,
- permutační grafy (grafy, ve kterých hrany představují dvojice prvků, které jsou obráceny permutací),
- a cographs (grafy tvořené rekurzivními operacemi disjunktního sjednocení a komplementace).
- Dokonale uspořádatelné grafy, což jsou grafy, které lze řadit tak, že a chamtivé zbarvení algoritmus je optimální na každém indukovaném podgrafu. Patří mezi ně bipartitní grafy, chordální grafy, grafy srovnatelnosti,
- vzdálenostně dědičné grafy (ve kterých jsou nejkratší dráhové vzdálenosti v připojených indukovaných podgrafech stejné jako v celém grafu),
- a grafy kol s lichým počtem vrcholů.
- Trapézové grafy, což jsou průsečíkové grafy z lichoběžníky jehož paralelní páry hran leží na dvou rovnoběžných liniích. Patří mezi ně intervalové grafy, triviálně dokonalé grafy, prahové grafy, grafy větrných mlýnů a permutační grafy; jejich doplňky jsou podmnožinou grafů srovnatelnosti.
Vztah k větám min-max
Ve všech grafech poskytuje číslo kliky dolní mez pro chromatické číslo, protože všem vrcholům v klice musí být při správném vybarvení přiřazeny odlišné barvy. Perfektní grafy jsou ty, pro které je tato dolní hranice těsná, a to nejen v samotném grafu, ale ve všech jeho indukovaných podgrafech. U grafů, které nejsou dokonalé, se může chromatické číslo a číslo kliky lišit; například cyklus délky pět vyžaduje tři barvy v jakémkoli správném vybarvení, ale jeho největší klika má velikost dvě.
Důkaz, že třída grafů je dokonalá, lze považovat za větu min-max: minimální počet barev potřebných pro tyto grafy se rovná maximální velikosti kliky. Mnoho důležitých min-max vět v kombinatorice lze vyjádřit těmito termíny. Například, Dilworthova věta uvádí, že minimální počet řetězců v oddílu a částečně objednaná sada do řetězců se rovná maximální velikosti antichain, a lze jej přeformulovat tak, že uvádí doplňky srovnatelné grafy jsou perfektní. Mirskyho věta uvádí, že minimální počet antichainů do oddílu na antichains se rovná maximální velikosti řetězce a stejným způsobem odpovídá dokonalosti srovnatelných grafů.
Dokonalost permutační grafy je ekvivalentní tvrzení, že v každé posloupnosti seřazených prvků je délka nejdelší klesající posloupnost se rovná minimálnímu počtu sekvencí v oddílu do zvyšujících se posloupností. The Erdős – Szekeresova věta je snadným důsledkem tohoto tvrzení.
Kőnigova věta v teorii grafů se uvádí, že minimální vrcholový kryt v bipartitním grafu odpovídá a maximální shoda a naopak; lze jej interpretovat jako dokonalost doplňků bipartitních grafů. Další věta o bipartitních grafech, že jejich chromatický index se rovná jejich maximálnímu stupni, je ekvivalentní dokonalosti spojnicových grafů bipartitních grafů.
Charakterizace a věty o dokonalém grafu
Ve své počáteční práci na dokonalých grafech vytvořil Berge dva důležité dohady o jejich struktuře, které se ukázaly až později.
První z těchto dvou vět byla dokonalá věta o grafu z Lovász (1972) s tím, že graf je dokonalý, právě když je jeho doplněk je perfektní. Dokonalost (definovaná jako rovnost maximální velikosti kliky a chromatického čísla v každém indukovaném podgrafu) je tedy ekvivalentní k rovnosti maximální velikosti nezávislé sady a počtu krytů kliky.

Druhá věta, kterou předpokládal Berge, poskytla a zakázaná charakterizace grafu dokonalých grafů. An indukovaný cyklus alespoň liché délky 5 se nazývá zvláštní díra. Indukovaný podgraf, který je doplňkem liché díry, se nazývá an zvláštní antihole. Zvláštní cyklus délky větší než 3 nemůže být dokonalý, protože jeho chromatické číslo je tři a jeho klikové číslo je dvě. Podobně doplněk lichého cyklu délky 2k + 1 nemůže být dokonalý, protože jeho chromatické číslo je k + 1 a jeho číslo kliky je k. (Alternativně nedokonalost tohoto grafu vyplývá z věty o dokonalém grafu a nedokonalosti doplňkového lichého cyklu). Protože tyto grafy nejsou dokonalé, musí být každý dokonalý graf a Bergeův graf, graf bez zvláštních děr a bez zvláštních děr. Berge si domyslel, že každý graf Berge je perfektní. To se nakonec ukázalo jako silná dokonalá věta o grafu z Chudnovský, Robertson, Seymour, a Thomas (2006). Triviálně to implikuje teorém o dokonalém grafu, odtud název.
Věta o dokonalém grafu má krátký důkaz, ale důkaz silné věty o dokonalém grafu je dlouhý a technický, založený na hlubokém strukturním rozkladu Bergeových grafů. Související techniky rozkladu přinesly ovoce i při studiu jiných tříd grafů, zejména pro grafy bez drápů.
Existuje třetí věta, opět kvůli Lovászovi, kterou původně navrhl Hajnal. Uvádí, že graf je dokonalý, pokud se velikost největší kliky a největší nezávislé množiny při násobení rovná nebo překračuje počet vrcholů grafu a totéž platí pro jakýkoli indukovaný podgraf. Je to snadný důsledek silné věty o dokonalém grafu, zatímco věta o dokonalém grafu je jejím snadným důsledkem.
Hajnalův charakter není lichý n-cykly nebo jejich doplňky pro n > 3: lichý cyklus zapnut n > 3 vertices má číslo kliky 2 a číslo nezávislosti (n − 1)/2. Opak platí pro doplněk, takže v obou případech je to produkt n − 1.
Algoritmy na dokonalých grafech
Ve všech dokonalých grafech je problém zbarvení grafu, maximální problém s klikou, a problém maximálně nezávislé množiny vše lze vyřešit v polynomiální čas (Grötschel, Lovász & Schrijver 1988 ). Algoritmus pro obecný případ zahrnuje Lovászovo číslo z těchto grafů, které (pro doplnění daného grafu) jsou vloženy mezi chromatické číslo a číslo kliky. Výpočet Lovászova čísla lze formulovat jako a semidefinitní program a numericky aproximován v polynomiální čas za použití elipsoidní metoda pro lineární programování. Pro dokonalé grafy zaokrouhlením této aproximace na celé číslo získáte chromatické číslo a číslo kliky v polynomiálním čase; maximální nezávislou množinu lze najít uplatněním stejného přístupu na doplněk grafu. Tato metoda je však komplikovaná a má vysoký polynomiální exponent. Efektivnější kombinatorické algoritmy jsou známy pro mnoho zvláštních případů.
Po mnoho let zůstávala složitost rozpoznávání Bergeových grafů a dokonalých grafů otevřená. Z definice Bergeových grafů okamžitě vyplývá, že jejich rozpoznávání je in co-NP (Lovász 1983). Nakonec, po důkazu silné dokonalé věty o grafu, Chudnovsky, Cornuéjols, Liu, Seymour a Vušković objevili algoritmus polynomiálního času.
Reference
- ^ West, Douglas Brent, autor. (2017-02-14). Úvod do teorie grafů. ISBN 9780131437371. OCLC 966410137.CS1 maint: více jmen: seznam autorů (odkaz)
- 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.CS1 maint: ref = harv (odkaz)
- Berge, Claude (1963). "Perfektní grafy". Šest článků o teorii grafů. Kalkata: Indický statistický institut. s. 1–21.
- Chudnovský, Maria; Cornuéjols, Gérard; Liu, Xinming; Seymour, Paule; Vušković, Kristina (2005). Msgstr "Rozpoznávání grafů Berge". Combinatorica. 25 (2): 143–186. doi:10.1007 / s00493-005-0012-8.CS1 maint: ref = harv (odkaz)
- Chudnovský, Maria; Robertson, Neil; Seymour, Paule; Thomas, Robin (2006). „Silná dokonalá věta o grafu“. Annals of Mathematics. 164 (1): 51–229. arXiv:matematika / 0212070. doi:10.4007 / annals.2006.164.51.CS1 maint: ref = harv (odkaz)
- Gallai, Tibor (1958). "Maximum-minimum Sätze über Graphen". Acta Math. Acad. Sci. Visel. 9 (3–4): 395–434. doi:10.1007 / BF02020271.CS1 maint: ref = harv (odkaz)
- Golumbic, Martin Charles (1980). Algoritmická teorie grafů a dokonalé grafy. Akademický tisk. ISBN 0-444-51530-5. Archivovány od originál dne 22. 05. 2010. Citováno 2007-11-21.CS1 maint: ref = harv (odkaz) Druhé vydání, Annals of Discrete Mathematics 57, Elsevier, 2004.
- Grötschel, Martin; Lovász, László; Schrijver, Alexander (1988). Geometrické algoritmy a kombinatorická optimalizace. Springer-Verlag.CS1 maint: ref = harv (odkaz) Viz zejména kapitola 9, „Stabilní sady v grafech“, s. 273–303.
- Lovász, László (1972). "Normální hypergrafy a dokonalá hypotéza grafu". Diskrétní matematika. 2 (3): 253–267. doi:10.1016 / 0012-365X (72) 90006-4.CS1 maint: ref = harv (odkaz)
- Lovász, László (1972). Msgstr "Charakterizace dokonalých grafů". Journal of Combinatorial Theory. Řada B. 13 (2): 95–98. doi:10.1016/0095-8956(72)90045-7.CS1 maint: ref = harv (odkaz)
- Lovász, László (1983). "Perfektní grafy". In Beineke, Lowell W .; Wilson, Robin J. (eds.). Vybraná témata v teorii grafů, roč. 2. Akademický tisk. str. 55–87. ISBN 0-12-086202-6.
externí odkazy
- Silná dokonalá věta o grafu podle Václav Chvátal.
- Otevřené problémy na dokonalých grafech, udržovaný Americký matematický institut.
- Dokonalé problémy, vedený Václavem Chvátalem.
- Informační systém o zahrnutí tříd grafů: perfektní graf