nauki ścisłe
Autor: Marek Penszko | dodano: 2013-03-19
Śladem Hamiltona

Wierzchołki, krawędzie i cykle

W roku 1859 irlandzki fizyk i matematyk William Rowan Hamilton spłaszczył dwunastościan foremny. Chodziło o to, aby dwunastościenna łamigłówka jego pomysłu, która miała pojawić się w sprzedaży, była łatwa do seryjnej produkcji i poręczna w użyciu. Dziełko Hamiltona wiązało się z raczkującą wówczas teorią grafów, czyli działem matematyki zajmującym się obiektami złożonymi z punktów (wierzchołków) i łączących je linii (krawędzi). To powiązanie sprawiło, że łamigłówka, a właściwie pamięć o niej, przetrwała do dziś.

Rys. 1

 

Rys. 2

Spłaszczenie wielościanu nie było mechanicznym zgnieceniem, lecz szczególnym rodzajem rzutu perspektywicznego – takim, który odwzorowuje na płaszczyźnie wierzchołki i krawędzie bryły w postaci grafu płaskiego. Ze względu na przejrzystość i estetykę pożądane jest, aby, jeśli to możliwe, graf był symetryczny. Rysunek 1 przedstawia dwa rzuty perspektywiczne sześcianu. Oba są symetryczne, choć pierwszy ma jedną, a drugi cztery osie symetrii, jednak tylko drugi może być grafem płaskim, ponieważ jego krawędzie nigdzie się nie przecinają. Dwunastościan foremny (rys. 2a) po spłaszczeniu przez sir Hamiltona zmienił się w graf płaski przedstawiony na rys. 2b. W oryginalnej łamigłówce-zabawce sprzed ponad półtora wieku wierzchołki grafu były otworami w drewnianej płytce. Zabawa polegała na umieszczaniu w nich 20 ponumerowanych kołeczków tak, aby droga wzdłuż krawędzi od kołeczka 1 do 20 wiodła przez kolejne liczby, a ponadto 1 i 20 znajdowały się na końcach tej samej krawędzi. Inaczej mówiąc, należało obejść wszystkie wierzchołki, nie goszcząc dwukrotnie w żadnym – oprócz startowego, który był także metą. Całość miała kojarzyć się z podróżą, bo otwory oznaczone były pierwszymi literami nazw miast wymienionych w instrukcji.

Łamigłówka Hamiltona, zwana „Icosian game” (od greckiego είκοσι – dwadzieścia; liczba wierzchołków), zaowocowała pojawieniem się w teorii grafów trzech pojęć hamiltonowskich: drogi, cyklu i grafu. Droga hamiltonowska przebiega przez wszystkie wierzchołki grafu – przez każdy dokładnie raz; cykl jest drogą zamkniętą, czyli taką, której początek i koniec są połączone krawędzią, a graf hamiltonowski to taki, który zawiera cykl.

 

 

Rys. 3

Oznaczyć cykl Hamiltona w grafie dwunastościanu nietrudno, zwłaszcza po nadaniu mu nieco prostszej, „zaokrąglonej” formy (rys. 3). W przykładzie na rys. 3a najpierw narysowano krótki fragment, łączący trzy okręgi (ciemnozielona linia), potem połączono pozostałe wierzchołki na każdym okręgu (zielona) i na koniec dodano cztery krawędzie-łączniki (seledynowe). W „Icosian game” zadania były nieco inaczej sformułowane, a łamigłówka, zgodnie z nazwą, przypominała grę. Jedna osoba umieszczała pięć kołeczków z liczbami od 1 do 5 w kolejnych otworach, wyznaczając w ten sposób początek cyklu. Druga powinna w określonym czasie umieścić pozostałe, tworząc pełny cykl. Nie było to zbyt trudne. Na rys. 3b zielona linia, łącząca pięć wierzchołków, to początkowy fragment. Rozwiązanie, czyli dokończenie cyklu może wyglądać tak, jak na rys. 3a – ale nie tylko. Istnieje jeszcze jeden cykl z zielonym fragmentem – proszę go oznaczyć. W instrukcji była też propozycja drugiej gry, polegającej na rekonstrukcji drogi Hamiltona. W tym przypadku kołeczkami oznaczano tylko trzy kolejne wierzchołki, zaczynające drogę oraz wskazywano wierzchołek, w którym powinna się ona zakończyć. Przykład zadania na rys. 3c – zielone wierzchołki i krawędzie oznaczają początek i koniec drogi. O ile pierwszy sposób gry ma jako łamigłówka zawsze więcej niż jedno rozwiązanie, o tyle drugi może go wcale nie mieć. Ogólniej mówiąc, nietrudno wskazać w grafie dwunastościanu dwa wierzchołki, których nie sposób połączyć drogą Hamiltona, choć cyklem zawsze można.

