BEBRO konkurso užduotys 2017- Nykštukai
- Mažyliai
- Bičiuliai
- Draugai
- Mėgstamiausi gėrimai
- Kairėn–dešinėn
- Skliaustai
- Šunų susikeitimas
- Picerija „Bebrynė“
- Ką valgysime pietums?
- Įsibrovimas
- Honomakato lankstusis tinklas
- Kritulių pasiskirstymas
- Nindzė
- Žinių redagavimas
- Knygų mainų klubas
- Šviesų menas
- „Skydas ir kardas“
- Raidžių dėlionė
- Rutuliukai
- Daug vienetų
- Trumpa programa
- Mėgstamiausi gėrimai
- Jauniai
- Etapas 1
- Užtvankos tuneliai
- Mėgstamiausi gėrimai
- Labirintas
- Picerija „Bebrynė“
- Araboto kelias
- Honomakato lankstusis tinklas
- Važiavimas dviračiu
- Kritulių pasiskirstymas
- Knygų mainų klubas
- Šviesų menas
- „Skydas ir kardas“
- Spalvotas pastatas
- Šifravimo ratas
- Atstumas tarp žodžių
- Rutuliukai
- Failų atsisiuntimas
- Žiedinių sankryžų miestas
- Daug vienetų
- Užtvankos tuneliai
- Etapas 2
- Etapas 1
- Kolegos
- Etapas 1
- Pramogų bebravietė
- Sugedusi laistymo sistema
- Mėgstamiausi gėrimai
- Užtvankos tuneliai
- Saldainių rinkimas
- Labirintas
- Araboto kelias
- Važiavimas dviračiu
- Bebragrama
- Biblioteka
- Spalvotas pastatas
- Vaizdų glaudinimas
- Trumpiausias kelias
- Atstumas tarp žodžių
- Rutuliukai
- Skaitmenų atpažinimas
- Šifro „nulaužimas“
- Daug vienetų
- Etapas 2
- Etapas 1
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:____
Š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.
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.