Salos ir tiltai

Taškai: 6

Bebrų bendruomenės gyvena salose ir nori tarp jų nutiesti tiltus. Inžinierius pateikė schemą, kurioje taškai žymi salas, o linijos – jas jungiančius tiltus.   


Tačiau bebrai pageidauja schemos, kurioje taškai vaizduotų tiltus, o linijos – salas. Kaip atrodytų tokia schema?

A C
B D

 

Paaiškinimas

Realių situacijų modeliavimas grafais tapo itin reikšmingas atsiradus kompiuteriams ir daugeliui grafų skaičiavimo algoritmų. Algoritmų, kurie apdorotų grafus, kūrimas yra viena iš daugiausia dėmesio sulaukiančių informatikos sričių. Informatikoje grafais vaizduojami komunikacijų tinklai, duomenų organizavimas, skaičiavimo procesai įrenginiuose, informacijos srautai ir pan. Pavyzdžiui, tinklalapio ryšių struktūrą pavaizdavus grafu, galima optimizuoti paiešką ir atlikti kitokius veiksmus. Kuriant ar taikant grafų algoritmus, dažnai reikia transformuoti turimą grafą – keisti viršūnes ir briaunas vietomis. Tam sukurta formalių metodų. Grafo transformavimo procesas reikalauja gana nemažų abstrahavimo pastangų.

Reikšminiai žodžiai: abstrachavimas, grafas, modeliavimas, transformavimas.

Atsakymas

Teisingas atsakymas yra D.
C atvejį iš karto atmetame, nes tiltų yra 9, o šioje schemoje 10 viršūnių (salų).
Toliau pastebime, kad yra vienas tiltas, iš kurio tiesiai galime pasiekti 6 tiltus – taip tėra tik B ir D atvejais. Toliau galime ieškoti tiltų, iš kurių tiesiogiai galima pasiekti 5 tiltus. Tačiau paprasčiau pastebėti, kad yra 2 tiltai, iš kurių tiesiogiai galima pasiekti tik 2 kitus tiltus – tokio atvejo B nėra. Vadinasi, belieka teisingas D.

 

 
Informacija atnaujinta 2016-10-18 10:55:36
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.