1 WYKŁAD 2. Kolorowanie wierzchołków(Uogólnienie problemu ZOO)

2 Kliki i zbiory niezależneW nazywamy kliką, gdy G[W] jest pełny. W nazywamy zbiorem niezależnym, gdy G[W] jest pusty. Liczba klikowa ω(G)= ω to moc największej kliki w grafie G. Liczba niezależności α(G)=α to moc największego zbioru niezależnego w G.

3 Przykład ω=3 α=3

4 Liczba chromatyczna Liczba chromatyczna χ(G)= χ to najmniejsza liczba k, taka że zbiór V można rozbić na k rozłącznych zbiorów niezależnych. Inaczej, minimalna liczba kolorów, przy pomocy których można pomalować wierzchołki grafu, tak by końce każdej krawędzi miały różne kolory.

5 Graf Petersena: χ=3

6 k-kolorowalność = k-dzielnośćJeśli to mówimy, że graf jest k-kolorowalny, albo k-dzielny. Mówiąc k-dzielny, mamy zwykle na myśli ustalony podział V na k zbiorów niezależnych V_1,...,V_k. Graf pełny dwudzielny K(m,n) to graf dwudzielny o dwupodziale (V_1,V_2), przy czym |V_1|=n a |V_2|=m, posiadający wszystkie mn krawędzie o jednym końcu w V_1 a drugim w V_2.

7 Ilustracja: k=3

8 Ilustracja: K(3,4)

9 Oszacowania dolne Grafy doskonałe: χ(G[W])=ω(G[W]) dla wszystkich W.Wszystkie grafy pełne oraz puste są doskonałe, bo χ(K_n)= ω(K_n)=n i χ(N_n)= ω(N_n)=1. Wszystkie grafy dwudzielne są doskonałe, bo χ(G)= ω(G)=2 (o ile G jest niepusty). Dopełnienia grafów dwudzielnych też są doskonałe (ćwiczenie).

10 Słaba hipoteza Berge’aLovász 1972: Graf jest doskonały wgdy jego dopełnienie jest doskonałe. Lovász pokazał mocniejszy fakt: G jest doskonały wgdy dla każdego W

11 Cykle parzyste Długość cyklu mierzymy liczbą krawędzi.Cykle parzyste (nieparzyste) to cykle o parzystej (nieparzystej) długości. Cykle parzyste są dwudzielne. C_4

12 Cykle nieparzyste Dla cykli nieparzystych χ=3.Ponadto, cykle nieparzyste długości większej niż 3 nie są doskonałe, bo ω=2. C_5

13 Mocna hipoteza Berge’a 1966Chudnovsky, Robertson, Seymour, and Thomas 2002: Graf jest doskonały wgdy ani on ani jego dopełnienie nie zawierają indukowanych cykli nieparzystych dłuższych niż 3. Dowód na 200 stron pomijamy!

14 Grafy „anty-doskonałe”Mycielski 1955: Dla dowolnej liczby naturalnej k ≥ 2 istnieje graf G_k, taki że ω(G_k)=2, a χ(G_k)=k. Dowód indukcyjny: G_2=K_2. Załóżmy, że G_k jest już skonstruowany na wierzchołkach v_1,...,v_n. Utwórzmy G_{k+1} przez dodanie n+1 nowych wierzchołków u_1,...,u_n oraz v i połączenie każdego u_i z v oraz ze wszystkimi sąsiadami wierzchołka v_i w G_k.

15 Ilustracja dowodu Tw. Mycielskiegov_1 v v_2 u_1 G_3 G_2

16 Ilustracja – ciąg dalszyv_1 v_5 u_1 v_2 u_5 u_2 v u_4 u_3 v_3 v_4 G_4

17 G_{k+1} nie zawiera K_3 Gdyby zawierał, to składałby się z 1 nowego wierzchołka – u_i i dwóch „starych” – v_j,v_l. Skoro jednak u_iv_j i u_iv_l są krawędziami grafu G_{k+1}, to v_iv_j i v_iv_l są krawędziami w G_k. Zatem v_i,v_j,v_l tworzą trójkąt w G_k – sprzeczność.

18 Ilustracja v_j u_i v_i v_l

19 χ(G_{k+1})=k+1 Weźmy dowolne k-kolorowanie G_k, powtórzmy kolor v_i na u_i, a v pomalujmy nowym, (k+1)-szym kolorem. Gdyby dało się pomalować G_{k+1} k kolorami, to na u_1,...,u_n wystąpiłoby tylko k-1 kolorów (k-ty kolor na v). Kolory z u_1,...,u_n można jednak przenieść na v_1,...,v_n otrzymując (k-1)-kolorowanie grafu – sprzeczność. 