Różnych cykli hamiltonowskich na dwunastościanie jest 30, jednak wszystkie są względem siebie „bliźniacze” ze względu na symetrie, a ściślej – grupę symetrii tej bryły. Można je więc sprowadzić do jednego podstawowego cyklu, na przykład takiego, jak na rys. 3a. Hamilton ustalił, że hamiltonowskie są grafy wszystkich brył platońskich. Odtąd zaczęto szukać kryteriów, które powinien spełniać graf, aby był hamiltonowski, oraz sposobów wyznaczania w nim dróg i cykli.

Graf każdego wielościanu wypukłego jest planarny, czyli – mówiąc potocznie – można go zmienić w graf płaski, przesuwając wierzchołki i rozciągając krawędzie tak, aby się nie przecinały. Większość grafów takich wielościanów jest hamiltonowska, ale nie wszystkich. Najmniejsze wyłamujące się to dziewięciościan, którego wszystkie ściany są czworobokami (rys. 4a) i dwunastościan rombowy (rys. 4b). Łatwo sprawdzić, że cyklu hamiltonowskiego w żadnym z nich poprowadzić się nie da, ale warto też przytoczyć sprytny dowód. Zauważmy, że oba grafy są dwudzielne, tzn. wierzchołki każdego z nich można podzielić na dwie grupy tak, że żadne dwa z tej samej grupy nie będą połączone krawędzią. Na rys. 4 grupy wierzchołków oznaczone są różnymi kolorami. Ponieważ każdy czerwony połączony jest krawędzią tylko z czarnymi i odwrotnie, więc w cyklu kolory będą się „przeplatać”, a zatem jednych i drugich powinno być tyle samo. Tymczasem czarnych jest więcej niż czerwonych, więc cyklu być nie może.

 

Rys. 4                                                            



Rys. 5

 

W roku 1880 szkocki fizyk Peter Tait wysunął hipotezę, że każdy graf kubiczny, czyli taki, w którego wszystkich wierzchołkach schodzą się dokładnie 3 krawędzie, jest hamiltonowski. Hipoteza przetrwała do roku 1946, kiedy to angielski matematyk William Tutte zaprezentował graf kubiczny niehamiltonowski o 46 wierzchołkach i 69 krawędziach. Dziewięć lat później Joshua Lederberg (genetyk, noblista z 1958 roku), odkrył najmniejszy znany dotąd kontrprzykład – 38 wierzchołków i 57 krawędzi (rys. 5). W efekcie hipotezę Taita zastąpiła hipoteza Barnette’a: każdy dwudzielny graf kubiczny jest hamiltonowski. Dowodu dotąd nie znaleziono, ale ustalono przy wsparciu komputerowym, że hipoteza jest prawdziwa dla wszystkich grafów o liczbie wierzchołków mniejszej niż 178.

Istnieje jeszcze kilka innych względnie niewielkich grup grafów, o których można powiedzieć, że są na pewno lub z prawdopodobieństwem bliskim pewności hamiltonowskie. Nie znamy natomiast ani w miarę prostego i pewnego sposobu, pozwalającego ustalić, czy jakiś konretny graf takim jest, ani skutecznego algorytmu szukania cyklu Hamiltona. Problem jest istotny, ponieważ ma także znaczenie praktyczne. Optymalizacja wieloetapowych czynności i procesów, w których kolejność etapów nie jest z góry ściśle określona, sprowadza się często właśnie do szukania cyklu lub drogi Hamiltona.

