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

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].