2014 2015 2016 2017 2018

Upių užtvankos

Taškai: 12

Bebrai gyvena tvenkiniuose ir keliauja vieni pas kitus tvenkinius jungiančiomis upėmis. Upėse gali būti pastatyta užtvankų. Norėdamas įveikti užtvanką, bebras turi išlipti iš vandens.
Kiekvienas bebras norėtų aplankyti visus bebrus neišlipdamas iš vandens.
Paveikslėliuose pavaizduoti keturi kaimai. Galimas upių užtvankas žymi raudoni taškai. Nepatikima upe vadinsime upę, kurioje pastatyta užtvanka neleistų bebrams pasiekti visų to paties kaimo bebrų neišlipus iš vandens.
Tik vienas iš kaimų NETURI nepatikimos upės. Kuris? 

A.  C.  
B.  D.     
Paaiškinimas

Upės ir tvenkiniai sudaro tinklo sistemą. Šioje sistemoje tvenkiniai yra objektai, kurie sujungti upėmis. Tai panašu į internetą, kuriame kompiuteris, mobilusis telefonas, televizorius ir t. t. yra sujungti kabeliu, telefono linija, belaidžiu ryšiu ir pan.
Pirmasis tinklas ėmė veikti 1969 m. ir jungė keturis universitetus Jungtinėse Amerikos Valstijose. Norėta užtikrinti, kad tinklas veiks, net jei nutrūktų viena kuri jo jungtis. Tai reiškia, kad interneto kūrėjai praeito amžiaus 7-ame dešimtmetyje galvojo kaip išvengti silpno, nepatikimo ryšio pavojų.
Tinklo sistemos problemai spręsti (kaip tvenkinių ir upių uždavinyje) informatikoje naudojama grafų teorija. Grafas yra sudarytas iš viršūnių (tvenkinių) ir briaunų (upių). Informatikoje grafais modeliuojamos įvairios tinklo sistemos, pavyzdžiui, bendravimo tinklo, eismo tinklo. Dauguma algoritmų buvo sukurta uždaviniams, susijusiems su grafais, spręsti. Vienas iš pavyzdžių – surasti vadinamuosius „tiltus“ grafe (mūsų uždavinyje – nepatikimas upes).

Reikšminiai žodžiai: grafas, tinklas, silpnoji jungtis, silpnoji briauna.

Atsakymas

Teisingas atsakymas – A. Bet kurioje upėje pastačius užtvanką, nesvarbu kurioje, atsiras kelias tarp bet kurių dviejų tvenkinių.
Kiti tvenkiniai turi šias nepatikimas jungtis (žr. aiškinamąjį paveikslą): vidurinė upė antrame kaime, kairioji upė – trečiame, dvi vidurinės upės – ketvirtame. Pirmas kaimas nepatikimų jungčių neturi.
Jei iš tvenkinio ištekanti upė yra vienintelė jungtis su kitu tvenkiniu, tai – nepatikima jungtis. Toliau reikia patikrinti upes, kurios neatrodo kaip nepatikimos jungtys, bet tokios yra, nes nėra galimybės pasirinkti kelio kitomis upėmis.