Moda na sudoku, która opanowała świat przed siedmiu laty, utorowała drogę innym rodzajom łamigłówek, rodem głównie z Japonii. Kilka z nich polega na wyznaczaniu cyklu Hamiltona – najczęściej w grafie typowym dla większości zadań diagramowych, czyli prostokątnym fragmencie siatki kwadratowej dowolnej wielkości. Graf taki jest hamiltonowski, jeśli składa się z parzystej liczby rzędów lub/i kolumn. W zadaniach albo graf jest nieco zmodyfikowany, albo warunki są tak sformułowane, by wyznaczany cykl był tylko jeden. Takie są trzy poniższe zadania konkursowe. Wszystkie polegają na narysowaniu linii cyklu hamiltonowskiego biegnącej jasnymi korytarzami. Drugie – wbrew pozorom – też takim jest, tylko cykl jest pokawałkowany.

 

Rys. 6                                                        

Rys. 7                                             

Rys. 8

1. Proszę narysować linię łamaną zamkniętą, przechodzącą przez wszystkie skrzyżowania, przez każde tylko raz (rys. 6). Powinna ona załamywać się w każdym niebieskim skrzyżowaniu i nie załamywać w żadnym różowym. W rozwiązaniu wystarczy podać liczbę wszystkich załamań linii.

2. Każdą parę jednakowych liter należy połączyć linią (rys. 7). W każdym skrzyżowaniu powinna gościć jedna i tylko jedna linia. Linia nie może przecinać litery. W rozwiązaniu wystarczy podać, ile razy załamują się linie łączące poszczególne pary (np. A3, B5,…).

3. Na niektórych skrzyżowaniach (rys. 8) umieszczono blokady (czerwone kółka), ale nie wszystkie są ujawnione. Cyfra i strzałka w ujawnionej blokadzie oznaczają, ile nieujawnionych blokad znajduje się na skrzyżowaniach, na które wskazuje strzałka. Zadanie polega na równoczesnym ujawnieniu wszystkich blokad oraz narysowaniu linii łamanej zamkniętej, przechodzącej przez wszystkie wolne skrzyżowania – przez każde dokładnie raz. Nie wszystkie nieujawnione blokady są wskazane przez strzałki oraz żadne dwie nieujawnione blokady nie znajdują się na sąsiednich skrzyżowaniach. W rozwiązaniu wystarczy podać liczbę nieujawnionych blokad i liczbę załamań linii.

 

Rozwiązania prosimy nadsyłać do 30 kwietnia br. pocztą elektroniczną (swiatnauki@proszynskimedia.pl), wpisując w temacie e-maila hasło UG04/13, lub listownie: Świat Nauki, ul. Rzymowskiego 28, 02–697 Warszawa. Spośród nadawców poprawnych rozwiązań przynajmniej dwóch zadań wyłonimy pięciu zwycięzców i nagrodzimy ich książką Marcusa Chowna, Goverta Schillinga Po prostu Wszechświat, ufundowaną przez wydawnictwo Prószyński Media.

 

Rozwiązanie zadań z numeru lutowego

1. 36, 225, 900, 10404.

2. 134689

3. 16 i 256 lub 31 i 961.

4. x1=1/x, x2=x+1, x3=1/x2=1/(x+1), x4=x1–x3=1/x–1/(x+1)=1/(x2+x), x5=1/x4=x2+x, x6=x5–x=x2.

Za poprawne rozwiązanie przynajmniej dwóch zadań nagrodę, książkę Johna Gribbina Dlaczego jesteśmy, ufundowaną przez wydawnictwo Prószyński Media, otrzymują: Łukasz Rosa z Gdańska, Borys Sochoń z Warszawy, Szymon Sowiński z Niepołomic, Krzysztof Szeruga z Wrocławia, Mariusz Trzyna z Hyżnego.

 

Więcej w miesięczniku „Świat Nauki" nr 04/2013 »
Drukuj »
Komentarze
Dodany przez: m.penszko | 2013-04-13
Stud: dokładnie tak - każda blokada znajduje się na skrzyżowaniu i uniemożliwia poprowadzenie linii przez to skrzyżowanie. mp
Dodany przez: stud | 2013-04-13
Blokada z zadania 3 jest to skrzyżowanie, przez które nie przechodzi linia, tak?
Aktualne numery
11/2017
10/2017 - specjalny
Kalendarium
Listopad
19
W 1912 r. urodził się George Emil Palade, amerykański cytolog, laureat Nagrody Nobla.
Warto przeczytać
Czy znasz powiedzenie że matematykowi do pracy wystarczy kartka, ołówek i kosz na śmieci? To nieprawda! Pasjonującą, efektowną i praktyczną matematykę poznaje się dopiero w laboratorium.

