Delta
  Wiw.pl   Na bieżąco:  Informacje   Co nowego   Matematyka i przyroda:  Astronomia   Biologia   Fizyka   Matematyka   Modelowanie rzeczywistości   Humanistyka:  Filozofia   Historia   Kultura antyczna   Literatura   Sztuka   Czytaj:  Biblioteka   Delta   Wielcy i więksi   Przydatne:  Słowniki   Co i gdzie studiować   Wszechświat w obrazkach    
  Jesteś tutaj:  Wirtualny Wszechświat > Delta > Matematyka - spis artykułów >  CZTERY BARWY I OKOLICE  
  Jesteś tutaj
Wybór artykułów z miesięcznika "Delta"
"Delta" to miesięcznik popularyzujący matematykę, fizykę i astronomię na bardzo wysokim poziomie, wydawany od 1974 roku.
Wirtualny Wszechświat prezentuje wybór tekstów publikowanych w "Delcie" od pierwszego numeru po początek XXI wieku.
  Szukacz
Delta 04/1999
Paweł STRZELECKI
CZTERY BARWY I OKOLICE

Zagadnienie czterech barw i związane z nim problemy kolorowania map (czy też, jeśli ktoś woli bardziej fachową terminologię, grafów) to ciekawy temat, o którym pisaliśmy już w "Delcie", m.in. w numerze 5/1996. Jak wiadomo, podany w 1976 roku przez Hakena i Appela dowód twierdzenia o czterech barwach należy do najbardziej kontrowersyjnych osiągnięć matematyki dwudziestowiecznej, ze względu na wykorzystanie w nim komputerów na niespotykaną wcześniej skalę. Dowód ten nadał nowy sens pytaniom o to, czym właściwie jest dowodzenie i czy każde rozumowanie matematyczne można - poświęciwszy na to odpowiednio dużo czasu - starannie prześledzić i sprawdzić.

Dla tych, którzy w twierdzenie o czterech barwach nie wierzą, mamy dobrą wiadomość. Otóż przed dwoma laty pojawił się nowy dowód tego wyniku, również wykorzystujący komputer, ale w sposób istotnie mniej skomplikowany od tego, co robili Haken i Appel. Jego autorami są panowie: Robertson, Sanders, Seymour i Thomas z Atlanty. Jak piszą we wstępie do swojej pracy, zamierzali - głównie dla spokoju własnych sumień - sprawdzić dowód Appela i Hakena, lecz szybko zamiar porzucili, stwierdzając, że znacznie łatwiej będzie znaleźć nowy, niezależny dowód.

Kto szuka, ten znajdzie: praca wspomnianych czterech autorów, która otwiera tom 70 "Journal of Combinatorian Theory" z 1997 roku, liczy wraz z ilustracjami 43 strony tekstu, napisanego stosunkowo elementarnym językiem. Dwa spośród licznych lematów o kombinatorycznym charakterze zostały dowiedzione z pomocą komputera, lecz, po pierwsze, setka godzin pracy dużej maszyny, której potrzebowali Appel i Haken, została zastąpiona mniej więcej trzema godzinami pracy przeciętnej stacji roboczej, a po drugie, skrócenie czasu obliczeń nie jest jedynie wynikiem postępu w szybkości procesorów. Szczegółowe wydruki z dowodami wspomnianych dwóch lematów zajęłyby mniej więcej jeden rocznik "Delty", można więc sobie wyobrazić, że odpowiednio zacięty człowiek zdołałby je samodzielnie przeczytać i sprawdzić. W przypadku dowodu Hakena i Appela taka operacja byłaby raczej nie do pomyślenia.

Oba komputerowe dowody twierdzenia o czterech barwach zawierają w istocie pewien algorytm kolorowania każdej mapy. Dowód Hakena i Appela prowadzi do algorytmu kolorowania, który działa w czasie proporcjonalnym do czwartej potęgi liczby państw na mapie. Natomiast dowód Robertsona, Sandersa i Seymoura i Thomasa daje algorytm, który mapę złożoną z p państw pozwala pokolorować w czasie rzędu p2, a więc nieporównanie szybciej.

