Twierdzenie o czterech barwach

Niniejszy artykuł jest częścią cyklu teoria grafów.




Najważniejsze pojęcia
graf
drzewo
podgraf
cykl
klika
stopień wierzchołka
stopień grafu
dopełnienie grafu
obwód grafu
pokrycie wierzchołkowe
liczba chromatyczna
indeks chromatyczny
izomorfizm grafów
homeomorfizm grafów


Wybrane klasy grafów
graf pełny
graf spójny
drzewo
graf dwudzielny
graf regularny
graf eulerowski
graf hamiltonowski
graf planarny


Algorytmy grafowe
A*
Bellmana-Forda
Dijkstry
Fleury'ego
Floyda-Warshalla
Johnsona
Kruskala
Prima
przeszukiwanie grafu
wszerz
w głąb
najbliższego sąsiada


Zagadnienia przedstawiane jako problemy grafowe
problem komiwojażera
problem chińskiego listonosza
problem marszrutyzacji
problem kojarzenia małżeństw


Inne zagadnienia
kod Graya
diagram Hassego
kod Prüfera


Twierdzenie o czterech barwach – dla każdego skończonego grafu planarnego istnieje funkcja taka że czyli możliwe jest przypisanie każdemu z jego wierzchołków jednej z czterech liczb 1, 2, 3 i 4 w taki sposób, aby żadne sąsiednie wierzchołki nie miały przyporządkowanej tej samej liczby. Jest to jeden z najsłynniejszych problemów matematycznych.

Four Colour Planar Graph.svg
Równoważność zagadnienia dla mapy i dla grafu

Sformułowanie równoważne (mniej ścisłe matematycznie, lecz bardziej przemawiające do wyobraźni):

dowolną mapę polityczną, na płaszczyźnie lub sferze, można zabarwić czterema kolorami tak, aby każde dwa kraje mające wspólną granicę (nie tylko wspólny wierzchołek) miały inne kolory (zakładamy, że wszystkie państwa są spójne terytorialnie).

Równoważność tych dwóch sformułowań łatwo zauważyć wyróżniając w każdym „kraju” „stolicę” i prowadząc „drogi” pomiędzy stolicami każdych dwóch sąsiednich krajów. Przechodzimy wówczas z mapy politycznej do grafu opisanego w pierwszym z obu sformułowań twierdzenia. Analogicznie można przejść w przeciwną stronę.

Hipotezę o prawdziwości twierdzenia postawił już w roku 1840 August Ferdinand Möbius[1], a w roku 1852 (niezależnie) Francis Guthrie (1831–1899), wówczas student University College London, ale pełny dowód został przeprowadzony dopiero w 1976 roku przez Wolfganga Hakena i Kennetha Appela. Dowód wszakże był bardzo „brzydki”, gdyż wymagał sprawdzenia 1936 przypadków szczególnych przy pomocy komputera. Pojawiały się nawet wątpliwości, czy dowód jest poprawny[2].

Wątpliwości te usunięto za pomocą jego modyfikacji w 1994, a w 2004 udało się potwierdzić poprawność przy użyciu komputerowego asystenta. Nikt dotąd nie udowodnił twierdzenia o czterech barwach bez komputerowego wspomagania, choć wymyślono pewne uproszczenia oryginalnego dowodu. Przypadek ten stał się okazją do dyskusji na temat dopuszczalnych metod dowodowych w matematyce.

Uogólnienia na przypadek innych powierzchni

Istnieje uogólnienie twierdzenia o czterech barwach także dla grafów rozpiętych na powierzchniach topologicznych, które nie są homeomorficzne ze sferą lub płaszczyzną: dla każdej powierzchni liczba kolorów potrzebnych do zabarwienia dowolnej narysowanej na niej mapy politycznej tak, aby dwa sąsiednie kraje nie miały tej samej barwy, jest równa maksymalnej liczbie krajów na tej powierzchni, z których każdy graniczy z każdym innym.

Na różnych powierzchniach liczba ta może być różna, na przykład na torusie (powierzchnia dętki) liczba ta wynosi 7 – matematycy korzystający z map w kształcie torusa uznaliby za ważniejsze dowodzenie „twierdzenia o siedmiu barwach”.

Dla sfery i płaszczyzny uogólnione twierdzenie też jest prawdziwe, gdyż maksymalna liczba krajów, z których każdy dotyka każdego, jest na nich równa 4 (jeden kraj w środku i trzy dookoła).

To uogólnione twierdzenie dla wszelkich powierzchni poza sferą i płaszczyzną zostało udowodnione wcześniej niż twierdzenie o czterech barwach, i bez komputera. Pokonanie twierdzenia o czterech barwach uzupełniło więc dowód dla ostatnich dwóch szczególnych przypadków.

Zobacz też

Przypisy

  1. Marek Kowalski: Czy wszystko da się obliczyć? (pol.). W: Wykład akademicki (pps) [on-line]. www.perspektywy.org. [dostęp 2014-03-30].
  2. Agnieszka Rudzik-Sawicka (na podstawie artykułu Robina Wilsona, zamieszczonego w „Delta” 04/2009): Ilu kolorów potrzeba do pomalowania mapy? (pol.). W: Szkoła z klasą (blog). O matematyce i nie tylko… [on-line]. 10 stycznia 2013. [dostęp 2014-03-31]. [zarchiwizowane z tego adresu (2014-04-07)].

Bibliografia

  • Oryginalny dowód twierdzenia o czterech barwach: K. Appel and W. Haken. Every planar map is four colorable. Bulletin of the American Mathematical Society, wol. 82, 1976, s. 711–712.
  • Modyfikacja, która usunęła wątpliwości co do dowodu: N. Robertson, D. Sanders, P. Seymour, R. Thomas The Four Colour Theorem Preprint, luty 1994.
  • Doniesienie o sprawdzeniu poprawności dowodu za pomocą komputerowego asystenta: Devlin’s Angle, Last doubts removed about the proof of the Four Color Theorem, styczeń 2005

Linki zewnętrzne

Media użyte na tej stronie

Four Colour Planar Graph.svg
Autor: Inductiveload, Licencja: CC-BY-SA-3.0
Diagram showing a map coloured with four colours being transformed into a planer graph. See this Wikipedia article for more information.