Logowanie

Nazwa użytkownika

Hasło

Autor: Marek Penszko | dodano: 2013-03-19
Śladem Hamiltona

Wierzchołki, krawędzie i cykle

W roku 1859 irlandzki fizyk i matematyk William Rowan Hamilton spłaszczył dwunastościan foremny. Chodziło o to, aby dwunastościenna łamigłówka jego pomysłu, która miała pojawić się w sprzedaży, była łatwa do seryjnej produkcji i poręczna w użyciu. Dziełko Hamiltona wiązało się z raczkującą wówczas teorią grafów, czyli działem matematyki zajmującym się obiektami złożonymi z punktów (wierzchołków) i łączących je linii (krawędzi). To powiązanie sprawiło, że łamigłówka, a właściwie pamięć o niej, przetrwała do dziś.

Rys. 1

 

Rys. 2

Spłaszczenie wielościanu nie było mechanicznym zgnieceniem, lecz szczególnym rodzajem rzutu perspektywicznego – takim, który odwzorowuje na płaszczyźnie wierzchołki i krawędzie bryły w postaci grafu płaskiego. Ze względu na przejrzystość i estetykę pożądane jest, aby, jeśli to możliwe, graf był symetryczny. Rysunek 1 przedstawia dwa rzuty perspektywiczne sześcianu. Oba są symetryczne, choć pierwszy ma jedną, a drugi cztery osie symetrii, jednak tylko drugi może być grafem płaskim, ponieważ jego krawędzie nigdzie się nie przecinają. Dwunastościan foremny (rys. 2a) po spłaszczeniu przez sir Hamiltona zmienił się w graf płaski przedstawiony na rys. 2b. W oryginalnej łamigłówce-zabawce sprzed ponad półtora wieku wierzchołki grafu były otworami w drewnianej płytce. Zabawa polegała na umieszczaniu w nich 20 ponumerowanych kołeczków tak, aby droga wzdłuż krawędzi od kołeczka 1 do 20 wiodła przez kolejne liczby, a ponadto 1 i 20 znajdowały się na końcach tej samej krawędzi. Inaczej mówiąc, należało obejść wszystkie wierzchołki, nie goszcząc dwukrotnie w żadnym – oprócz startowego, który był także metą. Całość miała kojarzyć się z podróżą, bo otwory oznaczone były pierwszymi literami nazw miast wymienionych w instrukcji.

Łamigłówka Hamiltona, zwana „Icosian game” (od greckiego είκοσι – dwadzieścia; liczba wierzchołków), zaowocowała pojawieniem się w teorii grafów trzech pojęć hamiltonowskich: drogi, cyklu i grafu. Droga hamiltonowska przebiega przez wszystkie wierzchołki grafu – przez każdy dokładnie raz; cykl jest drogą zamkniętą, czyli taką, której początek i koniec są połączone krawędzią, a graf hamiltonowski to taki, który zawiera cykl.

 

 

Rys. 3

