ŽDU

Šikovní stavbári

Isté mesto - nazvime si ho ako chcete, sa rozkladá na 5 ostrovoch, ktoré nie sú nijako pospájané. Dá sa medzi nimi len plávať. A to už obyvateľov pomaly prestáva baviť. Vymysleli si, že ostrovy pospájajú mostami, ale nijako sa nevedia dohodnúť koľkými a ako, aby to nebolo príliš drahé, ale aby mostov bolo dosť. Preto požiadali o pomoc nás - matematikov. Čo myslíte, koľko by museli postaviť mostov, aby každé dva ostrovy boli spojené vlastným mostom? (Riešime úlohu svojimi spôsobmi.)
Nakreslime si obrázok (obr. 1):

staviame mosty Obr. 1 Staviame mosty

Z obrázka vidíme, že je potrebné postaviť 10 mostov.

Zistili sme spoločne, že medzi ostrovmi musia postaviť najmenej 4 mosty. Túto minimálnu cestu budeme nazývať MINIMÁLNA MOSTOVÁ SIEŤ - MMS. Keď sa pozriete na svoje obrázky takýchto sietí, zistíte, že ani jedna takáto sieť neobsahuje "slučku" (obr. 2).

MMS Obr. 2 Minimálna mostová sieť

Koľko mostov by mala MMS, ak by sme museli pospájať 6, 7, ... ostrovov? (5, 6, ...). Nakreslite čo najviac MMS pre našich 5 ostrovov. Viete koľko je všetkých možností? (125) Všetkých možností je síce veľa, ale my - šikovní matematici - si vieme ich spočítanie zjednodušiť. Už na pohľad sú niektoré spôsoby podobné, či skoro rovnaké. Predstavte si, že každý kto príde na ostrov musí za vstup zaplatiť, a čím viac mostov vedie na ostrov, tým je ostrov bohatší a významnejší. Na obrázku 3 sú niektoré z možností pospájania ostrovov pomocou MMS. Označme si pri každom ostrove počet mostov, ktorými sa na ostrov dá prísť a zapíšme si to.

MMS ostrovov Obr. 3 Spájanie ostrovov pomocou MMS

Siete na obrázku 4 by sme jednoducho zapísali (1, 2, 2, 2, 1), (1, 1, 3, 2, 1), ( 1, 4, 1, 1, 1), takže všetky tieto siete sú odlišné. Pokúste sa takto potriediť všetky MMS, ktoré si len viete nakresliť. Koľko rôznych typov MMS takto môžeme nájsť? (Správna odpoveď je 3 - už spomenuté.)

MMS ostrovov Obr. 4 Minimálne mostové siete

  • Všimli ste si, aký je súčet číslic v zátvorkách? Prečo je to tak?
  • Koľko typov MMS by sme našli pre mesto, ktorý má 6 ostrovov?
    Keby sme si ich všetky nakreslili, zistili by sme, že ich je 6 - obr. 5
  • Pokúste sa každý nakresliť rôzne typy mostov medzi 6 ostrovmi a priraďte ich k jednotlivým typom MMS
  • MMS ostrovov Obr. 5 Spájanie ostrovov pomocou MMS

    Vráťme sa ale k nášmu mestu. My matematici sme vymysleli, koľko a akých mostov by stavbári mali postaviť. Ale, čo ak príde mestský pokladník a povie, že takto nie, lebo to je drahé. A zas budeme mať prácu len my, matematici. Pozrime sa na obrázok 6. Je na ňom plán nášho mesta. Pri každom moste je však číslo, ktoré nám hovorí, aké sú náklady (v miliónoch korún) na jeho výstavbu. Poraďme stavbárom, ktorú MMS majú vybudovať, aby to mesto stálo, čo najmenej korún. Keď nájdete najlacnejší spôsob, pokúste sa vysvetliť, ako ste postupovali. Vedeli by ste oddôvodniť, že vaša cesta je naozaj najlacnejšia?

    budovanie optimálnej MMS ostrovov Obr. 6 Budovanie optimálnej minimálnej mostovej siete

    Pokúsme sa pouvažovať nad tým spoločne: Vieme, že MMS musí mať 4 mosty. Najlacnejšie 4 mosty v našom meste stoja 2, 2, 3 a 3 milióny, spolu teda 10 miliónov. A MMS, ktorú sme našli stojí presne toľko, je teda optimálna. Predstavte si teraz, že vás pozvali do susedného mesta a požiadali vás, aby ste tento istý problém vyriešili u nich. Plánik mesta je na obrázku 7. Cesty, ktoré nie sú vyznačené sa nedajú postaviť z technických príčin. Máte vybrať mosty tak, aby umožňovali spojenie medzi všetkými mestami a náklady boli minimálne. Našli ste aj vy takéto správne riešenie, ktoré je na vedľajšom obrázku? Nie? Tak ho opäť skúsime nájsť spolu.

    hľadanie MMS ostrovov Obr. 7 Hľadanie minimálnej mostovej siete

    V prvom rade by sme mali začať vyberať od najlacnejších mostov. Aby mohol systém mostov byť minimálny, mali by sme vybrať pre n ostrovov n-1 mostov. Nie vždy, keď vyberieme n-1 mostov však vybraný cyklus spĺňa podmienku, ktorú sme spomenuli na začiatku, teda to, že nesmie obsahovať cykly. Vezmime si napríklad mesto na obrázku 8. Najlacnejšia MMS obsahuje 5 mostov s cenami 2, 3, 5, 7, 10 a nie mosty s cenami 2, 3, 4, 5, 6.

    najlacnejšia MMS ostrovov Obr. 8 Budovanie najlacnejšej minimálnej mostovej siete

    Pokúste sa sformulovať algoritmus - teda predpis, či postup na hľadanie najlacnejšej MMS ako jednoduchý návod pre staviteľov ciest a mostov. Na záver si tento postup zapíšeme do diagramu a vyskúšame si jeho funkčnosť na iných mestách.

    algoritmus hľadania MMS ostrovov Obr. 9 Algoritmus hľadania minimálnej mostovej siete

    Teória, ktorá sa zaoberá hľadaním takýchto minimálnych mostových, či cestných sietí sa nazýva TEÓRIA GRAFOV. Každý plánik, ktorý sme nakreslili sa v tejto teórii nazýva GRAF, jednotlivé ostrovy nazývame UZLY, mosty nazveme HRANY grafu. S teóriou grafov pracujú často v doprave, v logistike a napríklad aj pri budovaní akýchkoľvek vedení, či potrubí.




    Naspäť