Dwie rocznice

Wspomnę o bardziej poważnym światowym wyróżnieniu, związanym z Erdősem. Od 35 lat przyznawana jest prestiżowa nagroda jego imienia za działalność w olimpiadach matematycznych. W tym roku (2026) otrzymał ją Michał Krych z Uniwersytetu Warszawskiego. Jest on drugim polskim laureatem tej nagrody. Pierwszym był Marcin Kuczma, też z Uniwersytetu Warszawskiego (1992). Dla ścisłości wspomnę, że wtedy nagroda ta funkcjonowała jako „nagroda Hilberta”. Kilka słów o Hilbercie – nieco dalej. Obaj uczeni, Erdős i Hilbert, to filary współczesnej matematyki. Dlatego ranga tych nagród jest bardzo wielka. Gratuluję Michałowi (Marcinowi gratulowałem owe 34 lata temu).

Przejdę do kolorowania grafów – czyli punktów połączonych odcinkami. Co w tym trudnego? Oj, to bywa bardzo trudne. Czy zajmowanie się takimi zadaniami ma sens? Tak, od kilkudziesięciu lat analiza kolorowych grafów ma dużo zastosowań. Po kolei.

***

Czy wiesz, Czytelniku, że pierwszym zagadnieniem matematycznym rozwiązanym za pomocą programu komputerowego było zagadnienie czterech barw? Zaczęło się to 23 października 1852 roku. Pewien student brytyjski, Francis Guthrie, zauważył wtedy, że każdą mapę umie pokolorować czterema kolorami w ten sposób, że obszary mające wspólną granicę są zaznaczone różnymi kolorami. Zapytał znanego matematyka Augustusa De Morgana, czy to jest ogólnie prawdziwe. Ten po dłuższym czasie odpisał, że nie wie i nie umie tego udowodnić. Zagadnienie stało się sławne. Wielu matematyków próbowało rozwiązać ten problem. W 1879 roku dowód opublikował Alfred Kempe i wydawało się, że sprawa się zakończyła. Ale w kilka lat potem znaleziono błąd w tym dowodzie. Dało się tylko uratować „twierdzenie o pięciu barwach” – że pięć kolorów wystarczy. Ten dowód nie jest bardzo skomplikowany, choć też wykracza poza ramy tego kącika.

Rysunki 1 i 2 pokazują, o co chodzi. Na pierwszym mamy pięć kolorów i nie możemy zamienić czerwonych obszarów na żadne inne. Wydaje się więc, że tych pięć kolorów jest niezbędnych. Wystarczy jednak inaczej ustawić kolory i widzimy, że cztery istotnie wystarczą.

Rysunek 1 i 2

Zagadnienie przeszło na XX wiek. Należy wspomnieć o tzw. 23 problemach Hilberta. David Hilbert, niekwestionowany lider matematyków owych czasów, w 1900 roku sformułował najważniejsze zagadnienia matematyczne do rozwiązania w nadchodzącym wtedy XX stuleciu. Nie włączył do tej listy zadania o czterech barwach. W oczach współczesnych matematyków miało ono charakter bardziej „łamigłówkowy”, a poza tym nie wpisywało się w główne kierunki badań Hilberta. Dopiero potem zadanie to stało się sławne – właśnie przez to, że w 1976 roku rozwiązali je Kenneth Appel i Wolfgang Haken przy użyciu komputerów, co było wtedy czymś przełomowym (i kontrowersyjnym).

3.

Zresztą trochę jest tak, jak czuł Hilbert. Niektóre twierdzenia matematyczne są trudne, a nawet bardzo trudne, ale nie są specjalnie ważne z ogólnego punktu widzenia. Jeżeli porównać matematykę do eksploracji wysokich gór, to można powiedzieć, że są one jak samotnie stercząca skała na uboczu. Trudna, ale nie zawadza w eksploracji. Istotne jest tylko to, że zagadnienie to wpisuje się w intensywnie rozwijaną od około 50 lat teorię grafów. Grafy okazały się nadzwyczaj ważnym pojęciem matematycznym. Ważnym dla samej matematyki, ale przede wszystkim dla zastosowań – co pokazują dalsze zadania.