Oznaczyć cykl Hamiltona w grafie dwunastościanu nietrudno, zwłaszcza po nadaniu mu nieco prostszej, „zaokrąglonej” formy (rys. 3). W przykładzie na rys. 3a najpierw narysowano krótki fragment, łączący trzy okręgi (ciemnozielona linia), potem połączono pozostałe wierzchołki na każdym okręgu (zielona) i na koniec dodano cztery krawędzie-łączniki (seledynowe). W „Icosian game” zadania były nieco inaczej sformułowane, a łamigłówka, zgodnie z nazwą, przypominała grę. Jedna osoba umieszczała pięć kołeczków z liczbami od 1 do 5 w kolejnych otworach, wyznaczając w ten sposób początek cyklu. Druga powinna w określonym czasie umieścić pozostałe, tworząc pełny cykl. Nie było to zbyt trudne. Na rys. 3b zielona linia, łącząca pięć wierzchołków, to początkowy fragment. Rozwiązanie, czyli dokończenie cyklu może wyglądać tak, jak na rys. 3a – ale nie tylko. Istnieje jeszcze jeden cykl z zielonym fragmentem – proszę go oznaczyć. W instrukcji była też propozycja drugiej gry, polegającej na rekonstrukcji drogi Hamiltona. W tym przypadku kołeczkami oznaczano tylko trzy kolejne wierzchołki, zaczynające drogę oraz wskazywano wierzchołek, w którym powinna się ona zakończyć. Przykład zadania na rys. 3c – zielone wierzchołki i krawędzie oznaczają początek i koniec drogi. O ile pierwszy sposób gry ma jako łamigłówka zawsze więcej niż jedno rozwiązanie, o tyle drugi może go wcale nie mieć. Ogólniej mówiąc, nietrudno wskazać w grafie dwunastościanu dwa wierzchołki, których nie sposób połączyć drogą Hamiltona, choć cyklem zawsze można.

Różnych cykli hamiltonowskich na dwunastościanie jest 30, jednak wszystkie są względem siebie „bliźniacze” ze względu na symetrie, a ściślej – grupę symetrii tej bryły. Można je więc sprowadzić do jednego podstawowego cyklu, na przykład takiego, jak na rys. 3a. Hamilton ustalił, że hamiltonowskie są grafy wszystkich brył platońskich. Odtąd zaczęto szukać kryteriów, które powinien spełniać graf, aby był hamiltonowski, oraz sposobów wyznaczania w nim dróg i cykli.

Graf każdego wielościanu wypukłego jest planarny, czyli – mówiąc potocznie – można go zmienić w graf płaski, przesuwając wierzchołki i rozciągając krawędzie tak, aby się nie przecinały. Większość grafów takich wielościanów jest hamiltonowska, ale nie wszystkich. Najmniejsze wyłamujące się to dziewięciościan, którego wszystkie ściany są czworobokami (rys. 4a) i dwunastościan rombowy (rys. 4b). Łatwo sprawdzić, że cyklu hamiltonowskiego w żadnym z nich poprowadzić się nie da, ale warto też przytoczyć sprytny dowód. Zauważmy, że oba grafy są dwudzielne, tzn. wierzchołki każdego z nich można podzielić na dwie grupy tak, że żadne dwa z tej samej grupy nie będą połączone krawędzią. Na rys. 4 grupy wierzchołków oznaczone są różnymi kolorami. Ponieważ każdy czerwony połączony jest krawędzią tylko z czarnymi i odwrotnie, więc w cyklu kolory będą się „przeplatać”, a zatem jednych i drugich powinno być tyle samo. Tymczasem czarnych jest więcej niż czerwonych, więc cyklu być nie może.

 

Rys. 4                                                            



Rys. 5

 

W roku 1880 szkocki fizyk Peter Tait wysunął hipotezę, że każdy graf kubiczny, czyli taki, w którego wszystkich wierzchołkach schodzą się dokładnie 3 krawędzie, jest hamiltonowski. Hipoteza przetrwała do roku 1946, kiedy to angielski matematyk William Tutte zaprezentował graf kubiczny niehamiltonowski o 46 wierzchołkach i 69 krawędziach. Dziewięć lat później Joshua Lederberg (genetyk, noblista z 1958 roku), odkrył najmniejszy znany dotąd kontrprzykład – 38 wierzchołków i 57 krawędzi (rys. 5). W efekcie hipotezę Taita zastąpiła hipoteza Barnette’a: każdy dwudzielny graf kubiczny jest hamiltonowski. Dowodu dotąd nie znaleziono, ale ustalono przy wsparciu komputerowym, że hipoteza jest prawdziwa dla wszystkich grafów o liczbie wierzchołków mniejszej niż 178.

