W matematyce , zwłaszcza w teorii wykres The Brooks twierdzenie daje związek pomiędzy stopniem maksymalnej z podłączonym wykresie nieukierunkowany i numer chromatycznej .
Zgodnie z tym twierdzeniem, w grafie, w którym każdy wierzchołek ma co najwyżej Δ sąsiadów , wierzchołki mogą być pokolorowane co najwyżej Δ kolorami, bez dwóch sąsiednich wierzchołków o tym samym kolorze, z wyjątkiem dwóch przypadków, pełnych wykresów i wykresów nieparzystych. cykle długości , które wymagają Δ + 1 kolorów.
Twierdzenie - W dowolnym połączonym grafie nieskierowanym G o maksymalnym stopniu Δ, liczba chromatyczna χ (G) spełnia χ (G) ≤ Δ, chyba że G jest grafem pełnym lub cyklem o nieparzystej długości, w którym to przypadku χ (G) = Δ + 1.
Twierdzenie to nosi imię R. Leonarda Brooksa , który opublikował jego dowód w 1941 roku. Barwienie liczbą kolorów opisaną przez twierdzenie Brooksa jest czasami nazywane barwieniem Brooksa lub Δ- barwieniem . László Lovász dał prostszy dowód twierdzenia w 1975 roku.
Nie jest trudno wykazać, że dla dowolnego grafu χ (G) ≤ Δ + 1. Rzeczywiście, każdy wierzchołek v ma co najwyżej Δ sąsiednich wierzchołków, które w najgorszym przypadku są różnie pokolorowane. Nawet w tym przypadku zawsze możemy przyjąć (Δ + 1) kolor do koloru v . Zasługą Brooksa było zmniejszenie tego wzrostu o 1 jednostkę w większości przypadków.
Istnieje kilka dowodów twierdzenia Brooksa. Możemy na przykład rozumować przez indukcję na liczbie wierzchołków grafu. Poniższa demonstracja przebiega inaczej, opiera się na algorytmie zachłannym do kolorowania wykresów i dlatego ma tę zaletę, że dostarcza algorytmów do kolorowania wykresu (jest to demonstracja konstruktywna ).
Demonstrację tę przedstawił Ross Churchley w 2010 roku na podstawie pracy Johna Adriana Bondy'ego z 2003 roku. Zakończenie zastępuje rozumowanie Bondy innymi pracami, aby nie musieć najpierw odwoływać się do wyników dotyczących drzew o dużym zasięgu .
Poniżej przeanalizujemy kolejno cztery przypadki:
Zasadą w przypadku grafów nieregularnych jest uporządkowanie wierzchołków w określony sposób, a następnie pokolorowanie ich jeden po drugim za pomocą algorytmu zachłannego .
Niech G będzie grafem nieregularnym o n wierzchołkach i maksymalnym stopniu Δ. Ponieważ G nie jest regularne, istnieje co najmniej jeden wierzchołek x stopnia s ściśle mniejszego niż Δ. Umieszczamy ten wierzchołek na końcu planowania, czyli v n = x (rysunek 1) . Wierzchołki sąsiadujące z x są umieszczone tuż przed w tej kolejności, to znaczy w v n-s , v n-s-1 ,…, v n-1 (rysunek 2 ) .
Następnie bierzemy pod uwagę wierzchołki sąsiadujące z v n-1, które nie zostały jeszcze uporządkowane (rysunek 3) , następnie te, które sąsiadują z v n-2 i które nie zostały jeszcze uporządkowane, i tak dalej, aż do uporządkowania ich wszystkich, co jest to możliwe, ponieważ G jest podłączony (rysunek 4) .
W tej kolejności (v 1 , v 2 ,…, v n ) wszystkie wierzchołki mają co najmniej jeden sąsiadujący z tyłu wierzchołek (o wyższym indeksie), z wyjątkiem wierzchołka x . W konsekwencji, wszystkie one mają, z wyjątkiem wierzchołka x , liczbę poprzednich sąsiednich wierzchołków (o niższym indeksie) ściśle mniejszą niż Δ. Ostatni wierzchołek x ma również, według swojego początkowego wyboru, liczbę poprzednich sąsiednich wierzchołków ściśle mniejszą niż Δ.
Następnie kolorujemy wierzchołki v i jeden po drugim, ponieważ i zmienia się od 1 do n . Na każdym kroku wierzchołek v i nie został jeszcze pokolorowany. Jego poprzednie sąsiednie wierzchołki, które zostały już pokolorowane, mają maksymalną liczbę Δ-1, a zatem użyj a fortiori maksymalnie Δ-1 kolorów. Dlatego możemy przyjąć za nowy wierzchołek, w najgorszym przypadku, pozostały kolor spośród Δ (rysunki od 5 do 8) .
W grafie niepołączonym istnieje co najmniej jeden punkt artykulacji , czyli wierzchołek, którego usunięcie powoduje, że graf jest niepołączony.
Rozważmy taki regularny graf G stopnia Δ niedwuspójny i niech x będzie punktem artykulacji G (na czerwono na rysunku 1).
Rozkładamy G mnożąc punkt artykulacji jak na rys. 2. Otrzymujemy co najmniej dwa połączone wykresy nieregularne o maksymalnym stopniu Δ: rzeczywiście, wierzchołki otrzymane przez pomnożenie x mają każdy stopień ściśle mniejszy niż Δ.
Wraca się zatem do poprzedniego przypadku i można pokolorować każdy nieregularnie połączony element przy użyciu opisanej wcześniej metody. Możemy zaaranżować, aby wierzchołki otrzymane przez pomnożenie x miały ten sam kolor: w tym celu w razie potrzeby zamieniamy kolory w połączonych komponentach.
Pozostaje tylko ponownie złożyć części wykresu, aby uzyskać kolorowy wykres z Δ kolorami.
Jedynym połączonym grafem regularnym stopnia 0 jest graf regularny 0 składający się z jednego wierzchołka. Może być pokolorowany 1 kolorem (rysunek 1) . Ponieważ należy do kategorii grafów pełnych, spełnia twierdzenie Brooksa.
Jedynym połączonym grafem regularnym 1-stopniowym jest graf 1-regularny składający się tylko z dwóch wierzchołków, z krawędzią pomiędzy tymi dwoma wierzchołkami (rysunek 2) . Można go pokolorować 2 kolorami i tutaj też mamy do czynienia z pełnym grafem: spełnia on twierdzenie Brooksa.
Jedynymi połączonymi regularnymi wykresami stopnia 2 są cykle. Cykle o parzystej liczbie wierzchołków mogą być pokolorowane 2 kolorami (rysunek 4) , a 3 kolory są potrzebne dla cykli o nieparzystej liczbie wierzchołków (rysunki 3 i 5) . W obu przypadkach obowiązuje twierdzenie Brooksa.
Jeśli wykres G jest kompletny i stopnia Δ, to ma Δ + 1 wierzchołki, z których każdy kolor może być innym kolorem. W tym przypadku również obowiązuje twierdzenie Brooksa.
Jeśli wykres nie jest kompletny, ponownie uporządkujemy określoną liczbę wierzchołków, a następnie pokolorujemy je za pomocą algorytmu zachłannego. Nie jest to jednak tak proste, jak w przypadku grafu nieregularnego, ponieważ nic nie gwarantuje a priori, że po dotarciu do ostatniego wierzchołka będzie miał swobodny kolor. Dlatego zorganizujemy, że ostatni pokolorowany wierzchołek v będzie miał dwóch sąsiadów u i w już pokolorowanych tym samym kolorem, co zapewnia, że będziemy mieli co najmniej jeden wolny kolor więcej, jeśli chodzi o kolorowanie v .
Niech G będzie niekompletnym, podwójnie połączonym grafem stopnia Δ ≥ 3. Istnieją trzy wierzchołki u , v i w takie, że
A G nie jest kompletna, istnieją dwa wierzchołki i b , które nie są bezpośrednio połączone z krawędzi. Ponieważ wykres jest połączony, istnieje ścieżka ( a , v 1 , v 2 ,…, v p , b ) łącząca a z b . Niech i będzie największą wartością taką, że v i jest związane z a . Rozważ u = a , v = v i oraz w = v i + 1 . Te trzy wierzchołki sprawdzają, czy u i w są połączone z v bez łączenia się ze sobą.
Ponieważ wykres jest dwojaki, możemy usunąć z niego u lub w nie przestając być połączonym: G - { u } i G - { w } są połączone. Możemy nawet przyjąć u , v i w takie , że G - { u , w } jest nadal połączone.
Demonstracja Lemat 2 W dwuspójnym grafie G, o stopniu minimum 3 lub wyższym i niepełnym, możemy znaleźć wierzchołki u i w sąsiadujące z tym samym wierzchołkiem v , ale nie sąsiadujące między nimi, tak że G - { u , w } jest nadal połączone .Ponieważ wykres nie jest kompletny, istnieje co najmniej jeden wierzchołek a, który nie sąsiaduje z pozostałymi.
Jeśli G - { a } jest dwojaki, przyjmujemy, jak w dowodzie Lematu 1, u = a i w równe dowolnemu wierzchołkowi znajdującemu się w odległości 2 od a . Ponieważ G - { a } jest dwojaki, możemy usunąć z niego w bez utraty łączności, a G - { u , w } jest połączone.
Rozważmy teraz przypadek, w którym G - { a } jest połączone, ale nie jest bipołączone. Ma zatem punkty przegubowe (na rysunku zaznaczone na czerwono) . Niech z będzie jednym z tych punktów artykulacji. G - { a , z } nie jest połączony, jest nawet podzielony na co najmniej dwie rozłączne połączone elementy. Każdą z tych połączonych składowych V 1 , V 2 ,… V n można z kolei podzielić na dwójkowo połączone składowe połączone punktami przegubu. Te podwójnie połączone komponenty tworzą drzewo z korzeniem z .
W G, a ma sąsiada na każdym z liści na końcu tego drzewa. Rzeczywiście, jeśli usuniemy punkt artykulacji z i, do którego jest przymocowany liść, gdyby nie był połączony z a na drugim końcu, G - { z i } byłaby niespójna, co jest niemożliwe, ponieważ G jest dwojaki.
Weźmy u w jednym z liści na końcu V 1 oraz w w jednym z liści na końcu V 2 i niech v = a . Wierzchołki u i w są bardzo zbliżone do v . Nie sąsiadują ze sobą, ponieważ są pobierane z różnych połączonych komponentów.
Wierzchołki u i w brane w składowych dwuspójnych G-{ a }, a jednocześnie różne od punktów artykulacji G-{ a }, G-{ a , u , w } pozostają połączone. Ponieważ ponadto stopień a jest większy lub równy 3, istnieje trzeci wierzchołek pozwalający na połączenie a z G - { a , u , w }. Wykres G - { u , w } jest zatem połączony.
Ponieważ G - { u , w } jest połączone, możemy je uporządkować jak w poprzednich przypadkach, podając v najsilniejszą liczbę. Następnie kolorujemy G w następujący sposób:
Kiedy dochodzimy do pokolorowania ostatniego wierzchołka v , mamy gwarancję, że pozostanie wolny kolor, ponieważ jego dwaj sąsiedzi u i w mają ten sam kolor (rysunek 2 ) .
Do kolorowania list stosuje się uogólnienie twierdzenia Brooksa : mając nieskierowany i spójny wykres o maksymalnym stopniu Δ, który nie jest ani grafem kompletnym, ani cyklem o nieparzystej długości, oraz listę Δ kolorów dla każdego wierzchołka, można wybrać kolor dla każdego wierzchołka z listy, tak aby dwa sąsiadujące wierzchołki nigdy nie miały tego samego koloru. Innymi słowy, liczba chromatyczna listy nieskierowanego połączonego grafu nigdy nie jest większa niż Δ, z wyjątkiem przypadku pełnego grafu lub cyklu o nieparzystej długości. Zademonstrował to Vadim Vizing w 1976 roku.
W przypadku niektórych wykresów potrzebujemy nawet mniej Δ kolorów. Bruce Reed pokazuje, że kolory Δ-1 są wystarczające wtedy i tylko wtedy, gdy wykres nie ma Δ- kliknięć, gdy Δ jest wystarczająco duże. W przypadku grafów bez trójkąta (bez zestawu trzech sąsiadujących ze sobą wierzchołków parami) lub ogólniej dla grafów, w których sąsiedztwo każdego wierzchołka jest wystarczająco puste , wystarczają kolory O (Δ / log Δ).
Stopień wykresu pojawia się również w górnych granicach liczby kolorów wymaganych dla innych rodzajów kolorowania:
Kolorowanie Δ kolorami lub nawet kolorowanie przez listę with kolorami wykresu o maksymalnym stopniu Δ można uzyskać w czasie liniowym (proporcjonalnym do liczby wierzchołków i krawędzi). Znane są również wydajne algorytmy, które umożliwiają znajdowanie plam Brooksa przy użyciu przetwarzania równoległego lub rozproszonego.
(en) Eric W. Weisstein , „ Twierdzenie Brooksa ” , o MathWorld