Problém čínského listonoše
Z Wikipedie, otevřené encyklopedie
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 1962.
Obsah |
[editovat] 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.
[editovat] Ř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. 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. Vybíráme hrany s nejnižším ohodnocením (kvůli optimalizaci).
[editovat] Reálné aplikace
K aplikacím v reálném světě patří např. úklid, čištění, sypaní silnic, kontroly či opravy dopravního značení.
