Problem chińskiego listonosza

Niniejszy artykuł jest częścią cyklu teoria grafów.

Najważniejsze pojęcia graf drzewo podgraf cykl klika stopień wierzchołka stopień grafu dopełnienie grafu obwód grafu pokrycie wierzchołkowe liczba chromatyczna indeks chromatyczny izomorfizm grafów homeomorfizm grafów więcej... Wybrane klasy grafów graf pełny graf spójny drzewo graf dwudzielny graf regularny graf eulerowski graf hamiltonowski graf planarny więcej... Algorytmy grafowe A* Bellmana-Forda Dijkstry Fleury'ego Floyda-Warshalla Johnsona Kruskala Prima przeszukiwanie grafu – wszerz – w głąb najbliższego sąsiada Zagadnienia przedstawiane jako problemy grafowe problem komiwojażera problem chińskiego listonosza problem marszrutyzacji problem kojarzenia małżeństw Inne zagadnienia kod Graya diagram Hassego kod Prüfera

pokaż • dyskusja • edytuj

Problem chińskiego listonosza (ang. Chinese postman problem lub route inspection problem) – w teorii grafów 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].

Przypisy

[edytuj] Linki zewnętrzne

Strona PW