Początek badań w tej sprawie sięga 1852 roku. Francis Guthrie, brytyjski matematyk, podczas kolorowania mapy angielskich hrabstw zauważył, że do rozróżnienia wszystkich sąsiadujących regionów wystarczą cztery kolory. Zaczął się zastanawiać, czy taka zasada obowiązuje w przypadku każdej możliwej mapy. Pytanie szybko zainteresowało matematyków, którzy przez kolejne dekady bezskutecznie próbowali znaleźć jego uzasadnienie.
Tak narodziło się twierdzenie o czterech barwach. Jego treść jest wyjątkowo prosta: każdą mapę podzieloną na rozłączne obszary można pokolorować maksymalnie czterema kolorami, tak aby żadne dwa obszary mające wspólną granicę nie były oznaczone tą samą barwą. Problem okazał się jednak znacznie trudniejszy, niż sugerowałoby jego sformułowanie.
Pierwszą próbę udowodnienia twierdzenia przedstawił w 1879 roku Alfred Bray Kempe. Jego rozwiązanie przez jedenaście lat uznawano za poprawne, zanim matematyk Percy John Heawood odkrył w nim błąd. Mimo to część pomysłów Kempego stała się fundamentem późniejszych badań. Przełom nastąpił dopiero w 1976 roku. Kenneth Appel i Wolfgang Haken przedstawili dowód, który po raz pierwszy wykorzystywał komputer do sprawdzenia ogromnej liczby matematycznych konfiguracji. Badacze ograniczyli problem do 1482 przypadków, które następnie zweryfikowały komputery Uniwersytetu Illinois.
Rozwiązanie wywołało kontrowersje, a niektórzy matematycy zastanawiali się, czy dowód wspomagany komputerowo można uznać za pełnoprawny. Wątpliwości stopniowo rozwiewały się wraz z rozwojem technologii. W 1997 roku światło dzienne ujrzała udoskonalona wersja, która wymagała sprawdzenia 633 konfiguracji. Wydawało się, że sprawa jest zamknięta. Ale nie dla wszystkich.
Najnowszy rozdział tej historii rozpoczął się w 2015 roku. Po niemal dekadzie pracy naukowcy opracowali nowy dowód, ponownie potwierdzają prawdziwość twierdzenia. Opracowali również znacznie wydajniejszą metodę kolorowania grafów. Wykorzystali w tym celu 8202 konfiguracje, które można redukować równolegle, zamiast analizować je pojedynczo. Dzięki temu procedura jest zdecydowanie szybsza niż wcześniejsze rozwiązania.
Czytaj też: Materiał, który zmienia kolor, choć tego nie zobaczysz. Naukowcy wypowiedzieli wojnę podróbkom
Odkrycie może mieć znaczenie również poza samym problemem kolorowania map. Nowe narzędzia pomagają lepiej zrozumieć strukturę tzw. grafów planarnych, czyli matematycznych modeli złożonych z punktów połączonych liniami, które nie przecinają się poza wspólnymi wierzchołkami. Znajdują one zastosowanie między innymi w informatyce, analizie sieci i modelowaniu różnych zjawisk.
Źródło: Smithsonian Magazine