4.

Wspomnijmy jeszcze Francisa Guthrie (1831–1899). W 1861 roku wyjechał na stałe do Afryki Południowej. Został profesorem na Uniwersytecie w Kapsztadzie. Prowadził tam również badania botaniczne. Rozwiązania odkrytego przez siebie problemu, jak widać, nie doczekał.

5.

Zadanie 1. Poniżej widzisz schematyczną mapę sąsiedztwa krajów europejskich (bez państw wyspowych i Skandynawii, ale z Liechtensteinem, Andorrą i San Marino). Czy widzisz, że nie da się jej pokolorować trzema kolorami? Zobacz – wszystko psuje mały Luksemburg! Gdyby nie on, to trzy kolory wystarczyłyby. Pokoloruj czterema.

6.

Zadanie 2. ma sformułowanie jak w filmie akcji, ale po przeczytaniu proszę przetłumaczyć je na całkiem „cywilną” i pokojową sytuację. Mamy ułożyć plan lekcji. Niektóre zajęcia nie mogą się odbywać jednocześnie (na przykład prowadzi je ten sam nauczyciel albo niektórzy uczniowie chodzą na obydwa). W jednej sali nie może być jednocześnie dwóch różnych zajęć. Być może są jeszcze inne uwarankowania, nawet niecałkiem poważne – na przykład prof. X nie chce mieć lekcji po prof. Y, bo uważa, że po lekcji z nim uczniowie są zbyt „rozbrykani”. Teraz owo zadanie z wątkiem szpiegowskim.

7.

Zadanie 2. Xylonia i Yxlonia to dwie wyspy na Oceanie Kolorowym. Panuje między nimi wrogość. Xylonia wysłała do Yxlonii szpiegów. Ich dane są oczywiście tajne, a ich pseudonimy operacyjne to: Arbuzy, Brunacy, Czarusia, Drapichrust, Endokrynologia, Falafel i Gradacja. Pracują nad powierzonymi zadaniami, ale niezależnie. Nie znają się nawzajem. To po pierwsze dla bezpieczeństwa, ale również po to, by Centrala mogła ich doniesienia łatwiej weryfikować. Jak to szpiedzy, mają bowiem przekazywać meldunki do centrali. Robią to tak, jak na filmach z Klossem. W określone dni tygodnia o godzinie 11 wrzucają kartkę z meldunkiem do umówionych koszy na śmieci na ulicy. Meldunek wyjmuje o godzinie 12 wysłannik centrali, przebrany za pracownika Zakładu Oczyszczania Miasta. Jak przydzielić kosze na śmieci, żeby szpiedzy, którzy mają te same zadania, nie spotykali się?

1. Arbuzy pracuje nad tymi samymi tematami co Brunacy, Czarusia i Drapichrust.
2. Brunacy pracuje nad tymi samymi co Arbuzy, Czarusia i Endokrynologia.
3. Czarusia nad tymi samymi co Arbuzy, Brunacy i Drapichrust.
4. Drapichrust ma te same zadania co Arbuzy, Czarusia, Endokrynologia i Falafel.
5. Endokrynologia – to samo co Brunacy, Czarusia, Drapichrust i Falafel.
6. Falafel – to samo co Drapichrust i Endokrynologia.

Jaki to ma związek z kolorowaniem grafu? Oczywisty – trzeba narysować schemat systemu uwarunkowań i pokolorować go zgodnie z przyjętą zasadą (końce każdego odcinka mają różne kolory). To oczywiście łatwe i bez wielkiej matematyki, ale gdy w grę wchodzą dziesiątki osób i dziesiątki ograniczeń, trzeba użyć matematyki.

