Twierdzenie o czterech barwach

Co się właśnie stało?

Trzy różne mapy — 4, 6 i 9 obszarów, o zupełnie innym układzie sąsiedztwa — dały się pokolorować tak, by żadne dwa sąsiadujące obszary nie miały tego samego koloru, i żadna nie potrzebowała więcej niż 4 kolorów. To nie przypadek ani szczęście doboru przykładów — to konsekwencja twierdzenia, które matematycy udowodnili dla każdej możliwej mapy na płaszczyźnie.

Model: mapa jako graf

Każdy obszar mapy zamieniamy na wierzchołek grafu, a wspólną granicę dwóch obszarów — na krawędź. Pokolorowanie mapy staje się kolorowaniem grafu: trzeba przypisać każdemu wierzchołkowi kolor tak, by żadna krawędź nie łączyła dwóch wierzchołków tego samego koloru.

gdzie $\chi(G)$ (liczba chromatyczna) to najmniejsza liczba kolorów potrzebna do pokolorowania grafu G. Graf płaski to taki, który da się narysować na płaszczyźnie bez przecinających się krawędzi — dokładnie taki, jaki powstaje z mapy podzielonej na obszary.

Twierdzenie o czterech barwach

Dowolną mapę podzieloną na obszary (kraje, województwa, działki) da się pokolorować tak, by żadne dwa obszary mające wspólny odcinek granicy (nie tylko punkt styku) nie miały tego samego koloru — używając co najwyżej 4 kolorów. Bywa, że wystarczą 2 lub 3 (jak w mapie średniej wyżej — jej graf jest dwudzielny), ale nigdy nie trzeba więcej niż 4, niezależnie od tego, ile obszarów ma mapa i jak bardzo są powyginane.

Dlaczego to było takie trudne

Problem postawił w 1852 r. Francis Guthrie, kolorując mapę hrabstw Anglii i zauważając, że 4 kolory zawsze wystarczają. Przez ponad 120 lat matematycy próbowali to udowodnić lub znaleźć kontrprzykład — bez skutku. Dopiero w 1976 r. Kenneth Appel i Wolfgang Haken przedstawili pierwszy poprawny dowód, przełomowy nie tylko wynikiem, ale metodą: sprowadzili problem do sprawdzenia 1834 „nieuniknionych" konfiguracji map, których obecność wyklucza istnienie kontrprzykładu. Ręczne sprawdzenie wszystkich przypadków było niemożliwe — zajęło komputerowi ponad miesiąc obliczeń. Był to pierwszy ważny dowód matematyczny w historii wykonany z istotnym udziałem komputera, co wzbudziło kontrowersje: część matematyków kwestionowała, czy dowód, którego żaden człowiek nie jest w stanie ręcznie prześledzić krok po kroku, można w ogóle uznać za dowód matematyczny.

Co to znaczy w praktyce?

Kolorowanie grafów wykracza daleko poza mapy: przydział częstotliwości radiowych (sąsiednie nadajniki nie mogą kolidować), układanie planu zajęć (te same osoby/sale nie mogą się pokrywać w czasie) czy alokacja rejestrów w kompilatorach — wszędzie tam, gdzie trzeba przypisać zasoby tak, by „sąsiadujące" elementy się nie konfliktowały, to właśnie ten sam problem.

Po co Ci to na maturze:

Twierdzenie o czterech barwach samo w sobie nie wchodzi w zakres matury — to ciekawostka spoza programu. Ale przejście „mapa → graf → kolorowanie" to wzorcowy przykład modelowania problemu geometrycznego jako problemu z teorii grafów, a rozumowanie o niezmiennikach (tu: liczbie użytych kolorów, która nigdy nie przekracza 4) przydaje się w zadaniach kombinatorycznych z rozszerzenia.

Zapamiętaj: każdą mapę na płaszczyźnie da się pokolorować tak, by sąsiadujące obszary miały różne kolory, używając co najwyżej 4 kolorów — to twierdzenie, udowodnione w 1976 r. przy istotnym udziale komputera po 1834 sprawdzonych konfiguracjach, a nie tylko obserwacja z pojedynczych przykładów.