BEBRO konkurso užduotys 2017

 

Honomakato lankstusis tinklas

Taškai: 6

Honomakato salynas sudarytas iš penkių salų – Ho, No, Ma, Ka ir To. Ho sala yra prijungta prie interneto storu kabeliu. Ploni kabeliai jungia Ho ir No, Ho ir Ka, Ka ir Ma, taip pat Ka ir To salas. Šiais kabeliais visos salos yra sujungtos su Ho sala.

Honomakato gyventojai nori, kad interneto tinklas būtų patikimas, t. y. jei vienas iš plonų kabelių būtų sugadintas, salos vis tiek būtų prijungtos prie interneto.

Tarp kurių dviejų salų porų turi būti nutiesti kabeliai, kad tinklas būtų patikimas?

  1. Tarp Ho ir To, taip pat tarp No ir Ma.
  2. Tarp Ho ir To, taip pat tarp Ma ir To.
  3. Tarp Ka ir No, taip pat tarp No ir Ma.
  4. Padaryti tinklą patikimą neužtektų dviejų kabelių.
Paaiškinimas

Honomakato salyno interneto struktūra vaizduoja tik mažą dalį viso interneto tinklo. Visi prie interneto prijungti įrenginiai gali būti laikomai mazgais (salomis).

1960 metais vienas iš tikslų buvo sukurti jungųjį tinklą. Svarbiausia, kad, praradus ryšį tarp dviejų tinklo mazgų, nežlugtų visas interneto tinklas. Kitiems tinklams, pavyzdžiui, eismo, tiekimo ir kt., taip pat svarbu, kad mazgas turėtų daugiau kaip vieną jungtį.

Informatikoje šie tinklų vaizdavimo būdai vadinami grafais. Grafas – tai taškai (viršūnės), sujungti linijomis (briaunomis). Realiame gyvenime tinklai gali būti vaizduojami grafais ieškant optimalaus sprendimo. Grafas, kurio kiekvieną viršūnių porą jungia tinklas, vadinamas jungiuoju. Grafo briauna, kurią atėmus keičiasi grafo jungumo komponenčių skaičius, vadinama tiltu. Kitaip tariant, jei norėtume iš kurios nors viršūnės pasiekti kitą viršūnę ir tuo tikslu būtinai turėtume eiti tam tikra briauna, ši briauna ir būtų tiltas. Jungiuosiuose tinkluose tiltų neturėtų būti. Informatikoje yra algoritmų tiltams aptikti. Robertas Tarjanas, be kitų algoritmų, yra sukūręs ir tiltų aptikimo algoritmą.

Raktiniai žodžiai: dinaminė duomenų struktūra, grafas, tiltas.

Atsakymas

Teisingas atsakymas yra A – tarp Ho ir To, taip pat tarp No ir Ma.

Jei tarp Ho ir To būtų kabelis, tai

  • To liktų prijungta prie interneto, jei Ho ir Ka arba Ka ir To kabelis būtų sugadintas,
  • Ka liktų prijungta prie To, net jei Ho ir Ka kabelis būtų sugadintas.

Jei tarp No ir Ma būtų kabelis, tai

  • Ma liktų prijungta prie interneto per No, jei Ho ir Ka arba Ka ir Ma kabelis būtų sugadintas;
  • No liktų prijungta prie interneto per Ka ir Ma, jei Ho ir No kabelis būtų sugadintas;
  • Ka liktų prijungta prie interneto per No ir Ma, jei Ho ir Ka kabelis būtų sugadintas.

Ma ir To kabelis neapsaugo No salos nuo atjungimo nuo tinklo, jei Ho ir No kabelis būtų sugadintas.
Ka ir No kabelis neapsaugo To salos nuo atjungimo nuo tinklo, jei Ho ir Ka arba Ka ir To kabelis būtų sugadintas.

Interaktyvi užduotis

 

 
Informacija atnaujinta 2017-11-13 16:52:39