Twierdzenie o czterech barwach wyjaśnione
W 1852 roku młody matematyk, kolorując mapę hrabstw Anglii, zauważył, że cztery kolory wydają się wystarczać, by odróżnić od siebie sąsiednie hrabstwa. Czy mogło to być prawdą dla każdej możliwej mapy? Pytanie stało się jednym z najsłynniejszych problemów matematyki, doczekało się głośnego błędnego dowodu, który przetrwał jedenaście lat, i zostało ostatecznie rozstrzygnięte w 1976 roku w sposób, który zmienił to, co matematycy uznają za dowód.
Pytanie
Francis Guthrie, były student Augustusa De Morgana, zapytał, czy każdą mapę można pokolorować czterema kolorami tak, by kraje mające wspólną granicę otrzymały różne kolory. Dwie zasady czynią pytanie precyzyjnym. Kraje muszą być spójne, każdy w jednym kawałku, a kraje stykające się tylko w jednym punkcie nie liczą się jako sąsiedzi. Trzy kolory oczywiście nie zawsze wystarczą, bo kraj otoczony pierścieniem trzech innych, które wszystkie się stykają, wymaga czwartego. Pytanie brzmi, czy kiedykolwiek potrzebny jest piąty.
Mapy jako grafy
Zaznacz punkt w każdym kraju i narysuj linię między dwoma punktami, gdy ich kraje mają wspólną granicę. Wynikiem jest graf, a ponieważ mapa leży na płaskiej kartce, linie można narysować bez przecięć: graf jest planarny. Kolorowanie mapy to kolorowanie wierzchołków tego grafu tak, by końce każdej krawędzi się różniły. Najmniejsza liczba kolorów, która wystarcza, to liczba chromatyczna, a twierdzenie o czterech barwach stwierdza, że żaden graf planarny nie ma liczby chromatycznej większej niż cztery.
Nieudany dowód Kempego
W 1879 roku adwokat i matematyk Alfred Kempe opublikował dowód. Jego pomysłowa idea, zwana dziś łańcuchami Kempego, polega na zamianie dwóch kolorów wzdłuż spójnego łańcucha krajów, aby zwolnić kolor tam, gdzie jest potrzebny. Dowód był uznawany przez jedenaście lat, aż w 1890 roku Percy Heawood znalazł w nim lukę. Poprawka Heawooda dowiodła słabszego wyniku: pięć kolorów zawsze wystarczy. Łańcuchy Kempego przetrwały i stały się narzędziem w ostatecznym dowodzie.
Dlaczego pięć jest łatwe
Każdy graf planarny ma wierzchołek o co najwyżej pięciu sąsiadach; wynika to ze wzoru Eulera, który ogranicza liczbę krawędzi grafu planarnego o n wierzchołkach do co najwyżej 3n − 6. Usuń taki wierzchołek, pokoloruj resztę mapy tym samym argumentem i przywróć wierzchołek. Jeśli jego sąsiedzi używają mniej niż pięciu kolorów, jeden jest wolny. Jeśli używają wszystkich pięciu, zamiana wzdłuż łańcucha Kempego zawsze jakiś zwolni. Przy czterech kolorach ta sama zamiana może zawieść i to jest właśnie luka, której Kempe nie zauważył.
Dowód komputerowy
W 1976 roku Kenneth Appel i Wolfgang Haken z Uniwersytetu Illinois udowodnili twierdzenie. Pokazali, że każda mapa zawiera co najmniej jedną z 1936 konfiguracji ze zbioru nieuniknionego i że każda konfiguracja jest redukowalna: najmniejsza mapa wymagająca pięciu kolorów nie mogłaby jej zawierać. Sprawdzenie redukowalności zajęło ponad tysiąc godzin pracy komputerów – o wiele za dużo, by zweryfikować to ręcznie. Wielu matematyków niepokoił dowód, którego żaden człowiek nie mógł przeczytać w całości, i rozpoczęła się debata o dowodach wspomaganych komputerowo.
Prostsze dowody i pełna weryfikacja
W 1996 roku Neil Robertson, Daniel Sanders, Paul Seymour i Robin Thomas opublikowali bardziej systematyczny dowód z 633 konfiguracjami, nadal sprawdzany komputerowo, ale łatwiejszy do zweryfikowania. W 2005 roku Georges Gonthier i Benjamin Werner sformalizowali cały dowód w asystencie dowodzenia Coq, tak że mały, zaufany program sprawdza każdy krok logiczny. Dziś twierdzenie o czterech barwach jest jednym z najdokładniej zweryfikowanych wyników w matematyce.
Algorytmy kolorowania
Znalezienie pokolorowania danej mapy czterema kolorami jest w praktyce szybkie, ale znalezienie najmniejszej liczby kolorów dla ogólnego grafu jest trudne: rozstrzygnięcie, czy wystarczą trzy kolory, jest problemem NP-zupełnym. Praktyczne metody to m.in. kolorowanie zachłanne w kolejności malejących stopni, DSATUR, który jako następny koloruje najbardziej ograniczony wierzchołek, oraz przeszukiwanie z nawrotami, które bada wybory i cofa je, gdy utknie. Kolorowanie grafów pozwala układać harmonogramy egzaminów bez kolizji, przydzielać częstotliwości radiowe tak, by sąsiednie nadajniki się nie zakłócały, i przydzielać rejestry w kompilatorach.
Wypróbuj sam
Otwórz kolorowanie mapy czterema kolorami, aby generować mapy liczące od 4 do 120 krajów, malować je ręcznie czterema kolorami i obserwować, jak konflikty pojawiają się na czerwono. Pozwól algorytmowi zachłannemu, DSATUR albo przeszukiwaniu z nawrotami rozwiązać mapę krok po kroku, pokaż graf sąsiednich krajów i sprawdź, ilu kolorów mapa naprawdę potrzebuje co najmniej.
Często zadawane pytania
Czy twierdzenie pomaga kartografom?
Raczej nie. Prawdziwe mapy zwykle koloruje się większą liczbą kolorów dla czytelności, a zawierają one oceany, jeziora i kraje składające się z kilku części, których twierdzenie nie obejmuje. Jego znaczenie jest matematyczne: napędzało rozwój teorii grafów i postawiło pytanie, co można uznać za dowód.
Czym jest łańcuch Kempego?
Weź dwa kolory, np. czerwony i niebieski, oraz kraj pokolorowany na czerwono. Jego łańcuch Kempego to zbiór wszystkich czerwonych i niebieskich krajów, do których możesz z niego dotrzeć, przechodząc tylko przez czerwonych i niebieskich sąsiadów. Zamiana czerwonego z niebieskim w całym łańcuchu zachowuje poprawność kolorowania i może zwolnić kolor dla kraju sąsiadującego z łańcuchem.
Dlaczego kraje złożone z kilku części psują twierdzenie?
Jeśli kraj może się składać z oddzielnych obszarów, które wszystkie muszą mieć ten sam kolor, graf sąsiedztwa przestaje być planarny i można zbudować mapy wymagające dowolnej liczby kolorów aż do 12 przy dwóch częściach na kraj, co Heawood badał w swoim problemie imperiów.
Dlaczego aplikacja tworzy mapy z punktów?
Każdy kraj to obszar kwadratu położony bliżej jednego losowego punktu niż jakiegokolwiek innego – diagram Woronoja. Daje to realistycznie wyglądające mapy z wypukłymi krajami, a dwa kraje są sąsiadami dokładnie wtedy, gdy ich obszary mają wspólny odcinek granicy, co aplikacja oblicza precyzyjnie.
Chcesz wypróbować?
Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.
Otwórz kolorowanie mapy czterema kolorami