Twierdzenie o silnym grafie doskonałym - Strong perfect graph theorem

W teorii grafów The silny wykres idealny twierdzenie jest zabronione charakterystyka wykres z graf doskonały jak będąc dokładnie te wykresy, które mają ani dziwne otwory (nieparzyste długości cykli indukowane ) ani nieparzyste antiholes (uzupełnia dziwnych dziur). Przypuszczał to Claude Berge w 1961 roku. Dowód autorstwa Marii Chudnovsky , Neila Robertsona , Paula Seymoura i Robina Thomasa został ogłoszony w 2002 roku i opublikowany przez nich w 2006 roku.

Dowód twierdzenia o silnym grafie doskonałym zdobył dla swoich autorów nagrodę w wysokości 10 000 USD, którą ufundował Gérard Cornuéjols z Carnegie Mellon University oraz nagrodę Fulkersona w 2009 roku .

Komunikat

Doskonałe wykres przedstawia wykres, w którym na każdy indukowanego podgrafu , wielkość maksymalna klika równa minimalnej liczby kolorów w zabarwieniu na wykresie; graf doskonały zawierać wiele klas dobrze znany wykres w tym graf dwudzielny , akordowe wykresy i wykresy porównywalności . W swoich pracach z 1961 i 1963 definiujących po raz pierwszy tę klasę grafów, Claude Berge zauważył, że nie jest możliwe, aby doskonały graf zawierał nieparzystą dziurę, indukowany podgraf w postaci nieparzystego wykresu cyklu o długości pięciu lub więcej, ponieważ nieparzyste dziury mają klikę numer dwa i chromatyczną numer trzy. Podobnie zaobserwował, że idealne grafy nie mogą zawierać nieparzystych antydziur, indukowanych podgrafów komplementarnych do nieparzystych dziur: nieparzysta antydziura z 2 k  + 1 wierzchołkami ma liczbę kliki k i liczbę chromatyczną k  + 1, co jest ponownie niemożliwe dla grafów doskonałych. Grafy nie posiadające ani nieparzystych dziur, ani nieparzystych antydziur stały się znane jako grafy Berge.

Berge przypuszczał, że każdy graf Berge jest doskonały, lub równoważnie, że idealne grafy i grafy Berge definiują tę samą klasę grafów. Stało się to znane jako hipoteza silnego grafu doskonałego, aż do jego dowodu w 2002 roku, kiedy to zostało przemianowane na twierdzenie o silnym grafie doskonałym.

Związek ze słabym twierdzeniem o grafie doskonałym

Innym przypuszczeniem Berge, potwierdzonym w 1972 roku przez László Lovásza , jest to, że dopełnienie każdego doskonałego wykresu jest również doskonałe. Stało się to znane jako twierdzenie o doskonałym grafie lub (w celu odróżnienia od hipotezy / twierdzenia o silnym doskonałym grafie) twierdzenie o słabym grafie doskonałym. Ponieważ zakazana przez Bergego charakterystyka grafów jest samokomplementarna, twierdzenie o słabym grafie doskonałym wynika bezpośrednio z twierdzenia o grafie silnym.

Dowód pomysłów

Dowód twierdzenia o silnym grafie doskonałym autorstwa Chudnovsky'ego i in. opiera się na zarysie wymyślonym w 2001 r. przez Conforti, Cornuéjolsa, Robertsona, Seymoura i Thomasa, zgodnie z którym każdy graf Berge tworzy albo jeden z pięciu typów podstawowych elementów budulcowych (specjalne klasy doskonałych grafów), albo ma jeden z czterech różnych typów rozkład strukturalny na prostsze grafy. Minimalnie niedoskonały graf Bergego nie może mieć żadnej z tych dekompozycji, z czego wynika, że ​​nie może istnieć żaden kontrprzykład dla twierdzenia. Pomysł ten opierał się na wcześniejszych domniemanych dekompozycjach strukturalnych podobnego typu, które sugerowałyby silną hipotezę grafu doskonałego, ale okazały się fałszywe.

