Žodžių grandinės

Taškai: 9

Tomui namų darbams užduota parengti projektą. Jis turi surašyti žodžius ant kortelių ir sujungti jas gumine juosta.

Mokytoja liepė sujungti bet kuriuos du žodžius, kurie skiriasi tik viena raide.

Kaip padarė Tomas, parodyta dešinėje.

Pabaigęs namų darbus Tomas išėjo pažaisti į kiemą.

Kai grįžo, nustebo pamatęs, ką padarė jo broliukas Petriukas: ištrynė visus žodžius. Be to, kortelės buvo visiškai sumaišytos (paveikslėlis kairėje).

Petriukas labai nusiminė, bet Tomas jį nuramino: „Nesijaudink, aš žinau, kur turi būti teisingi žodžiai, o tu man gali padėti“.

Kaip turi būti teisingai surašyti žodžiai kortelėse?

A. B.
C. D.
Paaiškinimas

Sistemą, kurią Tomas sukonstravo iš kortelių ir guminių juostų, galima pavaizduoti kaip grafą. Informatikoje grafas yra viršūnių aibė, kurią šiame uždavinyje atitinka kortelės, ir briaunų aibė, kurią atitinka juostos.

Nepaisant to, kad pasukta sistema atrodo kitaip, jos struktūra iš tikrųjų nepasikeičia – sistema vis dar sudaryta iš tų pačių kortelių ir juostų. Du grafai, turintys vienodą struktūrą, vadinami izomorfiniais.

Grafai dažnai naudojami informatikoje. Jais modeliuojamos įvairiausios struktūros iš objektų ir jų ryšių, pavyzdžiui, traukinių maršrutų arba vandentiekių išdėstymo schemos. Tai leidžia pagal poreikį keisti tos pačios schemos atvaizdavimą, transformojant ją įvairiai, bet tik tol, kol schemos išlieka izomorfiškos.

Norint įrodyti, kad du dideli grafai yra izomorfiški, tam naudojant kompiuterinius algoritmus, reikia daug išteklių – galingų kompiuterių, daug valandų skaičiavimų, o tai brangu.

Atsakymas

Teisingas atsakymas – B.

Panagrinėkime vieną iš keleto galimų sprendimų.

Yra dvi kortelės su trimis juostomis: LATAS ir BATAS.
Yra dvi kortelės su dviem juostomis: BARAS ir RATAS.
Yra dvi kortelės su viena juosta: LAPAS ir KARAS.
Yra tik viena kortelė su viena juosta, kuri jungia kitą kortelę, turinčią tik vieną juostą – tai kortelė KARAS. Tada antroji likusi kortelė su viena juosta turi būti LAPAS.
Kortelė, sujungta su LAPAS, turi dvi juostas – tai bus kortelė LATAS, o kortelė, sujungta su KARAS turi vieną juostą – tai bus kortelė BARAS.
Tuomet priešpaskutinė likusi kortelė su trimis juostomis yra BATAS, o paskutinė likusi kortelė su dviem juostomis yra RATAS.

Kai išsiaiškinama, kad B yra teisingas atsakymas, galima iš karto pastebėti, kad kiti trys atsakymai yra neteisingi, nes skiriasi kortelių juostų skaičius ir sujungimai.

 

 
Informacija atnaujinta 2015-12-03 07:50:57
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.