Tiltai (2014)
Taškai: 9
Tarp salų ežere nutiesti tiltai. Kaip parodyta paveiksle, vieni tiltai yra viešieji (ištisinė linija), kiti yra mokami (brūkšninė linija).
Sandra nori iš savo namų nukeliauti į miškingąją salą. Ji ieško kelio, kuriame būtų mažiausiai tiltų. Tačiau Sandra turi nedaug pinigų ir gali užmokėti ne daugiau kaip už du mokamus tiltus.
Kiek mažiausiai tiltų reikės Sandrai pereiti, jei mokamų tiltų gali būti ne daugiau kaip du?
A. 4
B. 5
C. 6
D. 7
Šis paveikslas – tai grafo modelis. Prašoma surasti kelią iš vienos viršūnės (Sandros namų) į kitą (mišką). Apsiribojama tam tikru mokamų tiltų skaičiumi ir ieškoma pigiausio galimo kelio.
Yra daug būdų išspręsti tokius uždavinius; vienas įdomiausių ir iššūkius keliančių informatikos aspektų – galimybė susidurti su gerai žinomų problemų variantais.
Teisingas atsakymas – B: reikės pereiti 5 tiltus.
Iš Sandros namų nėra nei vieno kelio, kuris turėtų mažiau negu 4 tiltus. Visi keliai, kurie turi 4 tiltus, apima 3 mokamus tiltus. Yra keli keliai, kurie apima 5 tiltus, iš kurių 2 yra mokami.
