BEBRO konkurso užduotys 2017

 

Sąnaudų mažinimas

Taškai: 9

Bebrų krašto geležinkelio bendrovė valdo aštuonias stotis ir penkias linijas. Jų išdėstymas ir sąsajos parodytos diagramoje. Kiekviena linija nuspalvinta skirtinga spalva. Atkreipkite dėmesį, kad iš bet kurios stoties galima nukeliauti į bet kurią kitą stotį, daugiausia vieną kartą persėdus iš vienos linijos į kitą. Pavyzdžiui, norint patekti iš B į H, galima vykti purpurine linija nuo B iki F, paskui persėsti į oranžinę liniją ir vykti į H.

Geležinkelio bendrovė nori sumažinti išlaidas, todėl planuoja uždaryti vieną ar kelias geležinkelio linijas. Tai padaryti ji turi taip, kad nenukentėtų bebrai keleiviai, t. y. kad visos stotys būtų prijungtos prie geležinkelių tinklo ir kad iš bet kurios stoties į bet kurią kitą stotį būtų galima nuvykti ne daugiau kaip vienąkart persėdus.

Kiek daugiausia geležinkelio linijų gali uždaryti bendrovė?

Atsakymas turi būti skaičius:____

Paaiškinimas

Šioje užduotyje naudojami grafai, kurie vaizdžiai pateikia geležinkelių tinklą. Informatikoje grafų dažnai prireikia sudėtingoms problemoms spręsti. Kuo geriau problema pavaizduojama, tuo lengviau mokiniai gali išspręsti sudėtingas problemas.

Raktiniai žodžiai:  grafas.

Atsakymas

Pašalinus raudoną (GEDH) ir šviesiai mėlyną liniją (DFC), visos sąlygos vis dar tenkinamos. Iš tiesų likusios linijos (BAFC, GEAD ir EFH) pasiekia visas aštuonias stotis, be to, turi papildomą savybę, kad kiekviena jų pora yra susijusi bent viena bendra stotimi. Todėl iš bet kurios stoties galima nuvykti į bet kurią kitą stotį ne daugiau kaip vieną kartą persėdant.

Ar būtų galima uždaryti 3 linijas vietoj 2? Kitaip tariant, ar visos sąlygos gali būti tenkinamos naudojant tik dvi linijas?

Atsakymas yra neigiamas. Atkreipkite dėmesį, kad purpurinė linija (BAFC) yra vienintelė, kuria pasiekiama B stotis, todėl ši linija turi likti. Tada kita linija turi pasiekti keturias likusias stotis, todėl vienintelė galimybė – raudona (GEDH) linija. Deja, šios dvi linijos neturi bendros stoties, todėl, pavyzdžiui, neįmanoma nukeliauti traukiniu iš B į H, jau nekalbant apie ne daugiau kaip vieną persėdimą. Taigi dviejų linijų nepakanka.

Interaktyvi užduotis

 

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