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 Kwan Mei-Ko roku 1960.
Zadání
[editovat | editovat zdroj]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í
[editovat | editovat zdroj]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, 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).
Reálné aplikace
[editovat | editovat zdroj]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í.[1]
Odkazy
[editovat | editovat zdroj]Reference
[editovat | editovat zdroj]- ↑ SCHRIJVER, Alexander. Combinatorial optimization : polyhedra and efficiency. Berlin: Springer, 2003. 1881 s. ISBN 3-540-44389-4. (anglicky)
Související články
[editovat | editovat zdroj]Externí odkazy
[editovat | editovat zdroj]
Obrázky, zvuky či videa k tématu Problém čínského listonoše na Wikimedia Commons - Harold Thimbleby, Problém čínského listonoše
- Problém čínského listonoše v encyklopedii MathWorld (anglicky)
