Twierdzenie o grafie doskonałym

Dwa uzupełniające się doskonałe wykresy

W teorii grafów twierdzenie László Lovásza ( 1972a , 1972b ) o grafach doskonałych stwierdza, że ​​graf nieskierowany jest doskonały wtedy i tylko wtedy, gdy jego graf dopełnienia jest również doskonały. Wynik ten został wysunięty przez Berge'a ( 1961 , 1963 ) i czasami nazywany jest twierdzeniem o słabym grafie doskonałym, aby odróżnić go od twierdzenia o silnym grafie doskonałym charakteryzującym grafy doskonałe przez ich zabronione indukowane podgrafy .

Oświadczenie

Graf doskonały to graf nieskierowany, którego właściwość polega na tym, że w każdym indukowanym podgrafie rozmiar największej kliki jest równy minimalnej liczbie kolorów w kolorowaniu podgrafu. Grafy doskonałe obejmują wiele ważnych klas grafów, w tym grafy dwudzielne , grafy akordowe i grafy porównywalności .

Dopełnienie grafu ma krawędź między dwoma wierzchołkami wtedy i tylko wtedy, gdy oryginalny graf nie ma krawędzi między tymi samymi dwoma wierzchołkami. W ten sposób klika w oryginalnym grafie staje się niezależnym zbiorem w dopełnieniu, a kolorowanie oryginalnego wykresu staje się pokryciem kliki dopełnienia.

Twierdzenie o grafie doskonałym stwierdza:

Dopełnienie doskonałego wykresu jest doskonałe.

Równoważnie, w idealnym grafie rozmiar maksymalnego niezależnego zestawu jest równy minimalnej liczbie klik w pokryciu kliki.

Przykład

Cykl siedmiu wierzchołków i jego dopełnienie, antydziura z siedmioma wierzchołkami, pokazujący w każdym przypadku optymalną kolorystykę i maksymalną klikę (pokazaną z grubymi krawędziami). Ponieważ żaden wykres nie używa liczby kolorów równej rozmiarowi jego kliki, żaden z nich nie jest doskonały.

Niech G będzie wykresem cyklu o nieparzystej długości większej niż trzy (tzw. „dziura nieparzysta”). Wtedy G wymaga co najmniej trzech kolorów w dowolnym zabarwieniu, ale nie ma trójkąta, więc nie jest doskonały. Zgodnie z twierdzeniem o wykresie doskonałym uzupełnienie G („nieparzysty antydziura”) również nie musi być doskonałe. Jeśli G jest cyklem pięciu wierzchołków, jest izomorficzny ze swoim dopełnieniem , ale ta właściwość nie jest prawdziwa dla dłuższych nieparzystych cykli, a obliczenie liczby kliki i liczby chromatycznej w nieparzystym antydziurze nie jest tak trywialne, jak w nieparzystym otworze. Jak silne twierdzenie o doskonałym grafie , nieparzyste dziury i nieparzyste antydziury okazują się minimalnymi zakazanymi podgrafami indukowanymi dla grafów doskonałych.

Aplikacje

W nietrywialnym grafie dwudzielnym optymalna liczba kolorów to (z definicji) dwa, a (ponieważ grafy dwudzielne nie zawierają trójkątów ) maksymalna wielkość kliki również wynosi dwa. Ponadto każdy indukowany podwykres grafu dwudzielnego pozostaje dwudzielny. Dlatego grafy dwudzielne są doskonałe. W n -wierzchołkowych grafach dwudzielnych minimalne pokrycie kliki ma postać maksymalnego dopasowania wraz z dodatkową kliką dla każdego niedopasowanego wierzchołka, o rozmiarze n − M , gdzie M jest licznością dopasowania. Zatem w tym przypadku twierdzenie o grafie doskonałym implikuje twierdzenie Kőniga , że ​​rozmiar maksymalnego zbioru niezależnego w grafie dwudzielnym wynosi również n - M , co było główną inspiracją dla sformułowania przez Berge'a teorii grafów doskonałych.

Twierdzenie Mirsky'ego charakteryzujące wysokość zbioru częściowo uporządkowanego pod względem podziałów na antyłańcuchy można sformułować jako doskonałość wykresu porównywalności zbioru częściowo uporządkowanego, a twierdzenie Dilwortha charakteryzujące szerokość zbioru częściowo uporządkowanego pod względem podziałów na łańcuchy można sformułować jako doskonałość dopełnień tych grafów. Zatem twierdzenie o grafie doskonałym może być użyte do udowodnienia twierdzenia Dilwortha na podstawie (znacznie łatwiejszego) dowodu twierdzenia Mirsky'ego lub odwrotnie.

