Informatyczny kącik olimpijski

Kolorowanie cyklu

Zagadnienie kolorowania cyklu niejednokrotnie pojawiało się na konkursach programistycznych, m.in. na Mistrzostwach Europy Środkowej w Programowaniu Zespołowym (zadanie Beijing Guards z roku 2004), czy też Mistrzostwach Polski w Programowaniu Zespołowym (zadanie Słoneczna wyspa z roku 2010).

Dany jest cykl o $n$ wierzchołkach $v1,...,vn,$ którym trzeba tak przyporządkować kolory, by:

(1): wierzchołek $v i$ dostał dokładnie $w i$ różnych kolorów;
(2): każda para sąsiadujących wierzchołków dostała rozłączne zestawy kolorów;
(3): liczba użytych różnych kolorów była jak najmniejsza.

Rys. 1 Przykład dla cyklu o $n 4$ wierzchołkach i zapotrzebowaniach na kolory $|w1$ Do pokolorowania go wystarczy $K 6$ różnych kolorów.

Zadanie to ma bardzo proste rozwiązanie w przypadku cyklu o długości parzystej. Do pokolorowania pary sąsiadujących wierzchołków $|vi$ i $vi+1$ potrzebujemy $|wi + wi+1$ różnych kolorów (zakładamy dla uproszczenia, że $wn+1 = w1$ ). Zatem w sumie potrzebujemy ich co najmniej

K = max{wi + wi+1 i = 1,...,n}.

Okazuje się, że tyle różnych kolorów wystarczy. Jeśli oznaczymy te kolory kolejnymi liczbami naturalnymi $1,2,...,K,$ to wierzchołkom o numerach parzystych możemy przyporządkować początkowe kolory z listy, a wierzchołkom o numerach nieparzystych - kolory z końca listy. Innymi słowy, wierzchołek $i$ -ty dostanie kolory ${1,2,...,w }, i$ jeśli $i$ jest nieparzyste, lub kolory ${K− wi + 1,...,K},$ jeśli $i$ jest parzyste (patrz rysunek 1). Zauważmy, że powyższy algorytm działa nie tylko dla cyklu o długości parzystej, ale również dla ścieżek, drzew i w ogólności dla dowolnych grafów dwudzielnych.

Rys. 2 Przykład dla $n 7$ wierzchołków, z których każdy potrzebuje dwóch kolorów $| wi$ Zgodnie z algorytmem potrzebujemy $|K max 4, 143 - 5$ kolorów. Ponieważ $|k 2,$ więc wierzchołki $v1,v2,v3,v4$ kolorujemy cyklicznie, a wierzchołki $v5,v6,v7$ zgodnie z parzystością.

W przypadku cyklu o długości nieparzystej $n = 2m+ 1$ powyższe rozwiązanie nie działa. Już dla $n = 3$ widzimy, że potrzebne jest $|w1 + w2 + w3$ różnych kolorów. W ogólnym przypadku musimy sumarycznie wykonać $|W = Pni 1wi$ przydziałów kolorów. Ponieważ największy zbiór niezależny na cyklu (tzn. zbiór wierzchołków niepołączonych krawędziami) ma rozmiar $m,$ więc każdy kolor przydzielimy do co najwyżej $|m$ wierzchołków. Potrzebować więc będziemy co najmniej $|⌈Wm-⌉$ różnych kolorów. Okazuje się, że wystarczająca liczba kolorów to

′ W-- K = max {K,⌈ m ⌉} .

Niech $k$ będzie taką najmniejszą liczbą, że $2k+1 P i 1 wi⩽ kK′.$ Liczba ta istnieje, bo w szczególności nierówność powyższa jest spełniona dla $|k = m.$ Podzielimy teraz wierzchołki cyklu na dwie grupy, które będziemy kolorować na dwa różne sposoby (patrz przykład na rysunku 2). Wierzchołki $v1,v2,...,v2k$ kolorujemy cyklicznie, tzn. po kolei nadając im kolory z listy

1,2,...,K′,1,2,...,K′,1,2,...,K′,...

Natomiast wierzchołki $v2k+1,...,vn$ kolorujemy, używając metody dla cyklu długości parzystej, tzn. wierzchołkom nieparzystym przyporządkowujemy kolory $′ ′ {K − wi + 1,...,K },$ a wierzchołkom parzystym kolory $|{1,2,...,wi}.$

Pozostaje wykazać, że końce krawędzi łączących te dwie grupy wierzchołków są pokolorowane poprawnie. Dla krawędzi $v1vn$ jest prosto: wierzchołek $|v1$ używa kolorów ${1,...,w1},$ a wierzchołek $vn$ kolorów $|{K′−wn +1,...,K′ },$ wiemy też, że $K′⩾ w1 +wn.$ Dowód dla krawędzi $|v v 2k 2k+1$ jest trudniejszy. Ponieważ

2k−1 2k+1 (k − 1)K′< Q wi oraz Q wi ⩽kK ′, i 1 i 1

więc wierzchołkowi $|v2k$ zostaną przypisane kolory ze spójnego przedziału liczb naturalnych ${α + 1,α + 2,...,α +w2k},$ gdzie $2k−1 α = (Pi 1 wi) mod K′ .$ Ponadto spełnione jest $|α+ w2k + w2k+1⩽ K′,$ więc żaden kolor z tego przedziału nie jest kolorem ze zbioru kolorów $|{K′− w + 1,...,K′} 2k+1$ przypisanych do $v2k+1.$

Powyższy algorytm wyznaczający kolorowanie cyklu ma złożoność czasową $O(n).$