BEBRO konkurso užduotys 2017

 

Trumpiausias kelias

Taškai: 12

Paveiksle pavaizduotas vienakryptis kelių tinklas. Kiekvienos viršūnės skaičius nurodo trumpiausią kelią nuo S iki atitinkamos viršūnės.

Kuris iš šių teiginių apie dvi storesniu kraštu pažymėtas viršūnes yra teisingas?

  1. Trumpiausias kelias tarp šių viršūnių yra lygiai 8.
  2. Trumpiausias kelias tarp šių viršūnių yra ne daugiau kaip 8.
  3. Trumpiausias kelias tarp šių viršūnių yra ne mažiau kaip 8.
  4. Nė vienas atsakymas nėra teisingas.
Paaiškinimas

Užduotyje pristatomi tinklai (grafai) ir žymioji trumpiausiojo kelio paieškos problema. Plačiau apie šią problemą galima paskaityti čia:

 https://en.wikipedia.org/wiki/Shortest_path_problem

Trumpiausiojo kelio paieškos problemą galima spręsti Dijkstros algoritmu. Tačiau šiame uždavinyje prašoma surasti trumpiausią kelią tarp dviejų viršūnių tinkle, o ne tarp pradžios ir pabaigos taškų.

Atsakymas

Teisingas atsakymas yra C.

Jei trumpiausias kelias tarp šių išskirtų viršūnių būtų mažesnis nei 8, tai trumpiausias kelias tarp S ir 11 viršūnės turėtų būti mažesnis už 11. Kad ir kaip keistai atrodytų iš pirmo žvilgsnio, tačiau trumpiausias kelias tarp šių išskirtų viršūnių gali būti ir didesnis nei 8! Mes juk nežinome atstumų tarp atskirų viršūnių: gali būti taip, kad trumpiausias kelias nuo S iki 11 viršūnės eina per išorines grafo viršūnes ir šių kelių netekome, todėl buvęs trumpiausias kelias gali ir pailgėti.

 

 
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.