1. Postav cesty!

Ak máte akékoľvek otázky ohľadom tejto úlohy napíšte Michalovi ‘Žabovi’ Anderlemu na [email protected]

Viete ako sa cestuje v Absurdistane? Tak ja vám to vysvetlím.

V Absurdistane je \(n\) miest, ktoré sú navzájom pospájané niekoľkými cestami. Každá cesta vedie medzi niektorými dvoma mestami a dá sa po nej pohybovať v oboch smeroch. Naviac sa žiadne dve cesty nekrižujú. Ak sa teda po niektorej z nich vyberiete, zísť z nej môžete iba v jednom z miest, ktoré spája. No, a našťastie, cestovať sa dá medzi ľubovoľnými dvoma mestami. Občas možno treba prejsť viacerými cestami, určite sa však viete dostať odvšadiaľ všade.

Problém je však v tom, že všetky cesty sú zastarané, neudržiavané a plné výmoľov. Vláda Absurdistanu sa preto rozhodla, že s tým treba niečo spraviť a niektoré cesty zrenovovať. Samozrejme, renovácia cesty niečo stojí a preto chce zrenovovať čo najmenej ciest. Zároveň však chce pôsobiť dojmom, že renovácia bola naozaj veľká. Chcela by preto zrenovovať také cesty, aby sa medzi každými dvoma mestami dalo cestovať iba po zrenovovaných cestách.

Na obrázku vľavo hore je príklad s desiatimi mestami, medzi ktorými vedie trinásť ciest. Napravo od neho sú červenou zvýraznené cesty, ktoré by mohla vláda Absurdistanu zrenovovať tak, aby zrenovovala čo najmenej ciest a zároveň sa dalo cestovať medzi každými dvoma cestami iba po zrenovovaných cestách. Táto možnosť samozrejme nie je jediná správna. Na nižších dvoch obrázkoch sú príklady rekonštrukcie, ktoré nespĺňajú niektorú požiadavku. Možnosť naľavo renovuje priveľa ciest (napríklad cestu medzi C a F nemusíme rekonštruovať), v možnosti napravo sa zase nevieme dostať po zrenovovaných cestách z mesta F do mesta A.

Úloha

1. (1 bod) Koľko najmenej ciest musí vláda Absurdistanu zrenovovať aby sa medzi každými dvoma mestami dalo cestovať iba po zrenovovaných cestách? Nezabudnite, že v Absurdistane je \(n\) miest, takže hľadaná odpoveď asi bude závisieť od tejto hodnoty.

2. (2 body) Popíšte postup (algoritmus), akým môže vláda Absurdistanu vybrať, ktoré cesty má zrekonštruovať.

   Popísať postup (algoritmus) je napísať nejakú postupnosť krokov a pravidiel, ktoré jednoznačne určia, ktoré cesty má vláda Absurdistanu vybrať, pričom tento postup funguje bez ohľadu na to, ako vyzerá plán ciest Absurdistanu.

   Ak si chcete vyskúšať, či je váš postup dobrý a zrozumiteľný, poproste o pomoc napríklad jedného z rodičov. Nakreslite mu plán Absurdistanu (napríklad ten z obrázku vyššie) a povedzte mu, aby riadiac sa vašim postupom, vybral cesty, ktoré sa majú zrenovovať.

3. (5 bodov) Vláda Absurdistanu však zistila, že niektoré cesty sú náročnejšie na renováciu. Presnejšie, o každej ceste vie povedať, či jej renovácia bude stáť 1 alebo 2 milióny dolárov. Stále chce zrekonštruovať cesty tak, aby sa medzi každými dvoma mestami dalo cestovať iba po zrekonštruovaných cestách, naviac však chce zaplatiť čo najmenej peňazí.

   Popíšte postup, ktorým môže vláda Absurdistanu vybrať cesty, ktoré má zrekonštruovať. Naviac zdôvodnite, prečo je váš postup správny a nájde najlacnejšie riešenie za každých okolností.

   Pri zdôvodňovaní sa skúste zamyslieť nad nasledovnými otázkami. Je treba vybrať viac ciest ako v riešení a)? Zmení sa úloha ak by sme namiesto hrán s hodnotami 1 a 2 mali hrany s hodnotami 0 a 1? Prečo sa mi neoplatí vybrať inú cestu?

4. (7 bodov) Hĺbková analýza terénu prišla s ešte horšími výsledkami. Zistilo sa, že renovácia rôznych ciest stojí rôzne množstvo peňazí. Za renováciu cesty môžeme občas zaplatiť 1 milión dolárov a občas až \(1\,000\,000\) miliónov dolárov. Našťastie, o každej ceste vieme, koľko bude stáť jej renovácia a takisto vieme, že všetky cesty majú tieto hodnoty rôzne.

   Popíšte postup, ktorý pomôže vláde Absurdistanu vybrať také cesty, ktorých renovácia bude stáť najmenšie množstvo peňazí a stále bude platiť, že medzi ľubovoľnými dvoma mestami sa dá cestovať pomocou zrenovovaných ciest. Zdôvodnite, prečo je váš postup správny a nájde najlacnejšie riešenie za každých okolností.

   Pri zdôvodňovaní sa skúste zamyslieť nad nasledovnými otázkami. Môže sa stať, že by najlacnejšie riešenie nebolo jednoznačné? Ak sa o nejakej ceste rozhodnem, že ju chcem zrenovovať, patrí táto cesta do najlacnejšieho riešenia? Čo by sa stalo, ak by najlacnejšie riešenie túto cestu nepoužívalo, ale my by sme ju doňho aj tak pridali?

Na obrázku je príklad k podúlohe c) a d) aj s možným optimálnym riešením. Čísla pri cestách určujú cenu renovovania danej cesty. Cena prvého riešenia je 11 miliónov dolárov, druhého 108 miliónov dolárov.