Problem chińskiego listonosza

Dlaczego listonosza ?
W swojej pracy, listonosz wyrusza z poczty, dostarcza przesyłki adresatom, by na koncu powrócić na pocztę. Aby wykonać swoją pracę musi przejść po każdej ulicy w swoim rejonie co najmniej raz. Oczywiście chciałby, aby droga, którą przebędzie, była możliwie najkrótsza.
Dlaczego chińskiego ?
Problem ten został sformułowany po raz pierwszy w języku teorii grafów przez chinskiego matematyka Mei Ku Kwana w 1962 roku.
Sformułowanie problemu.
Rozważmy graf, którego krawędzie odpowiadają ulicom w rejonie, obsługiowanym przez listonosza. Wierzchołki to po prostu skrzyżowania ulic. Krawędziom nadajemy wagi, które oznaczają odległości między dwoma skrzyżowaniami. Znalezienie możliwie najkrótszej drogi, którą musi przejść listonosz sprowadza sie do znalezienia w tym grafie drogio minimalnej sumie wag krawędzi, która przechodzi przez każdą krawędź co najmniej raz.
Jeśli graf posiada cykl Eulera.
Jeśli dany graf posiada cykl Eulera, to istnieje taka droga, która zaczyna i konczy sie w tym samym punkcie i wymaga przejścia po każdej ulicy dokładnie raz. Zauważmy, że ponieważ każdy cykl Eulera przechodzi raz przez każdą krawędź to suma wag krawędzi (długość drogi, którą musi przejść listonosz) jest zawsze taka sama (nie zależy od wierzchołka, w którym cykl ten zaczyna się i konczy). Rozwiązaniem jest więc dowolny cykl Eulera w tym grafie.
Jeśli graf nie posiada cyklu Eulera.
W takim przypadku listonosz będzie zmuszony przejść niektórymi ulicami wielokrotnie. Rozwiązanie jest więc cyklem, w którym suma długości krawędzi wybranych więcej niż raz jest możliwie najmniejsza.
Przykład
Na rysunku pokazany est układ ulic niedaleko Politechniki Warszawskiej. Załóżmy, że fragmenty tych pięciu ulic tworzą rejon listonosza.

Obok nazw ulic umieszczone są odległości w metrach. Prostokąt oznaczony literą $P$ oznacza miejsce, w którym umieściliśmy pocztę, na której pracuje 'nasz' listonosz. (Na marginesie: nazwy i układ ulic są prawdziwe, jednak podane odległości oraz umiejscowienie poczty nie odpowiadają rzeczywistości. Pocztę umieścilismy w miejscu, gdzie w rzeczywistości znajduje się Gmach Główny, w którym ma swoją siedzibę Wydział MiNI. I niestety nie ma w tym budynku poczty.) Oto jak wygląda graf odpowiadający danemu układowi ulic. Zauważmy, że graf ten nie ma cyklu Eulera ponieważ posiada dwa wierzchołki, z których wychodzi nieparzysta liczba krawędzi. Na rysunku zaznaczono również rozwiązanie czyli optymalną trasę listonosza.

Zwróćmy uwagę, że listonosz musi przejść dwukrotnie tylko ulicę Noakowskiego, zaś pozostałe ulice dokładnie raz. Powyższa droga jest najkrótszą z możliwych ponieważ odcinek, po którym przechodzi dwukrotnie liczy tylko 500 metrów i nie istnieje trasa spełniająca zadane warunki o krótszym odcinku, który listonosz musi pokonać więcej niż raz.
Czym różni się problem mostów królewieckich od problemu chinskiego listonosza ? Rozwiązanie problemu chinskiego listonosza istnieje zawsze o ile graf jest spójny.
Natomiast problem mostów królewieckich, a mówiąc ogólniej problem znalezienia cyklu Eulera w grafie, nie zawsze ma rozwiązanie. Jeśli jednak graf posiada cykl Eulera, to rozwiązanie jednego z tych problemów jest również rozwiązaniem dla drugiego.
Algorytm Fleury'ego
Jest to algorytm znajdujący cykl Eulera w grafie. Jak już wiemy, jeśli graf posiada taki cykl, to jest on rozwiązaniem rozważanego problemu. Po wprowadzeniu pewnych modyfikacji może posłużyć również do rozwiązywania problemu chinskiego listonosza w przypadku grafów, które nie mają cyklu Eulera.
Opis Algorytmu Fleury'ego
Startujemy z dowolnego wierzchołka. Każda kolejna krawędź, po której przechodzimy, wybierana jest spośród krawędzi wychodzących z wierzchołka, w którym aktualnie się znajdujemy. Wybieramy oczywiście krawędź, po której jeszcze nie przeszliśmy. O ile jest to możliwe, usunięcie wybranej krawędzi nie powinno rozciąć grafu na dwa 'kawałki'. Jeśli uda nam się, postępując w ten sposób, dojść do wierzchołka, z którego wyruszyliśmy i przejść przez wszystkie krawędzie, to otrzymana droga jest cyklem Eulera.

[ Początek strony ] [ MiNIWykłady ]
Wszystkie prawa zastrzeżone © 2000 Wydział Matematyki i Nauk Informacyjnych Politechniki Warszawskiej