Dowód Lovásza

Aby udowodnić twierdzenie o doskonałym grafie, Lovász zastosował operację zamiany wierzchołków w grafie na kliki; Berge wiedział już, że jeśli wykres jest doskonały, to wykres utworzony w wyniku tego procesu zastępowania jest również doskonały. Każdy taki proces zastępowania można podzielić na powtarzające się etapy podwajania wierzchołka. Jeśli podwojony wierzchołek należy do maksymalnej kliki grafu, zwiększa on zarówno liczbę klik, jak i liczbę chromatyczną o jeden. Jeśli natomiast podwojony wierzchołek nie należy do kliki maksymalnej, utwórz graf H usuwając wierzchołki o tym samym kolorze co podwojony wierzchołek (ale nie sam podwojony wierzchołek) z optymalnego kolorowania danego wykresu. Usunięte wierzchołki spełniają każdą maksymalną klikę, więc H ma liczbę klik i liczbę chromatyczną o jeden mniejszą niż na danym wykresie. Usunięte wierzchołki i nowa kopia podwojonego wierzchołka można następnie dodać z powrotem jako pojedynczą klasę kolorów, pokazując, że w tym przypadku krok podwojenia pozostawia liczbę chromatyczną niezmienioną. Ten sam argument pokazuje, że podwojenie zachowuje równość liczby kliki i liczby chromatycznej w każdym indukowanym podgrafie danego grafu, więc każdy krok podwojenia zachowuje doskonałość wykresu.

Mając idealny graf G , Lovász tworzy graf G * zastępując każdy wierzchołek v kliką t v wierzchołków, gdzie t v jest liczbą różnych maksymalnych niezależnych zbiorów w G , które zawierają v . Możliwe jest przyporządkowanie każdemu z odrębnych maksymalnych niezależnych zbiorów w G jednemu z maksymalnych niezależnych zbiorów w G * w taki sposób, że wybrane maksymalne niezależne zbiory w G * są rozłączne i każdy wierzchołek G * występuje w jednym wybranym zestawie; to znaczy G * ma kolorowanie, w którym każda klasa kolorów jest maksymalnie niezależnym zbiorem. Koniecznie to zabarwienie jest optymalnym zabarwieniem G *. Ponieważ G jest doskonały, G * też, a więc ma maksymalną klikę K *, której rozmiar jest równy liczbie kolorów w tym kolorowaniu, czyli liczbie odrębnych maksymalnych niezależnych zestawów w G ; koniecznie K * zawiera odrębnego przedstawiciela dla każdego z tych maksymalnych niezależnych zbiorów. Odpowiedni zestaw K wierzchołków w G (wierzchołki, których rozszerzone kliki w G * przecinają K *) jest kliką w G z tą właściwością, że przecina każdy maksymalny niezależny zbiór w G . Dlatego wykres utworzony z G przez usunięcie K ma liczbę pokrycia kliki co najwyżej o jeden mniejszą niż liczba kliki G i liczbę niezależności co najmniej o jedną mniejszą niż liczba niezależności G , a wynik następuje przez indukcję po tej liczbie.

Związek z silnym twierdzeniem o doskonałym grafie

Twierdzenie o silnym doskonałym grafie Chudnovsky'ego i in. (2006) stwierdza, że ​​graf jest doskonały wtedy i tylko wtedy, gdy żaden z jego indukowanych podgrafów nie jest cyklami o nieparzystej długości większej lub równej pięciu lub ich dopełnieniami. Ponieważ uzupełnienie wykresu nie ma wpływu na tę charakterystykę, natychmiast implikuje to twierdzenie o słabym doskonałym grafie.

Uogólnienia

Cameron, Edmonds i Lovász (1986) wykazali, że jeśli krawędzie pełnego grafu są podzielone na trzy podgrafy w taki sposób, że każde trzy wierzchołki indukują spójny graf w jednym z trzech podgrafów i jeśli dwa z podgrafów są doskonałe , to trzeci podwykres również jest doskonały. Twierdzenie o grafie doskonałym jest szczególnym przypadkiem tego wyniku, gdy jeden z trzech podwykresów jest grafem pustym .

Notatki

Pobrane z „ https://en.wikipedia.org/w/index.php?title=Perfect_graph_theorem&oldid=1135929956 ”