Grafo-mania, czyli rzecz o grafach i algorytmach. Gry chromatyczne na grafach | Politechnika Gdańska

Niech Alicja i Bogdan na przemian kolorują państwa na zadanej mapie, mając do dyspozycji ten sam skończony zbiór kolorów. Grę rozpoczyna Alicja, a jej celem jest pokolorowanie całej mapy. Natomiast jej przeciwnik, Bogdan, chce temu zapobiec. Obie strony obowiązuje reguła, że w każdym momencie gry państwa, które ze sobą graniczą, muszą mieć nadane różne kolory. Alicja zwycięża, gdy cała mapa G została pokolorowana. Inaczej zwycięzcą jest Bogdan. Najmniejszą liczbę kolorów, dla której Alicja ma strategię wygrywającą, nazywamy rozgrywaną liczbą chromatyczną χr(G). Na rys. 1 pokazujemy prosty przykład ilustrujący fakt, iż 4 barwy mogą już nie wystarczyć. Konstrukcja jest oparta na idei sześciościanu foremnego. Do pokolorowania potrzeba 5 barw, ponieważ za każdym razem, gdy Alicja wybiera region i kolor, Bogdan wybierze region niesąsiadujący z nim i nada mu kolor różny od koloru Alicji. Tym samym otrzymaliśmy pierwsze oszacowanie dolne liczby χr(G). Oszacowanie to można poprawić do 6, analizując ściany dwunastościanu foremnego (rys. 2). Tym razem strategia Bogdana polega na tym, by użyć koloru Alicji, ale dla ściany przeciwległej. Dolne oszacowanie można podnieść do 7 dla pewnej bryły 20-ściennej, która wymaga 7 kolorów. Na marginesie, wiadomo, że każdą mapę narysowaną na sferze można przenieść na płaszczyznę i na odwrót.

Ciekawsza jest historia górnych oszacowań rozgrywanej liczby chromatycznej. W roku 1994 Kierstead i Trotter podali pierwsze oszacowanie χr(G) ≤ 44, które zaraz potem poprawili do 33 dla każdego grafu planarnego G. Przy okazji oszacowanie dolne podnieśli do 8. Pięć lat później Dinski i Zhu pokazali, że χr(G) ≤ 30. W tym samym roku Zhu obniża swoje oszacowanie do 19, zaś Kierstead w roku 2000 poprawia jego wynik o 1. Obecnie rekord wynosi 17 i należy ponownie do Zhu.
Gry w kolorowanie można definiować dla różnych klas grafów, np. zewnętrznie planarnych (χr(G) ≤ 12), drzew T (χr(T) ≤ 6) i dla różnych modeli kolorowania, np. kolorowania krawędzi (χ'r(G) ≤ 2Δ–1, gdzie Δ jest stopniem grafu). Inny ciekawy problem powstaje, gdy pozwolimy Bogdanowi używać nowego koloru tylko wtedy, gdy nie może użyć żadnego z kolorów już wprowadzonych. W tym przypadku mamy χr(T) ≤ 3 dla wszystkich drzew T, zaś najmniejszym takim drzewem jest ścieżka na 4 wierzchołkach.

Czytelnikowi proponujemy, by spróbował ustalić, ile wynosi rozgrywana liczba chromatyczna mapy Polski. A gdy to mu się uda, proponujemy, by w ramach zabawy zmodyfikował granice województw tak, by powiększyć rozgrywaną liczbę chromatyczną kraju. Wskazówka: można to uczynić kosztem 3 województw.

kubale@eti.pg.edu.pl