Twierdzenie o grafie doskonałym - Perfect graph theorem
W teorii grafów The graf doskonały twierdzenie z László Lovász ( 1972a , 1972b ) stwierdza, że nieukierunkowane wykres jest idealny tylko wtedy, gdy jej wykres uzupełnieniem jest także doskonały. Wynik ten został wywnioskowany przez Berge'a ( 1961 , 1963 ) i jest czasami nazywany 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 podgrafy indukowane .
Oświadczenie
Doskonałe wykres jest nieukierunkowane wykres z właściwości, że w każdym z jego indukowanych subgraphs wielkość największych klika równa minimalnej liczby kolorów w zabarwieniu na podgrafu. Graf doskonały obejmują wiele ważnych wykresy zajęcia w tym graf dwudzielny , akordowych grafów i wykresów porównawczych .
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. Tak więc klika w oryginalnym grafie staje się niezależnym zbiorem w dopełnieniu, a kolorowanie oryginalnego grafu staje się pokryciem kliki dopełnienia.
Twierdzenie o grafie doskonałym mówi:
- Dopełnienie idealnego wykresu jest idealne.
Równoważnie, w idealnym grafie, rozmiar maksymalnego niezależnego zbioru jest równy minimalnej liczbie klik w okładce kliki.
Przykład
Niech G będzie wykresem cyklu o nieparzystej długości większej niż trzy (tzw. „dziurka nieparzysta”). Wtedy G wymaga co najmniej trzech kolorów w dowolnej kolorystyce, ale nie ma trójkąta, więc nie jest idealne. Zgodnie z twierdzeniem o doskonałym grafie dopełnienie G ("nieparzysta antydziura") również nie musi być doskonałe. Jeśli G jest cyklem o pięciu wierzchołkach, jest izomorficzny ze swoim dopełnieniem , ale ta własność nie jest prawdziwa dla dłuższych cykli nieparzystych, a obliczenie liczby kliki i liczby chromatycznej w nieparzystej antydziurze nie jest tak trywialne, jak w przypadku dziwna dziura. Jak stwierdza twierdzenie o silnym grafie doskonałym , nieparzyste dziury i nieparzyste antydziury okazują się minimalnymi podgrafami indukowanymi zabronionymi dla grafów doskonałych.
Aplikacje
W nietrywialnym grafie dwudzielnym optymalna liczba kolorów wynosi (z definicji) dwa, a (ponieważ grafy dwudzielne są wolne od trójkątów ) maksymalna wielkość kliki również wynosi dwa. Również każdy indukowany podgraf grafu dwudzielnego pozostaje dwudzielny. Dlatego wykresy dwudzielne są idealne. W dwudzielnych grafach n -wierzchołkowych minimalne pokrycie kliki przyjmuje 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 doskonałym grafie implikuje twierdzenie Kőniga, że rozmiar maksymalnie niezależnego zbioru w grafie dwudzielnym wynosi również n − M , co było główną inspiracją dla sformułowania teorii doskonałych grafów przez Berge'a.
Twierdzenie Mirsky'ego charakteryzujące wysokość zbioru częściowo uporządkowanego ze względu na podziały na antyłańcuchy można sformułować jako doskonałość grafu porównywalności zbioru częściowo uporządkowanego, a twierdzenie Dilwortha charakteryzujące szerokość zbioru częściowo uporządkowanego ze względu na podziały na łańcuchy może sformułować jako doskonałość uzupełnień tych wykresów. Zatem twierdzenie o doskonałym grafie 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 użył operacji zastępowania wierzchołków w grafie klikami; Berge wiedział już, że jeśli graf jest doskonały, to graf utworzony przez ten proces zastępowania jest również doskonały. Każdy taki proces zastępowania można podzielić na powtarzające się etapy podwojenia wierzchołka. Jeśli podwojony wierzchołek należy do maksymalnej kliki grafu, zwiększa zarówno liczbę kliki, jak i liczbę chromatyczną o jeden. Jeśli z drugiej strony podwojony wierzchołek nie należy do kliki maksimum, utwórz graf H usuwając wierzchołki o tym samym kolorze co podwojony wierzchołek (ale nie sam podwojony wierzchołek) z optymalnego pokolorowania danego grafu . Usunięte wierzchołki spełniają każdą maksymalną klikę, więc H ma liczbę kliki i liczbę chromatyczną o jeden mniejszą niż na danym wykresie. Usunięte wierzchołki i nowa kopia podwojonego wierzchołka mogą być następnie dodane z powrotem jako pojedyncza klasa koloru, pokazując, że w tym przypadku krok podwojenia pozostawia niezmienioną liczbę chromatyczną. Ten sam argument pokazuje, że podwojenie zachowuje równość liczby klik i liczby chromatycznej w każdym indukowanym podgrafie danego grafu, więc każdy krok podwojenia zachowuje doskonałość grafu.
Mając doskonały graf G , Lovász tworzy graf G * przez zastąpienie każdego wierzchołka v kliką t v wierzchołków, gdzie t v jest liczbą odrębnych maksymalnych niezależnych zbiorów w G, które zawierają v . Możliwe jest powiązanie każdego z odrębnych zbiorów maksymalnych niezależnych w G z jednym z maksymalnych niezależnych zbiorów w G * w taki sposób, że wybrane maksymalne zbiory niezależne w G * są wszystkie rozłączne i każdy wierzchołek G * pojawia się w jeden wybrany zestaw; to znaczy, G * ma kolorystykę, w której każda klasa koloru jest maksymalnie niezależnym zestawem. Koniecznie ta kolorystyka jest optymalną kolorystyką G *. Ponieważ G jest doskonałe, tak samo jest z G *, a zatem ma maksymalną klikę K *, której rozmiar jest równy liczbie kolorów w tym kolorowaniu, co jest liczbą odrębnych maksymalnych niezależnych zbiorów w G ; koniecznie, K * zawiera odrębnego przedstawiciela dla każdego z tych maksymalnych niezależnych zbiorów. Odpowiadający zbiór K wierzchołków w G (wierzchołki, których rozwinięte kliki w G * przecinają K *) jest kliką w G z własnością, że przecina każdy maksymalny niezależny zbiór w G . Zatem graf utworzony z G przez usunięcie K ma numer pokrycia kliki co najwyżej o jeden mniejszy niż numer kliki G , a numer niezależności co najmniej o jeden mniej niż numer niezależności G , a wynik następuje przez indukcję na tej liczbie.
Związek z twierdzeniem o silnym idealnym grafie
Silne twierdzenie doskonałe wykres z Chudnovsky 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łnieniom. Ponieważ na tę charakterystykę nie ma wpływu komplementacja grafów, od razu implikuje to twierdzenie o słabym grafie doskonałym.
Uogólnienia
Cameron, Edmonds i Lovász (1986) wykazali, że jeśli krawędzie grafu pełnego są podzielone na trzy podgrafy w taki sposób, że co trzy wierzchołki indukują spójny graf w jednym z trzech podgrafów i jeśli dwa z podgrafów są doskonałe , wtedy trzeci podgraf również jest doskonały. Twierdzenie o grafie doskonałym jest szczególnym przypadkiem tego wyniku, gdy jeden z trzech podgrafów jest grafem pustym .
Uwagi
Bibliografia
- 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 , 10 : 114 w języku niemieckim.
- Berge, Claude (1963), "Doskonałe wykresy", Six Papers on Graph Theory , Kalkuta: Indian Statistical Institute, s. 1-21.
- Cameron, K.; Edmonds, J .; Lovász, L. (1986), „Uwaga o doskonałych wykresach”, Periodica Mathematica Hungarica , 17 (3): 173-175, doi : 10.1007/BF01848646 , MR 0859346.
- Czudnowski, Maria ; Robertson, Neil ; Seymour, Paweł ; 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.
- Czudnowski, Maria ; Robertson, Neil ; Seymour, Paweł ; Thomas, Robin (2003), "Postęp na doskonałych wykresach" (PDF) , Programowanie matematyczne , Seria B., 97 (1-2): 405-422, doi : 10.1007/s10107-003-0449-8 , MR 2004404.
- Gallai, Tibor (1958), „Maksymalna-minimalna Sätze über Graphen”, Acta Mathematica Academiae Scientiarum Hungaricae (w języku niemieckim), 9 (3-4): 395-434, doi : 10.1007/BF02020271 , MR 0124238
- Golumbic, Martin Charles (1980), „3.2. Twierdzenie o idealnym wykresie”, Algorithmic Graph Theory and Perfect Graphs , New York: Academic Press, s. 53-58, ISBN 0-12-289260-7, MR 0562306.
- Kőnig, Denes (1931), „Gráfok és matrixok”, Matematikai és Fizikai Lapok (po węgiersku), 38 : 116-119
- Lovász, László (1972a), „Normalne hipergrafy i przypuszczenie idealnego wykresu”, Matematyka dyskretna , 2 (3): 253-267, doi : 10.1016/0012-365X(72)90006-4.
- Lovász, László (1972b), "Charakterystyka doskonałych wykresów", Journal of Combinatorial Theory , Seria B, 13 (2): 95-98, doi : 10.1016/0095-8956 (72) 90045-7.
- Reed, Bruce A. (2001), „Od przypuszczeń do twierdzenia”, w Ramírez Alfonsín, Jorge L.; Reed, Bruce A. (red.), Doskonałe wykresy , Wiley-Interscience Series on Discrete Mathematics and Optimization , Chichester: Wiley, str. 13-24, MR 1861356.