Jeżeli nie zależy nam na optymalnym rozwiązaniu, można użyć tak zwanego algorytmu zachłannego. Po prostu kolorujemy po kolei. Jeżeli zabraknie koloru, dokładamy następny. I tu właśnie cała trudność. Rozwiązanie będzie – ale może być za skomplikowane. Ułożony plan zajęć będzie nieżyciowy. Potrzebna jest lepsza matematyka.

Zadanie 3. Do obszaru działania naszej siatki z poprzedniego zadania doszła jeszcze jedna ważna sprawa, ale tak tajna, że nikt nie wie, o co chodzi. Tym niemniej przydzielono do niej Czarusię i Falafela. Narysuj graf zależności i przydziel na nowo kosze na śmieci. Czy potrafisz uzasadnić, że naprawdę potrzeba czterech kolorów?

Zadanie 4. W ogródkach działkowych są ujęcia wody do podlewania w punktach A, B, C, D, E, P, Q, R, S, T, X. Niebieskie linie pokazują, dokąd ciągnie się rura z danego punktu. Z powodu długotrwałej suszy wprowadzono nakaz, że żadnego dnia nie mogą być włączone ujęcia z obu stron jednego odcinka. Jak ustawić kolejność podlewania? Jaki to ma związek z kolorowaniem grafu?

Odpowiedź. W kolejne dni włączane są ujęcia: zielone, czarne, czerwone, niebieskie. Na przykład w dniu „czerwonym” woda dostępna jest na odcinkach SE, SD, SC, SX, PA, PX, PB.

Zadanie 5. Najpierw dowiedz się, co to jest mandala – choć nie ma to wiele wspólnego z zadaniem. Pokoloruj widoczną niżej mandalę, zgodnie z regułą, że końce każdego odcinka (łuku) mają mieć różne kolory. Oczywiście chodzi o jak najmniejszą liczbę kolorów.

Zadanie 6. Zarząd amerykańskiej sieci fast food „Eat here” postanowił sprawdzić, czy pewna restauracja w miasteczku Oconomowoc w stanie Wisconsin spełnia ogólne normy tej sieci. W tym celu czworo członków zarządu i ośmioro pracowników niższego szczebla wybrało się do tej restauracji. Zarząd usiadł na miejscach na zewnątrz, pracownicy przy stolikach ustawionych wewnątrz, w kształcie ośmiokąta. Menu restauracji to: 1) kurczak z frytkami i ketchupem, 2) pizza z pieczarkami i ketchupem, 3) cheeseburger z sosem serowym, 4) chińska zupa wonton. Zażądano, by wszyscy, których łączy odcinek na załączonym schemasie (rysunek 8), dostali co innego. W ten sposób Zarząd dostałby dwie opinie od dwóch swoich członków i od dwóch pracowników, a każdy z pracowników jedną od członka Zarządu i trzy niezależne od swoich kolegów.

1. Znajdź na mapie USA tę miejscowość.
2. Zaproponuj, co kto ma dostać.
3. Czy da się to tak zrobić, żeby Zarząd nie dostał dania z ketchupem?
4. Postaraj się to zrobić za pomocą mex.
5. Wyobraź sobie, że ajent w tej restauracji oświadcza, że jest sorry, ale nie może dziś zrobić pizzy, bo zepsuł się piekarnik. Czy da się spełnić wymagania Zarządu za pomocą dostępnych trzech dań?

8.

Komentarz. Taki graf nosi nazwę grafu Chvátala. Václav Chvátal jest Czechem. Wyjechał do USA trzy dni po inwazji radzieckiej w 1968 roku. Spotkałem go w Montrealu w 1984 roku; dziwił się, że nie zamierzam zostać na emigracji. W teorii grafów jego nazwisko wiele znaczy.