Między starym i nowym dowodem jest jeszcze jedna, dość istotna różnica. Nowy został szybko sprawdzony przez recenzentów, którzy zapędzili swych doktorantów do niezależnego napisania niezbędnych programów, sprawdzających poprawność wspomnianych dwóch lematów - z pozytywnym skutkiem. Ponadto, każdy zainteresowany może poznać wszystkie szczegóły dowodu: wystarczy sięgnąć po "Journal of Combinatorian Theory", a wszystkie programy i dodatkowe informacje ściągnąć z serwera ftp.math.gatech.edu, z dostępnego dla publiczności katalogu pub/users/thomas/four.

Dla tych, którzy sądzą, że z kolorowaniem map wiążą się jedynie rozumowania zawiłe, udowodnimy w dość prosty sposób, iż każdą mapę na płaszczyźnie można dobrze pomalować pięcioma barwami. Słowo "dobrze" tu i dalej oznacza: w taki sposób, by każde dwa państwa, które mają wspólny odcinek granicy, były różnego koloru. Nie będziemy rozważać map, tylko grafy: państwa będą wierzchołkami grafu, a dwa wierzchołki łączymy krawędzią wtedy i tylko wtedy, gdy odpowiadające im państwa graniczą ze sobą. Założymy oczywiście, że graf jest spłaszczalny, tzn. można go narysować na kartce papieru tak, by żadne dwie krawędzie nie przecinały się. Graf jest pokolorowany dobrze, gdy każda krawędź ma końce różnych kolorów.

Podany niżej dowód indukcyjny znalazł pięć lat temu Carsten Thomassen. Żeby ułatwić sobie zadanie, wzmocnimy nieco tezę. Przypuścimy, po pierwsze, że dla każdego wierzchołka w grafu G podana jest pewna lista Lw różnych barw, których można użyć do kolorowania tego wierzchołka. Dla różnych wierzchołków listy mogą być różne, co, jak pokazuje przykład na rysunku 1, wcale nie ułatwia kolorowania.

Rys. 1. Tzw. graf dwudzielny K2, 4 można dobrze pokolorować dwiema barwami (lewa część rysunku). Jednak, gdy dla każdego wierzchołka podamy z góry listę dwóch kolorów, to dobre kolorowanie może nie istnieć (prawa część rysunku): w podanym przykładzie każda para barw, które można wybrać do pomalowania dwóch górnych wierzchołków, stanowi zarazem listę barw dla jednego z dolnych wierzchołków, co jest przyczyną nieuchronnego konfliktu kolorów.

Po drugie, założymy, że dla każdego wierzchołka w na obwodzie grafu (proszę spojrzeć na rysunek 2) lista Lw zawiera trzy kolory, a dla każdego wierzchołka w we wnętrzu grafu - pięć kolorów. Po trzecie, założymy, że wybrane dwa sąsiednie wierzchołki ab, które leżą na obwodzie grafu, już zostały pokolorowane odpowiednio kolorami AB, przy czym A B. Po czwarte wreszcie, założymy bez zmniejszenia ogólności, że krawędzie dzielą wnętrze grafu na "trójkąty". (Gdyby tak nie było, zawsze można dodać nowe krawędzie, pokolorować tak uzyskany graf, a potem dodane krawędzie wytrzeć - stary graf też będzie dobrze pokolorowany).

Rys. 2. Kolorowa linia to obwód grafu G. Wierzchołki oznaczone czarnymi kropkami znajdują się we wnętrzu grafu. Krawędzie dzielą wnętrze grafu na trójkąty.

Przez indukcję względem liczby wierzchołków udowodnimy, że wierzchołki każdego grafu G, który spełnia cztery powyższe założenia, można dobrze pokolorować, kolorując każdy wierzchołek w pewnym kolorem z listy Lw. Początek jest banalny: gdy graf ma tylko trzy wierzchołki, teza jest oczywista. Załóżmy więc, że teza zachodzi dla każdego grafu, który ma nie więcej niż n wierzchołków. Pokażemy, że jeśli G ma n + 1 wierzchołków, to twierdzenie też zachodzi.

Rozważmy dwa przypadki. Załóżmy najpierw, że graf G ma cięciwę, to znaczy krawędź, która łączy dwa niesąsiednie wierzchołki w1 i w2 położone na obwodzie grafu (proszę spojrzeć na rysunek 3).

