BEBRO konkurso užduotys 2017

 

Gimtadienis

Taškai: 12

Molėtuose gyvenantis Bebras pakvietė visus savo draugus iš aplinkinių miestelių ir kaimų į gimtadienio šventę. Į šventę atvyko tik ne toliau kaip už 20 km gyvenantys draugai.

Žemėlapyje pavaizduoti atstumai tarp visų vietovių.

Spustelėkite visų miestelių ir kaimų, iš kurių atvyko draugai į Bebro gimtadienį, pavadinimus.

Paaiškinimas

Dažnai tikslinga grafo briaunai priskirti kurį nors dydį. Pavyzdžiui, jei grafu modeliuojame vietovės žemėlapį (viršūnėmis – miestus, o briaunomis – kelius), tai briaunoms galima priskirti tų kelių ilgius. Grafas, kurio visoms briaunoms yra priskirti dydžiai (svoriai), vadinamas svoriniu. Dažniausiai nagrinėjami svoriniai grafai, kurių briaunų svoriai yra skaičiai. Dijkstros algoritmu iš nurodytos viršūnės (Molėtų) randami trumpiausi keliai iki visų svorinio grafo viršūnių (miestelių ar kaimų). Plačiau apie algoritmą galima skaityti:

http://inf.knyga.nmakademija.lt/10_dijkstra.html

Raktiniai žodžiai: Dijkstros algoritmas.

Atsakymas

Teisingas atsakymas yra

Trumpiausias atstumas nuo Molėtų iki kiekvieno miestelio ar kaimo skaičiuojamas sudedant visus atstumus, jungiančius Molėtus su atitinkamu miesteliu ar kaimu, ir išrenkant mažiausią sumą. Tinka tik tie miesteliai ar kaimai, iki kurių atstumas yra mažesnis kaip 20 km. Pritaikius trumpiausio kelio Dijkstros algoritmą, gaunama:

Mindūnai = 2
Lėliai = 8
Šeštokiškės = 12
Kamužė = 13 = 2 + 11 (Saldutiškis = 13 + 8 = 21 – per toli)
Luokena = 16 = 8 + 8 (Zibalai = 16 + 8 = 24 – per toli)
Rudesa = 17 (Vilkaslastis = 17 + 8 = 25 – per toli )
Rudiliai = 17 = 12 + 5
Žiūrai = 18 = 8 + 10 (Bareikiai = 18 + 3 = 21 – per toli)
Bareikiai = 19 = 17 + 2

Interaktyvi užduotis

 

 
Informacija atnaujinta 2017-11-13 16:52:39
Informuojame, kad nuo 2019 m. rugsėjo 2 d. Ugdymo plėtotės centro veiklas vykdo Nacionalinė švietimo agentūra. Ši interneto svetainė toliau nebus atnaujinama, tačiau visa informacija išliks aktyvi ir prieinama tol, kol bus perkelta į Nacionalinės švietimo agentūros interneto svetainę www.nsa.smm.lt.