Zadanie 7. W pięknym i atrakcyjnym turystycznie miasteczku Barwigród Pentagonalny jest uroczy rynek w kształcie pięciokąta (rysunek 9). Kilka lat temu zarzucono tam politykę „betonozy” i rynek jest teraz cały w kwiatach i krzewach, a rosną już nowe drzewa. W narożnikach tego rynku jest pięć zabytkowych kamienic, a w centralnej części rynku też pięć malutkich restauracji. Między nimi są alejki spacerowe. W samym środku jest ratusz. Pewnego razu burmistrz Barwigrodu, Gwidon Koloryński, wpadł na pomysł, który jego zdaniem jeszcze podniesie atrakcyjność miasteczka. „Pomalujmy kamieniczki, restauracje i mój ratusz wesołymi kolorami, ale tak, żeby budynki na dwóch końcach każdej alejki były w innym kolorze”. Radni zgodzili się i już-już zamówiono jedenaście kolorów, ale burmistrz oburzony zakrzyknął: „Co wy, matematyki nie znacie, chcecie mi tu jakąś pstrokaciznę zrobić, a poza tym stracilibyśmy fundusze unijne za niegospodarność. Cztery podstawowe kolory są po prostu tańsze, no i wykorzysta się je bardziej ekonomicznie. Zaprojektować mi wszystko w czterech kolorach! A jak się da, to może w trzech. Ale wydaje mi się, że trzy to za mało.” A zatem pomożecie?

9.

Komentarz. Ten graf jest w matematyce nazywany grafem Mycielskiego M3. Jan Mycielski (1932–2025) był polskim matematykiem – choć teraz mówi się „polsko-amerykańskim”. Wyjechał do USA w 1986 roku jako „visiting professor” na prestiżowy Uniwersytet w Boulder w stanie Kolorado i został tam na stałe. Graf ten nie jest może czymś wyjątkowym, ale jest to początek całej serii grafów Mycielskiego, ważnych w tej dyscyplinie matematyki.

***

Od pewnego czasu przypatruję się felgom samochodowym (bądź plastikowym kołpakom) i odkrywam na nich często interesującą geometrię. Dziś o felgach związanych z zagadnieniem kolorowania.

Na fotografii (rysunek  10) widzimy częsty motyw felgi aluminiowej w samochodach Peugeot. Trochę przypomina on graf złożony z dwóch pięciokątów (rysunek  11). Po raz pierwszy zwrócił na niego uwagę duński matematyk Julius Petersen (1838–1910). Wtedy teoria grafów wydawała się czystą ciekawostką i układanką –  trochę jak dzisiejsze puzzle. W wierzchołkach grafu Petersena można tak umieścić koraliki trzech kolorów, żeby dwa końce każdego odcinka były w różnych kolorach. Więcej kolorów (bo cztery) potrzeba do innego kolorowania. Mianowicie gdy budujemy ten ornament (dygresja: czy wiesz, co to jest makrama?) ze sznurków różnych kolorów. Chcemy, by w każdym węźle mieć trzy różne kolory. Graf Petersena jest przykładem żmirłacza. Czego? Nie słyszałeś tego słowa, Czytelniku? Najpierw: czy wiesz, że Lewis Carroll (ten od „Alicji w Krainie Czarów”) był matematykiem? No, to już wiesz. Otóż w 1876 roku napisał on abstrakcyjny poemat „The Hunting of the Snark”. Takiego słowa „snark” nie ma w angielszczyźnie – on je utworzył. Było to coś pomiędzy snake (wąż) a shark (rekin). W 1982 roku Robert Stiller przetłumaczył to (i cały poemat) na polski jako „Wyprawa na żmirłacza”, błyskotliwie oddając sens oryginalnego połączenia. A w samej matematyce żmirłaczem (snark) nazwano, no cóż, graf stopnia 3 z indeksem chromatycznym 4. Chodzi o to, że z każdego wierzchołka wychodzą po trzy krawędzie, wybrane spośród czterech (tak jak na rysunku 12). Ale nie będę się zagłębiał w teorię grafów, bo mam jeszcze wiele ciekawego do opowiedzenia. Może innym razem.