20 Ilustracja v_1 u_1 v_5 v_2 u_5 u_2 v u_4 u_3 v_3 v_4

21 Oszacowania górne Δ(G)= Δ to największy stopień wierzchołka w grafie.Algorytm zachłanny („greedy”) maluje kolejno wierzchołki pierwszym wolnym kolorem.

22 Greedy -- ilustracja

23 Greedy -- ilustracja

24 Greedy -- ilustracja

25 Greedy -- ilustracja

26 Greedy -- ilustracja

27 Greedy -- ilustracja

28 Greedy -- ilustracja

29 Kiedy χ=Δ+1 ? Cykle nieparzyste i grafy pełne.Jeśli G jest niespójny, to znaczy istnieje podział V na A i B bez A-B krawędzi, to χ(G)=max(χ(G[A]), χ(G[B]), Δ(G) = max(Δ(G[A]), Δ(G[B]). Grafy G, w których Δ(G)=2 i choć jedna składowa jest cyklem nieparzystym. Grafy G, w których choć jedna składowa jest grafem pełnym K_{Δ(G)+1}.

30 Grafy niespójne - kolorowanieB B1 B2

31 Twierdzenie Brooksa (1941)Jeśli spójny graf G nie jest ani nieparzystym cyklem, ani grafem pełnym, to

32 Przypadek Δ=2 Przypadek Δ=2 obejmuje tylko ścieżki i cykle -- wśród nich tylko cykle nieparzyste mają χ=3.

33 G nieregularny Jeśli G nie jest regularny, to ustawmy wierzchołki w kolejności v_1,...,v_n, tak że d(v_n)< Δ , a dla każdego i=1,...,n-1, v_i ma sąsiada „na prawo”. Wtedy algorytm zachłanny użyje co najwyżej Δ kolorów.

34 Ilustracja

35 Ilustracja – c.d.

36 G ma wierzchołek cięciaWierzchołek v grafu spójnego G nazywamy wierzchołkiem cięcia, gdy G-v nie jest spójny. To znaczy istnieje podział V na A i B, |A|,|B|>1, A∩B={v}, bez krawędzi pomiędzy A-{v} i B-{v}. Wtedy χ(G)=max(χ(G[A]), χ(G[B]) oraz Δ(G) ≥ max(Δ(G[A]), Δ(G[B]). Pokazać, że w tym przypadku χ(G) ≤ Δ(G) (ćwiczenia).

37 Ilustracja B v A

38 Dowód Tw. Brooksa „Z głowy” mamy już przypadki: Δ=2, G nieregularny i G z wierzchołkiem cięcia. Niech teraz G będzie dowolnym grafem Δ-regularnym, bez wierzchołków cięcia, Δ ≥ 3, n=|V(G)|, spełniającym założenia twierdzenia. Ponieważ G nie jest grafem pełnym, to

39 Przypadek I G-{u,v}=G[V-{u,v}] jest spójny.Ustaw wierzchołki w kolejności u,v,v_1,...,v_{n-3},w tak, że dla każdego i=1,...,n-3, v_i ma sąsiada „na prawo”. Algorytm zachłanny pomaluje u i v tym samym kolorem i dlatego wystarczy Δ kolorów do pomalowania całego grafu.

40 Ilustracja u v w

41 Przypadek II Istnieje podział V na A i B, |A|,|B|>2 :Łatwo pokazać, że oba podgrafy, G[A] i G[B], można pomalować Δ kolorami (ćwiczenia). Jeśli oba podgrafy można pomalować tak, by u i v miały różne kolory, to potem można „zgrać” kolory uzyskując Δ-kolorowanie całego grafu G.

42 Ilustracja A B u v

43 Przypadek II – c.d. Przypuśćmy, że w każdym kolorowaniu podgrafu G[A], wierzchołki u i v otrzymują ten sam kolor. Wtedy, pamiętając, że uv nie jest krawędzią, mamy w G[A] d(u),d(v) ≥ Δ-1. Ponieważ stopnie u i v w obu podgrafach są pomiędzy 1 i Δ-1 (w przeciwnym razie byłby wierzchołek cięcia lub G nie byłby spójny), to w G[B] d(u)=d(v)=1. Ponieważ Δ ≥ 3, można znaleźć kolorowanie podgrafu G[B], w którym u i v są tego samego koloru, i znów „zgrać” kolory. 

44 Ilustracja A B u v