BYSTRÁ HLAVA

obtížnost:

Problém profesora Borůvky

Kdysi dávno, v začátcích elektrifikace, se na profesora Borůvku obrátili pracovníci elektrárny se svým problémem.
"Postavili jsme malou elektrárnu, která může zásobovat elektrickým proudem pět okolních obcí. Víme, kde by bylo možné postavit elektrické vedení pro každou dvojici těchto obcí, a známe také, jak dlouhé by muselo být. Nemůže vždy vést přímým směrem, protože se musí vyhýbat rybníkům a větším kopcům. Délky vedení v kilometrech jsou zde, na obrázku," ukazují a předkládají panu profesorovi malý náčrtek.

"A v čem je problém?" – táže se profesor Borůvka.
"Nevíme," odpovídají návštěvníci, "které z těchto možných spojení máme vybrat pro postavení elektrického vedení."
"To snad není tak obtížné určit," namítá pan profesor.
"Problém je v tom," nesouhlasí návštěvníci, "že bychom chtěli přivést elektřinu do všech těchto obcí, ale současně bychom chtěli, aby elektrické vedení, které je potřeba k tomu vybudovat, bylo co nejkratší, a tím i nejlevnější na stavbu, údržbu i ztráty elektrického proudu."
Profesor chvíli přemýšlí a pak – věren svému přesnému způsobu myšlení i vyjadřování – odpovídá: "Jde tedy o to, vybrat ze všech možných spojení taková, aby se elektrický proud dostal do všech míst a aby přitom byl součet délek vybraných úseků minimální. Jestli se nemýlím?"
"Přesně tak, pane profesore," dostává odpověď a současně i otázku: "Vyřešíte tento problém?"

Jiné varianty

• Zadání je stejné, jen jiná mapka
• Představte si, že pracovníci Elektrárny omylem oslovili souseda profesora Borůvky – pana Mefista – Jeho záměr je ale naprosto opačný – naplánovat elektrifikaci sice co nejjednodušeji, ale s co nejdelšími vzdálenostmi.