Problém čínského listonoše

Problém čínského listonoše je úloha z teorie grafů, která spadá do problematiky optimalizace cesty v grafu. Tuto úlohu formuloval čínský matematik M.-K. Kwan roku 1960.

Zadání

Listonoš musí zajít na poštu, vzít dopisy a obejít s nimi všechny ulice města a nakonec se vrátit do výchozího bodu - zpět na poštu. Musí přitom urazit minimální vzdálenost.

V grafu, který reprezentuje město, představují hrany grafu ulice a uzly odpovídají křižovatkám. Hrany jsou ohodnoceny kladnými čísly, které odpovídají délce ulic.

Řešení

Pokud je v grafu možné provést eulerovský tah, je řešení triviální. Listonoš projde všemi hranami právě jednou. +more Součet ohodnocení hran udává délku cesty, kterou urazil.

V opačném případě je nutné do grafu přidat hrany (resp. je zdvojit), tak aby bylo možné v novém grafu Eulerův cyklus nalézt. +more Vybíráme hrany s nejnižším ohodnocením (kvůli optimalizaci).

Reálné aplikace

K aplikacím v reálném světě patří např. úklid, čištění, sypání silnic, kontroly či opravy dopravního značení.

Související články

Problém obchodního cestujícího

Externí odkazy

[url=https://web. archive. +moreorg/web/20071207205008/http://www. uclic. ucl. ac. uk/harold/cpp/]The Chinese Postman Problem[/url] * [url=http://mathworld. wolfram. com/ChinesePostmanProblem. html]The Chinese Postman Problem (2)[/url].

Kategorie:Úlohy s grafy