Rys. 3. Krawędź w1w2 to cięciwa.

Cięciwa dzieli graf G na dwie części G1 G2; każda z tych części ma nie więcej niż n wierzchołków. Przyjmijmy, że wierzchołki ab leżą na obwodzie części G1 (być może któryś z nich pokrywa się z w1 lub w2 - w niczym to nam nie przeszkadza). Korzystając z założenia indukcyjnego, kolorujemy graf G1. Wierzchołki w1 i w2, które są wierzchołkami obwodu grafu G2, zostały pokolorowane różnymi kolorami. Możemy więc powtórnie skorzystać z założenia indukcyjnego i pokolorować graf G2. To kończy dowód kroku indukcyjnego w przypadku, gdy graf G ma cięciwę.

Załóżmy teraz, że G nie ma cięciwy. Niech w1 będzie wierzchołkiem, który na obwodzie grafu G sąsiaduje z a (i jest różny od b, patrz rysunek 4), w2 zaś - różnym od a sąsiadem w1 na obwodzie grafu. Końce krawędzi wychodzących z wierzchołka w1 oznaczmy przez v1, v2,..., vm. Wierzchołki aw2 połączone są łamaną av1v2...vmw2, na rysunku zaznaczoną kolorem.

Rys. 4

Na liście Lw1 kolorów dopuszczalnych dla wierzchołka w1 mamy trzy barwy. Od A, czyli od danej barwy wierzchołka a, różnią się przynajmniej dwie z nich. Dla ustalenia uwagi oznaczmy je CD. Wykreślmy CD z listy kolorów wierzchołków v1, v2, ..., vm. Nowa lista kolorów każdego z tych wierzchołków będzie zawierała (przynajmniej) trzy pozycje.

Niech G' będzie grafem, który powstaje z G przez usunięcie wierzchołka w1 i wszystkich wychodzących zeń krawędzi. Ponieważ G' ma n wierzchołków, więc na mocy założenia indukcyjnego możemy dobrze pokolorować G' (używając do kolorowania v1, v2, ..., vm kolorów z nowych, mniejszych list). Żeby pokolorować cały graf G, trzeba jeszcze tylko wybrać kolor dla wierzchołka w1. Nie jest to jednak kłopot, bowiem przynajmniej jeden z kolorów C i D jest różny od koloru, którym został pomalowany wierzchołek w2. To spostrzeżenie kończy dowód w drugim przypadku.

A co byłoby, gdybyśmy dla każdego wierzchołka grafu mieli podaną pewną listę czterech barw? Otóż, mogłoby się wówczas okazać, że grafu nie da się dobrze pokolorować. Najmniejszy znany przykład takiej sytuacji wymaga narysowania zawiłego grafu, który ma ponad pół setki wierzchołków. Być może niektórym Czytelnikom ta informacja wydaje się zaskakująca, a nawet szokująca. Proszę jednak zauważyć, że nie ma tu żadnej sprzeczności z twierdzeniem o czterech barwach: zakładamy w nim przecież, iż dla wszystkich wierzchołków grafu (jak kto woli, państw na mapie) dana jest jedna i ta sama lista czterech barw.

Uroda matematyki polega zarówno na tego typu zaskakujących odmiennościach, do których prowadzą pozornie nieznaczące zmiany założeń, jak i na tym, że wolno mieć nadzieję, iż ktoś kiedyś znajdzie równie niedługi, elementarny, prosty i elegancki dowód twierdzenia już nie o pięciu, lecz o czterech barwach.




[góra strony]
Wiw.pl  |  Na bieżąco  |  Informacje  |  Co nowego  |  Matematyka i przyroda  |  Astronomia  |  Biologia  |  Fizyka  |  Matematyka  |  Modelowanie rzeczywistości  |  Humanistyka  |  Filozofia  |  Historia  |  Kultura antyczna  |  Literatura  |  Sztuka  |  Czytaj  |  Biblioteka  |  Delta  |  Wielcy i więksi  |  Przydatne  |  Słowniki  |  Co i gdzie studiować  |  Wszechświat w obrazkach