Loading AI tools
zadanie znalezienia najkrótszej ścieżki przechodzącej przez wszystkie krawędzie w grafie Z Wikipedii, wolnej encyklopedii
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].
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].
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.