Twierdzenie o czterech barwach: kolorowanie mapy
Niezależnie od tego, jak skomplikowana jest mapa, cztery kolory zawsze wystarczą, aby pokolorować ją tak, by kraje mające wspólną granicę nigdy nie miały tego samego koloru. Sformułowanie jest tak proste, że dziecko może je sprawdzić kredkami, a mimo to udowodnienie go zajęło ponad sto lat i wymagało komputera. Pokoloruj sam losową mapę, zobacz, które granice są w konflikcie, a potem obserwuj, jak robią to trzy metody – od szybkiej reguły zachłannej, która czasem potrzebuje piątego koloru, po przeszukiwanie z nawrotami, które zawsze radzi sobie czterema. Wybierz kolor i klikaj kraje, aby je pomalować; granica robi się czerwona, gdy dwa sąsiednie kraje mają ten sam kolor. Kraje, które stykają się tylko narożnikiem, mogą mieć ten sam kolor. Możesz też zostawić to komputerowi: wybierz metodę i naciśnij Rozwiąż, aby obserwować jej działanie, albo Krok, aby śledzić ją ruch po ruchu. Najmniej kolorów sprawdza, czy ta mapa obeszłaby się trzema, a nawet dwoma kolorami. Nowa mapa rysuje inną mapę, a Pokaż sąsiadów rysuje sieć krajów, które mają wspólną granicę.
Jak to działa
- Wybierz liczbę krajów i naciśnij Nowa mapa albo zacznij od widocznej mapy.
- Wybierz kolor i klikaj kraje, aby je pomalować, zwracając uwagę na czerwone granice tam, gdzie sąsiedzi są w konflikcie.
- Wybierz metodę i naciśnij Rozwiąż lub Krok, aby zobaczyć, jak koloruje mapę, a potem naciśnij Najmniej kolorów, aby sprawdzić, ilu kolorów potrzebuje ta mapa.
Od map do grafów
Postaw kropkę w każdym kraju i połącz dwie kropki, jeśli ich kraje mają wspólną granicę. Mapa staje się grafem, a kolorowanie mapy to to samo co kolorowanie kropek tak, by połączone kropki się różniły. Ponieważ mapy rysuje się na płaskiej kartce, te grafy są planarne: można je narysować bez przecinających się linii. Kraje stykające się w jednym punkcie, jak cztery kwadraty w narożniku, nie są sąsiadami. Twierdzenie o czterech barwach mówi, że każdy graf planarny można pokolorować czterema kolorami. Włącz Pokaż sąsiadów, aby zobaczyć graf bieżącej mapy.
Trzy sposoby kolorowania
Kolorowanie zachłanne bierze kraje po kolei, najpierw te z największą liczbą sąsiadów, i daje każdemu pierwszy kolor, którego nie użyli jego sąsiedzi. Jest szybkie, ale krótkowzroczne i na niektórych mapach sięga po piąty, a nawet szósty kolor. DSATUR, wymyślony przez Daniela Brélaza w 1979 roku, zawsze wybiera jako następny kraj, którego sąsiedzi mają już najwięcej różnych kolorów, co zwykle pozwala uniknąć tej pułapki. Przeszukiwanie z nawrotami próbuje kolejnych kolorów, a gdy dla jakiegoś kraju nie zostaje żaden, cofa ostatnie wybory i próbuje ponownie; zawsze znajduje kolorowanie czterema kolorami, czasem po wielu nawrotach.
Często zadawane pytania
Dlaczego cztery kolory zawsze wystarczą?
Nikt nie znalazł krótkiego uzasadnienia. Dowód Kennetha Appela i Wolfganga Hakena z 1976 roku pokazał, że każda mapa musi zawierać jedną z 1936 małych konfiguracji i że każdą z nich można usunąć, a kolorowanie później odtworzyć; sprawdzenie ich wszystkich zajęło ponad tysiąc godzin pracy komputera. Prostszy dowód komputerowy Neila Robertsona, Daniela Sandersa, Paula Seymoura i Robina Thomasa z 1996 roku wymaga 633 konfiguracji, a w 2005 roku Georges Gonthier w pełni zweryfikował dowód za pomocą asystenta dowodzenia Coq.
Czy niektóre mapy wymagają wszystkich czterech kolorów?
Tak. Cztery kraje, z których każdy styka się z trzema pozostałymi, jak kraj otoczony pierścieniem trzech innych, wymagają czterech. Wiele map obchodzi się jednak trzema, a Najmniej kolorów sprawdza to dla mapy na ekranie. Rozstrzygnięcie w ogólnym przypadku, czy mapę można pokolorować trzema kolorami, jest trudnym problemem, NP-zupełnym, choć cztery kolory zawsze wystarczą.
Dlaczego metoda zachłanna czasem używa pięciu kolorów?
Koloruje każdy kraj raz i nigdy nie zmienia zdania. Wczesny wybór może sprawić, że późniejszy kraj zostanie otoczony wszystkimi czterema kolorami, a jedynym wyjściem jest piąty. Przeszukiwanie z nawrotami zamiast tego cofnęłoby się i zmieniło wcześniejsze wybory.
Czy twierdzenie jest prawdziwe na innych powierzchniach?
Na sferze tak: to to samo co płaszczyzna. Na torusie, czyli powierzchni pączka z dziurką, niektóre mapy wymagają siedmiu kolorów, a siedem zawsze wystarcza, jak pokazał Percy Heawood. Jeśli kraje mogą się składać z kilku oddzielnych części, jak państwo z koloniami, cztery kolory przestają wystarczać.
Czy coś jest wysyłane na serwer?
Nie. Mapa, metody kolorowania i sprawdzanie działają w twojej przeglądarce. Twoje ustawienia zostają w pamięci lokalnej tej przeglądarki.
Chcesz wypróbować?
Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.
Przejdź do edytora