Istnieje jeszcze kilka innych względnie niewielkich grup grafów, o których można powiedzieć, że są na pewno lub z prawdopodobieństwem bliskim pewności hamiltonowskie. Nie znamy natomiast ani w miarę prostego i pewnego sposobu, pozwalającego ustalić, czy jakiś konretny graf takim jest, ani skutecznego algorytmu szukania cyklu Hamiltona. Problem jest istotny, ponieważ ma także znaczenie praktyczne. Optymalizacja wieloetapowych czynności i procesów, w których kolejność etapów nie jest z góry ściśle określona, sprowadza się często właśnie do szukania cyklu lub drogi Hamiltona.

Moda na sudoku, która opanowała świat przed siedmiu laty, utorowała drogę innym rodzajom łamigłówek, rodem głównie z Japonii. Kilka z nich polega na wyznaczaniu cyklu Hamiltona – najczęściej w grafie typowym dla większości zadań diagramowych, czyli prostokątnym fragmencie siatki kwadratowej dowolnej wielkości. Graf taki jest hamiltonowski, jeśli składa się z parzystej liczby rzędów lub/i kolumn. W zadaniach albo graf jest nieco zmodyfikowany, albo warunki są tak sformułowane, by wyznaczany cykl był tylko jeden. Takie są trzy poniższe zadania konkursowe. Wszystkie polegają na narysowaniu linii cyklu hamiltonowskiego biegnącej jasnymi korytarzami. Drugie – wbrew pozorom – też takim jest, tylko cykl jest pokawałkowany.

 

Rys. 6                                                        

Rys. 7                                             

Rys. 8

1. Proszę narysować linię łamaną zamkniętą, przechodzącą przez wszystkie skrzyżowania, przez każde tylko raz (rys. 6). Powinna ona załamywać się w każdym niebieskim skrzyżowaniu i nie załamywać w żadnym różowym. W rozwiązaniu wystarczy podać liczbę wszystkich załamań linii.

2. Każdą parę jednakowych liter należy połączyć linią (rys. 7). W każdym skrzyżowaniu powinna gościć jedna i tylko jedna linia. Linia nie może przecinać litery. W rozwiązaniu wystarczy podać, ile razy załamują się linie łączące poszczególne pary (np. A3, B5,…).

3. Na niektórych skrzyżowaniach (rys. 8) umieszczono blokady (czerwone kółka), ale nie wszystkie są ujawnione. Cyfra i strzałka w ujawnionej blokadzie oznaczają, ile nieujawnionych blokad znajduje się na skrzyżowaniach, na które wskazuje strzałka. Zadanie polega na równoczesnym ujawnieniu wszystkich blokad oraz narysowaniu linii łamanej zamkniętej, przechodzącej przez wszystkie wolne skrzyżowania – przez każde dokładnie raz. Nie wszystkie nieujawnione blokady są wskazane przez strzałki oraz żadne dwie nieujawnione blokady nie znajdują się na sąsiednich skrzyżowaniach. W rozwiązaniu wystarczy podać liczbę nieujawnionych blokad i liczbę załamań linii.

 

Rozwiązania prosimy nadsyłać do 30 kwietnia br. pocztą elektroniczną (swiatnauki@proszynskimedia.pl), wpisując w temacie e-maila hasło UG04/13, lub listownie: Świat Nauki, ul. Rzymowskiego 28, 02–697 Warszawa. Spośród nadawców poprawnych rozwiązań przynajmniej dwóch zadań wyłonimy pięciu zwycięzców i nagrodzimy ich książką Marcusa Chowna, Goverta Schillinga Po prostu Wszechświat, ufundowaną przez wydawnictwo Prószyński Media.

 

Rozwiązanie zadań z numeru lutowego

1. 36, 225, 900, 10404.

2. 134689

3. 16 i 256 lub 31 i 961.

4. x1=1/x, x2=x+1, x3=1/x2=1/(x+1), x4=x1–x3=1/x–1/(x+1)=1/(x2+x), x5=1/x4=x2+x, x6=x5–x=x2.

Za poprawne rozwiązanie przynajmniej dwóch zadań nagrodę, książkę Johna Gribbina Dlaczego jesteśmy, ufundowaną przez wydawnictwo Prószyński Media, otrzymują: Łukasz Rosa z Gdańska, Borys Sochoń z Warszawy, Szymon Sowiński z Niepołomic, Krzysztof Szeruga z Wrocławia, Mariusz Trzyna z Hyżnego.