Úloha kropicího vozu
Úloha číslo: 3629
Nalezněte algoritmus pro nalezení nejkratšího uzavřeného sledu, jež obsahuje všechny hrany daného grafu (sled je posloupnost navazujících hran, kde se hrany i vrcholy mohou opakovat). Pro jednoduchost předpokládejte, že graf má nejvýše 6 vrcholů lichého stupně.
Řešení
Sestavíme pomocný úplný graf na vrcholech lichého stupně jehož hrany budou ohodnoceny vzáleností těchto vrcholů v původním grafu.
Párování minimální ceny odpovídá úsekům, které je potřeba projet dvakrát. Zdvojíme-li hrany podél těchto cest, dostaneme eulerovský graf, jehož uzavřený eulerovský tah nalezneme pomocí standardního algoritmu pro tuto úlohu.
Párování minimální ceny lze nalézt hrubou silou (je-li pomocný graf malý jako v zadání), případně využít některý ze sofistikovaných algoritmů pro tento problém.