10.

11.

13.

***

Jeden z moich sąsiadów ma dużego, paliwożernego SUV-a, z taką felgą jak na fotografii poniżej po lewej stronie. Obok widzisz wielokąt (graf), podobny do tej felgi. Wprawne oko matematyka zobaczy na nim… połowę dwunastościanu. Pokoloruj wierzchołki tego wielokąta zgodnie z regułą z poprzednich zadań.

14.

***

I to samo dla innej felgi (rysunek 15 i 16). Najpierw odgadnij markę tego samochodu. Poprosiłem AI, żeby poszukała, czy jest to jakiś znany graf. Odpowiedziała bez ładu i składu, byle co, zgodnie z zasadą „będzie pan zadowolony”. Nie będę przytaczał tych jej wypowiedzi. Sam poszukam. Ale jedna jej odpowiedź była ciekawa. Poprosiłem: na podstawie zdjęcia (rysunek 15) stwórz sama odpowiedni graf i ładnie go narysuj. „Proszę bardzo”, odpowiedziała i pokazała rysunek 17. Nie widzę związku, ale rysunek ładny.

15.

16.

***

Zachwyć się grafem na rysunku 18. Pokoloruj jego wierzchołki (koraliki) zgodnie z zasadą, o której tu cały czas chodzi: koraliki na końcach tego samego odcinka mają mieć różne kolory. Ile najmniej kolorów potrzeba? Pokoloruj krawędzie (odcinki) zgodnie z zasadą przy rysunku 12 – wszystkie krawędzie wychodzące z jednego wierzchołka muszą mieć inny kolor. Jeżeli uważasz, że to zbyt żmudne, to tylko odpowiedz: ilu kolorów najmniej potrzeba? To proste: spójrz na wierzchołki dużego pięciokąta.

17.

18.

***

Zacząłem od Pála Erdősa. O jego pracach o kolorowaniu grafów można napisać duży artykuł. Wspomnę jeden z ulubionych jego problemów, za rozwiązanie którego obiecał w 1972 roku nagrodę 500 dolarów. Była to tak zwana hipoteza Erdősa–Fabera–Lovásza. Samo sformułowanie jest dość skomplikowane, ale przytoczę je. Mamy n grafów pełnych (czyli takich, gdzie każdy koralik jest połączony z każdym innym). Każdy z tych grafów ma dokładnie n wierzchołków. Jeśli te grafy nakładają się na siebie w taki sposób, że każde dwa grafy mają co najwyżej jeden wspólny wierzchołek, to czy cały ten układ da się pokolorować, używając tylko n kolorów?

W 2021 roku piątka matematyków (Dong Yeap Kang, Tom Kelly, Stefan Kühn, Abhishek Methuku i Deryk Osthus) rozwiązała ten problem. Spadkobiercy wypłacili owe pół tysiąca USD, czyli po 100 na głowę; może wystarczyło na średnio wytworną kolację. Ale nie w tym tkwi wartość nagrody. Erdős był znany z tego, że „wyceniał” problemy matematyczne w zależności od ich trudności. Ceny wahały się zazwyczaj od 10 do 3000 dolarów. Za życia wypłacał je z własnej kieszeni. Sam mówił o tym z humorem, twierdząc, że wyznaczenie nagrody to sposób na skupienie uwagi młodych talentów na konkretnym zagadnieniu. Nagrody stały się tak kultowe, że dla matematyka czek podpisany przez niego (lub pośmiertne uznanie nagrody) jest wart wielokrotnie więcej niż wartość nominalna.

To optymistyczne, prawda? 

Michał Szurek

Źródła ilustracji: rysunki 1 i 2 – Wikipedia, hasło „twierdzenie o czterech barwach”. Rysunki 7, 9, 11, 17, 18 – Gemini (według poleceń autora). Pozostałe fotografie i rysunki – autor.