Pięć podstawowych klas doskonałych wykresów, które tworzą obudowę podstawy tej dekompozycji strukturalnej są graf dwudzielny , wykresy liniowe z graf dwudzielny, uzupełniające wykresy z graf dwudzielny uzupełnia wykresów liniowych graf dwudzielny i dwukrotnie wykresach dzielonych. Łatwo zauważyć, że dwudzielne grafy są doskonałe: w każdym nietrywialnym podgrafie indukowanym liczba klik i liczba chromatyczna są równe dwa, a zatem obie są równe. Doskonałość dopełnień grafów dwudzielnych i dopełnień grafów liniowych grafów dwudzielnych są równoważne twierdzeniu Kőniga o rozmiarach maksymalnych dopasowań , maksymalnych zbiorów niezależnych i minimalnych pokryć wierzchołków w grafach dwudzielnych. Doskonałość grafów liniowych grafów dwudzielnych można określić równoważnie jako fakt, że grafy dwudzielne mają indeks chromatyczny równy ich maksymalnemu stopniowi , co udowodnił Kőnig (1916) . Tak więc wszystkie cztery z tych podstawowych klas są doskonałe. Wykresy z podwójnym podziałem są względne w stosunku do wykresów z podziałem, które również można wykazać, że są doskonałe.

Cztery typy dekompozycji rozważane w tym dowodzie to 2-sprzężenia, dopełnienia 2-sprzężenia, zrównoważone podziały ukośne i pary jednorodne.

Połączenie dwudzielne to podział wierzchołków grafu na dwa podzbiory, z tą właściwością, że krawędzie obejmujące cięcie między tymi dwoma podzbiorami tworzą dwa kompletne grafy dwudzielne rozłączne z wierzchołkami . Gdy graf ma 2-sprzężenie, można go rozłożyć na indukowane podgrafy zwane „blokami”, zastępując jeden z dwóch podzbiorów wierzchołków najkrótszą ścieżką w tym podzbiorze, która łączy jeden z dwóch kompletnych grafów dwudzielnych z drugim; gdy taka ścieżka nie istnieje, zamiast tego blok jest tworzony przez zastąpienie jednego z dwóch podzbiorów wierzchołków dwoma wierzchołkami, po jednym dla każdego pełnego dwudzielnego podgrafu. Połączenie dwóch jest idealne wtedy i tylko wtedy, gdy oba jego bloki są idealne. Dlatego jeśli minimalnie niedoskonały graf ma 2-sprzężenie, musi być równy jednemu z jego bloków, z czego wynika, że ​​musi to być cykl nieparzysty, a nie Berge. Z tego samego powodu minimalnie niedoskonały graf, którego dopełnienie ma 2-sprzężenie, nie może być Berge.

Skośna strefa jest partycja wierzchołków wykresu na dwa podzbiory, z których jeden indukuje odłączony podgrafu a drugi z nich ma odłączony komplementarną; Chvátal (1985) przypuszczał, że żaden minimalny kontrprzykład dla hipotezy silnego grafu doskonałego nie może mieć podziału skośnego. Chudnovsky i in. wprowadzili pewne ograniczenia techniczne dotyczące ukośnych przegród i byli w stanie wykazać, że przypuszczenie Chvátala jest prawdziwe dla powstałych „zrównoważonych ukośnych przegród”. Pełne przypuszczenie jest następstwem twierdzenia o silnym grafie doskonałym.

Jednorodna para jest związana z modułową dekompozycji grafu. Jest to podział wykresu na trzy podzbiory V 1 , V 2 i V 3 takie, że V 1 i V 2 razem zawierają co najmniej trzy wierzchołki, V 3 zawiera co najmniej dwa wierzchołki, a dla każdego wierzchołka v w V 3 i każde i w {1,2} albo v sąsiaduje ze wszystkimi wierzchołkami w V i lub do żadnego z nich. Nie jest możliwe, aby minimalnie niedoskonały wykres miał jednorodną parę. Po dowodzie hipotezy silnego grafu doskonałego Chudnovsky (2006) uprościł ją, pokazując, że ze zbioru dekompozycji użytych w dowodzie można wyeliminować pary jednorodne.

Dowód na to, że każdy graf Berge należy do jednej z pięciu podstawowych klas lub ma jeden z czterech typów dekompozycji, wynika z analizy przypadku, w zależności od tego, czy w grafie istnieją pewne konfiguracje: „rozciągacz”, podgraf, który można rozłożyć na trzy indukowane ścieżki podlegające pewnym dodatkowym ograniczeniom, dopełnienie noszy i „właściwe koło”, konfiguracja związana z wykresem koła , składająca się z indukowanego cyklu wraz z wierzchołkiem piasty sąsiadującym z co najmniej trzema wierzchołkami cyklu i posłusznym kilku dodatkowe ograniczenia. Dla każdego możliwego wyboru, czy na danym wykresie Bergego istnieje napinacz, jego dopełnienie lub właściwe koło, można pokazać, że wykres należy do jednej z podstawowych klas lub jest rozkładalny. Ta analiza przypadku uzupełnia dowód.

Uwagi

Bibliografia

Linki zewnętrzne