Problem chińskiego listonosza
Niniejszy artykuł jest częścią cyklu teoria grafów. |
Najważniejsze pojęcia Wybrane klasy grafów Algorytmy grafowe Zagadnienia przedstawiane jako problemy grafowe Inne zagadnienia |
Problem chińskiego listonosza (ang. Chinese postman problem, route inspection problem) – zadanie znalezienia ścieżki zamkniętej (wracającej do wierzchołka początkowego), zawierającej każdą krawędź grafu co najmniej raz i mającej minimalny koszt (sumę wag krawędzi).
Problem został pierwszy raz sformułowany w 1962 roku w języku chińskim.
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[1].
Algorytm
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[2].
Przypisy
- ↑ 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.).