Problem chińskiego listonosza
Problem chińskiego listonosza (ang. Chinese postman problem, route inspection problem) – zadanie znalezienia najkrótszej ścieżki zamkniętej (wracającej do wierzchołka początkowego), która zawiera każdą krawędź grafu co najmniej raz.
Problem został pierwszy raz sformułowany przez chińskiego matematyka Kwan Mei-Ko w 1960 roku, choć jego artykuł został przetłumaczony na język angielski dopiero w 1962 roku[1].
Złożoność obliczeniowa problemu uzależniona jest od rodzaju grafu, na którym jest on rozpatrywany. W przypadku grafów w całości skierowanych albo nieskierowanych, problem chińskiego listonosza można rozwiązać w czasie wielomianowym. W przypadku grafów mieszanych (częściowo skierowanych, częściowo nieskierowanych) problem zalicza się do klasy NP-trudnych[2].
Algorytm[edytuj | edytuj kod]
Rozpatrywany graf jest grafem spójnym, nieskierowanym i ważonym.
W grafie eulerowskim rozwiązanie problemu chińskiego listonosza stanowi cykl Eulera, jako że jest to z definicji ścieżka zamknięta przechodząca przez wszystkie krawędzie w grafie.
W grafie półeulerowskim rozwiązaniem problemu jest ścieżka Eulera (z definicji łącząca jedyne dwa wierzchołki nieparzystego stopnia w grafie) wraz z minimalną ścieżką (czyli ścieżką o najmniejszej sumie wag krawędzi) łączącą wierzchołki nieparzystego stopnia. Do wyznaczania najkrótszej ścieżki pomiędzy dwoma wierzchołkami służy algorytm Dijkstry.
Jeżeli rozpatrywany graf G nie jest półeulerowski, to znaczy, że posiada przynajmniej 4 wierzchołki nieparzystego stopnia. Z wszystkich wierzchołków nieparzystego stopnia grafu G należy utworzyć graf H, w taki sposób aby graf H był grafem pełnym z wagami na krawędziach odpowiadającymi najmniejszej ścieżce pomiędzy wierzchołkami w grafie G. W grafie H należy znaleźć minimalne skojarzenie doskonałe i uzupełnić o nie graf G. Graf G jest teraz multigrafem eulerowskim, w którym rozwiązaniem problemu chińskiego listonosza jest cykl Eulera[3].
Przypisy[edytuj | edytuj kod]
- ↑ William R. Stewart, Chinese Postman Problem, Saul I. Gass, Michael C. Fu (red.), Boston, MA: Springer US, 2013, s. 161–164, DOI: 10.1007/978-1-4419-1153-7_110, ISBN 978-1-4419-1153-7 [dostęp 2024-01-30] (ang.).
- ↑ W.L. Pearn, J.B. Chou. Improved solutions for the Chinese postman problem on mixed networks. „Computers & Operations Research”. 26 (8), s. 819–827, lipiec 1999. Elsevier Science Ltd.. DOI: 10.1016/S0305-0548(98)00092-6. ISSN 0305-0548. (ang.).
- ↑ J.Edmonds, E.L.Johnson. Matching Euler tours and the Chinese postman problem. „Mathematical Programming”, s. 88–124, 1973. DOI: 10.1007/bf01580113. (ang.).
Linki zewnętrzne[edytuj | edytuj kod]
| Najważniejsze pojęcia | |
|---|---|
| Wybrane klasy grafów | |
| Algorytmy grafowe | |
| problemy grafowe | |
| Inne zagadnienia |
