BEBRO konkurso užduotys 2017

 

Pramogų bebravietė

Taškai: 12

Bebro šeima įrengė pramogų buveinę – 4 kambarius, kuriuos jungia 5 tuneliai ir iš kurių yra 7 durys į kiemą.

Bebro vaikai pastebėjo, kad įmanoma perbėgti visus tunelius ir pro visas duris, visur lankantis tik po vieną kartą.

Iš kurio kambario reikėtų pradėti bėgti?

A) Iš A B) Iš B C) Iš C D) Iš D
Paaiškinimas

Tai grafo teorijos uždavinys. Vadinamasis Oilerio kelias kaip tik ir eina per visas grafo viršūnes ir tik po vieną kartą. Būtina Oilerio kelio sąlyga: viena arba dvi viršūnės turi turėti nelyginį briaunų skaičių. Kodėl keliama tokia sąlyga, galime suprasti pamąstę: keliaudami į kiekvieną kambarį turime įeiti (tuneliu ar pro duris) ir taip pat iš jo išeiti (tuneliu arba pro duris), išskyrus maršruto pradžią ir pabaigą.

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

https://lt.wikipedia.org/wiki/Oilerio_mar%C5%A1rutas

 

Raktiniai žodžiai: grafas, viršūnė, Oilerio kelias.

Atsakymas

Teisingas atsakymas yra C.

Pramogų bebravietę galima pavaizduoti grafu. Kiekvienas kambarys tampa viršūne, kiemas žymimas atskira viršūne. Dvi viršūnės sujungiamos, jei tarp kambarių yra tuneliai arba iš kambario yra durys į kiemą.

Norimas maršrutas įmanomas, jei yra dvi viršūnės, turinčios nelyginį briaunų skaičių. Tada viena iš šių viršūnių yra maršruto pradžia, o kita – pabaiga.

Šiuo atveju tokia viršūnė, turinti nelyginį kelių skaičių, yra C (3 tuneliai + 2 durys).

 

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