Zagadka kolorowania mapy

W roku 1852 matematyk Francis Guthrie zadał pozornie proste pytanie, które wywołało niekończący się spór, doprowadziło do odrzucenia kilku publikacji oraz do rozwiązania, które poszerzyło zakres reguł matematycznych. Owo pytanie brzmiało: jakiej minimalnej liczby kolorów potrzeba do takiego pokolorowania mapy, aby każde dwa odrębne graniczące ze sobą obszary różniły się kolorem? Obrazowo istotę problemu przedstawiają zamieszczone obok mapy Stanów Zjednoczonych. Czarno-biała wygląda skromnie. Kolorowa jest przejawem kartograficznej zasady większej wyrazistości w celu podkreślenia granic między regionami.

Trzeba oczywiście unikać takiego samego koloru sąsiednich stanów, bo byłoby to mylące. Tutaj wykorzystano cztery kolory. Czy wystarczyłyby trzy? Czy inne mapy wymagałyby pięciu lub sześciu?

Mapa nie musi być geograficzna. Chodzi o każdy podział płaszczyzny na odrębne obszary, ale pytanie się nie zmienia – dotyczy minimalnej liczby kolorów bez dwu takich samych w graniczących obszarach. Wypada jeszcze podać dwie podstawowe zasady.

Po pierwsze: każdy odrębny obszar musi być ciągły. Stan Michigan (MI) narusza tę zasadę, ponieważ jest podzielony jeziorem Michigan na dwie rozłączne części.

Po drugie: aby dwa obszary były uznane za sąsiadujące, granica między nimi musi być ciągła, czyli powinna mieć jakąś długość; stykanie się w jednym punkcie lub w dyskretnym zbiorze punktów nie spełnia tego warunku; na przykład stany Utah (UT) i Nowy Meksyk (NM) stykają się tylko jednym rogiem, więc nie mogą być uznane za sąsiadujące.

Po ustaleniu tych zasad pojawia się kilka pytań z nieco zaskakującymi odpowiedziami. Załóżmy, że wydrukowano duży plakat ze skomplikowaną mapą, zawierającą kilka tysięcy regionów. Ile czasu zajęłoby ustalenie, czy dwie barwy wystarczą do jej pokolorowania. A może potrzebne będą trzy? A jeśli cztery? Nie chodzi o kolorowanie całości. Wystarczy ustalić, czy jest ono możliwe dla danej liczby barw. Co ciekawe, chociaż zadania wydają się niemal identyczne dla różnych liczb, to czasy uporania się z każdym zdecydowanie się różnią mimo stosowania najbardziej efektywnych metod.

• Zdecydowanie, czy wystarczą dwa kolory, zajęłoby około godziny. Aby to zrobić, wybieramy dowolny region i go kolorujemy, powiedzmy na czerwono. Wymusza to przyjęcie drugiego koloru, na przykład niebieskiego, dla wszystkich sąsiadów. Z kolei wszyscy ich sąsiedzi muszą być czerwoni i analogicznie dalej na całej mapie. Ostatecznie albo pojawi się konflikt, gdy sąsiadujące regiony będą w jednym kolorze i wówczas dwubarwność nie będzie możliwa, albo kolory pokryją całą mapę bezkonfliktowo, co potwierdzi założenie o wystarczalności pary kolorów. Przy 3000 regionów i jednej sekundzie na kolorowanie każdego regionu cały proces zajmie 50 min przyjemnie straconego czasu.

• Załóżmy teraz, że ograniczenie kolorów do dwóch nie wystarczy. Rozstrzygnięcie, czy uda się przy trzech, zajęłoby znacznie więcej czasu. Nie starczyłoby nie tylko dni, ani nawet tygodni na sprawdzanie kolejnych barwnych konfiguracji. Zajęcie trzeba by przekazać następnemu pokoleniu, a ono następnemu i jeszcze kolejnym. I ta żmudna czynność trwałaby aż do chwili, gdy nieuchronnie przerwałoby ją pochłonięcie Ziemi przez Słońce po kilku miliardach lat. A do rozstrzygnięcia i tak byłoby niewiele bliżej niż na początku.

Określenie, czy dowolna mapa ma trójkolorową wersję, jest trudne. „Trudne” jest tu terminem matematycznym, wskazującym na rodzaj problemu obliczeniowego znanego z czasochłonności, zwanego NP-zupełnym. W przypadku problemów z klasy NP nie znamy szybszych metod niż mniej lub bardziej brutalne sprawdzanie każdego możliwego rozwiązania. Ta przestrzeń wyszukiwania rośnie wykładniczo wraz ze wzrostem rozmiaru problemu. W przypadku małej mapy z zaledwie kilkoma regionami można wykonać wyczerpujące badanie każdego możliwego trójkolorowania – aż do znalezienia pokrywającego całą mapę lub do ustalenia, że takiego nie ma. Natomiast liczba sposobów przypisania trzech kolorów do mapy z tysiącami regionów jest już tak astronomiczna, że taka metoda po prostu nie ma sensu.

