2014 2015 2016 2017 2018

Grupinis sprendimas

Taškai: 6

Organizuodama vakarėlį, Sara turi pasitarti su penkiais draugais: Akvile, Roku, Karoliu, Deividu ir Elze.
Sara gali kalbėtis su Elze iš karto. Tačiau norėdama pasikalbėti su kitais draugais, Sara turi laikytis toki sąlygų:
1)    prieš kalbėdama su Deividu, ji turi pasikalbėti su Akvile;
2)    prieš kalbėdama su Roku, ji turi pasikalbėti su Elze;
3)    prieš kalbėdama su Karoliu, ji turi pirma pasikalbėti su Roku ir Deividu;
4)    prieš kalbėdama su Akvile, ji privalo pasikalbėti su Roku ir Elze.
Kokia eilės tvarka Sara turi pasikalbėti su savo draugais?

Paaiškinimas

Sąlygų tenkinimas yra informatikos problema, sutinkama realiame gyvenime. 
Ši individų norų ir jų eiliškumo problema gali būti sumodeliuota grafu. Grafas sudaromas iš viršūnių (individų) ir lankų, jungiančių viršūnes, tarp kurių yra ryšys (sąlygos pokalbiams. Šiuo atveju grafas ypatingas: kadangi yra nusakytas eiliškumas, jame nėra ciklų. Ciklu laikomas kelias, kuris prasideda vienoje viršūnėje, eina keliais lankais ir grįžta į pradinę viršūnę. Šio uždavinio grafas – orientuotas grafas, neturintis ciklų. Todėl problema priklauso prie topologijų rūšies. Surikiuojame viršūnes pagal jų lankų skaičių. Išrinkime visas viršūnes, neturinčias lankų, ir padėkime jas atsakymo pradžioje. Tada šaliname šias viršūnes iš grafo ir tęsiame procesą su nauju grafu. Visuomet bus viršūnių, neturinčių lankų, buvimas, nes grafe nėra ciklų.

Reikšminiai žodžiai: orientuotas grafas, ribojimas (sąlyga), grafas be ciklų, topologinis rikiavimas.

Atsakymas

Atsakymas: Elzė – Rokas – Akvilė – Deividas – Karolis
Šioje užduotyje reikia atsižvelgti į individų norus, jų sąlygas pokalbiams.
Elzė yra vienintelė draugė, kuri nenusakė jokių sąlygų, todėl ji turi būti pirma.
Rokas priklauso tik nuo Elzės, todėl jis gali būti antras.
Akvilė priklauso nuo Roko ir Elzės, todėl ji gali būti trečia.
Deividas priklauso nuo Akvilės, todėl jis turi eiti po jos.
Pagaliau Karolis priklauso nuo Roko ir Deivido, todėl jis yra paskutinis.
Jokia kita seka netenkina visų išreikštų norų.

Interaktyvi užduotis