Na stronie używamy cookies. Korzystanie z witryny oznacza zgodę na ich wykorzystywanie. Szczegóły znajdziesz w Regulaminie.
ZAMKNIJ X

Problem chińskiego listonosza

Ostatnio komentowane
kappa xdddddddd
kk • 2016-12-07 19:00:41
Do d**y
Hn 88H • 2016-12-06 20:48:20
Polecam
Ola6a • 2016-12-05 19:19:19
super
sr • 2016-12-05 18:58:48
Dzięki za pomoc!
Uczeń • 2016-12-05 17:25:49
Autor:
Drukuj
Drukuj
Rozmiar
AAA

Problem chińskiego listonosza

Wyobraźmy sobie następującą sytuacją: pewien listonosz ma do rozniesienia przesyłki i listy zaadresowane do mieszkań porozrzucanych po całym mieście, zatem odwiedzić będzie musiał każdą ulicę.

W jaki sposób to zrobić tak, by łącznie przebyta droga była jak najkrótsza?

Reprezentacją tego problemu jest oczywiście graf prosty z wagami, tzn. sieć ulic reprezentowana jest przez krawędzie z wagami oznaczającymi ich długość, a zadanie jakie stoi przed listonoszem to takie wyznaczenie drogi w tym grafie, by suma wag krawędzi była jak najmniejsza.

Problem ten został sformułowany w 1962 roku przez chińskiego matematyka (stąd jego nazwa) Mei Ku Kwana. Okazuje się, że rozwiązanie tego zadanie zależy od typu grafu, jakim opisane są ulice.

Jeśli graf jest eulerowski (tzn. ma cykl Eulera, a więc taki, który zawiera każdą krawędź dokładnie raz) to rozwiązanie jest banalne - jest nim bowiem dowolny cykl Eulera tego grafu, a ponieważ zawiera on każdą krawędź dokładnie raz, zatem suma wag krawędzi jest taka sama niezależnie od tego gdzie cykl się zaczyna i kończy.

Problem komplikuje się wtedy, gdy graf ten nie jest eulerowski - wówczas listonosz niektórymi ulicami będzie musiał przejść kilkakrotnie, co oczywiście zwiększa całkowitą sumę wag o wagi ulic odwiedzanych więcej niż jeden raz.

Dobra wiadomość natomiast jest taka, że rozwiązanie tego problemu zawsze istnieje (o ile graf jest spójny, tzn. gdy listonosz podróżuje po jednym mieście).

Problem ten jest przykładem zastosowania kombinatoryki i teorii grafów do praktycznych zagadnień ze świata rzeczywistego.

Polecamy również:

Komentarze (0)
5 + 5 =