• A jak będzie w przypadku czterech kolorów? Tu potrzeba ułamka sekundy – tyle, ile zajmuje wypowiedzenie słowa „tak”, ponieważ każdą mapę można pokolorować czterema kolorami. Ten wniosek wiąże się z niesławnym i długo kwestionowanym twierdzeniem o czterech barwach.

Guthrie wysunął hipotezę o czterech barwach w 1852 roku, gdy zauważył, że do prawidłowego pokolorowania mapy hrabstw Anglii potrzebował tylko czterech kolorów. Podejrzewał, że taka sytuacja dotyczy każdej mapy, ale chociaż każdy przedszkolak mógł to sprawdzić, ani on, ani jego koledzy po fachu nie potrafili tego dowieść. Było jasne, że z trzema kolorami nie zawsze się uda, o czym świadczy poniższy diagram kołowy, gdzie każdy region graniczy z każdym innym.

Nikomu nie udawało się znaleźć mapy, która wymagałaby pięciu kolorów. Zaskoczony problemem matematyk Augustus De Morgan był pod wrażeniem i doszedł do wniosku, że do listy aksjomatów, czyli stwierdzeń przyjmowanych w matematyce bez dowodu, z których wyprowadza się bardziej skomplikowane stwierdzenia, należy dodać jakiś nowy aksjomat, aby rozstrzygnąć hipotezę Guthriego.

Pozorny koniec frustracji nastąpił po pojawieniu się w 1879 roku pierwszego dowodu wystarczalności czterech kolorów, a w następnym roku niezależnie drugiego. Sprawa wydawała się rozstrzygnięta, nie szczędzono pochwał, a matematycy zajęli się innymi problemami – z wyjątkiem kilku sceptyków. 11 lat po publikacji pierwszego dowodu oba dowody zostały obalone, a wątpliwe twierdzenie o czterech barwach zdegradowano do hipotezy. Percy John Heawood z Durham University w Anglii, który ujawnił lukę w błędnych dowodach, posunął jednak sprawę do przodu, udowadniając, że do pokolorowania dowolnej mapy zawsze wystarczy pięć barw.

Świat matematyki znalazł się na rozstajach. Pozornie prosty problem miał dwie odpowiedzi – cztery lub pięć – choć tylko jedną dowiedzioną. Która była poprawna? Czy tylko ta druga? Taki stan niepewności miał trwać przez niemal sto lat.

Chociaż nikt nie mógł znaleźć mapy wymagającej pięciu kolorów, nikt nie mógł też wykluczyć pierwszej odpowiedzi. Ponieważ liczba map jest nieskończona, nie sposób każdą sprawdzić. Kluczowym krokiem ku rozwiązaniu było zredukowanie problemu do skończonego zbioru przypadków, które można sprawdzić indywidualnie. Skok od nieskończoności do skończoności wydaje się ogromny, ale monstrualna liczba przypadków zakwalifikowanych do sprawdzenia nadal znacznie przekraczała możliwość ręcznego uporania się z tą czynnością.

Kenneth Appel i Wolfgang Haken, matematycy z University of Illinois, podjęli się realizacji śmiałego pomysłu: postanowili zaprogramować komputer, aby zajął się problemem. W roku 1976, po latach szlifowania programu i po ponad tysiącu godzin pracy komputera, algorytm zakończył wyczerpujące sprawdzanie każdego przypadku, a hipoteza ostatecznie zmieniła się w twierdzenie o czterech barwach. Było to pierwsze znaczące twierdzenie, do którego dowiedzenia wykorzystano komputer.

W świecie matematyki zawrzało. Jedni byli zachwyceni, inni oburzeni. Kolega Appela i Hakena, William Tutte z University of Waterloo w Ontario, pogratulował im „pokonania krakena”. Inni z lekceważeniem i niesmakiem traktowali zastąpienie ludzkiej pomysłowości przez komputer.

Był to także problem filozoficzny: czy dowód, którego ludzki umysł nie jest w stanie zweryfikować, można w ogóle uznać za dowód? Wielu oczekiwało zanegowania efektów tej pracy, podobnie jak dwu poprzednich dowodów. „New York Times” początkowo odmówił nawet publikacji o dokonaniu Appela i Hakena, uznając, że wszystkie dowody twierdzenia o czterech barwach „są fałszywe”.

Liczne próby obalenia w kolejnych dekadach wspomaganego komputerowo dowodu zakończyły się fiaskiem. Później matematycy radykalnie uprościli dowód i zweryfikowali program, ale do dziś nie jest znany dowód wyprowadzony bez komputerowego wsparcia. Chociaż twierdzenie o czterech barwach jest powszechnie przyjęte, wciąż towarzyszy mu poczucie niespełnienia, bo program komputerowy, który systematycznie analizuje multum konfiguracji, nie wyjaśnia, dlaczego każda mapa może być czterokolorowa.

Mimo że matematycy dokonują odkryć chętnie wspomagając się komputerem, wciąż poszukują bardziej „ludzkiego” dowodu tej kolorowej zagadki.

***

Jack Murtagh pisze o matematyce, w tym rekreacyjnej, m.in. o ciekawostkach matematycznych w „Scientific American” i na portalu Gizmodo. Uzyskał doktorat z informatyki teoretycznej na Harvard University. Aktywny w serwisie X (@JackPMurtagh).