Izpitno vprašanje RAČ2PRA 16300

Iz MaFiRaWiki

GFDL Avtor tega članka je študent/ka KlaraRozina.

Pripravil/a ga je pri predmetu Računalništvo 2 (FMF PRA).


Kljub temu ste vsi vabljeni k urejanju in popravkom, saj je bistvo wikija ravno v sodelovalnem delu.

Vprašanje

Meta ima šest prijateljic: Aljo, Jano, Tejo, Sašo, Kajo in Uršo. Vse so navdušene uporabnice mobilnih telefonov. Ker mora vsako novico vsaka takoj sporočiti ostalim šestim, so njihovi telefonski računi zelo visoki. Ko so nekaj mesecev spremljale stroške povprečnega pogovora, so prišle do matrike stroškov posameznega klica. Kako naj se kličejo med seboj, da se bo novica med njimi kar najhitreje raznesla?

Odgovor

Z zapisovanjem stroškov klicev, so prijateljice dobile tabelo, s katero si bomo pomagali, da bomo prišli do najbolj ugodnega raznašanja novice.

slika:StroskiKlicev.jpg

Za reševanje si pomagamo s Kruskalovim algoritmom. Na podlagi tabele združujemo najcenejše povezave, kajti želimo, da bi prijateljice tudi malo prihranile.

1. združimo povezavo med Jano in Kajo, ki nas stane 15
2. združimo povezavo med Kajo in Ulo, ki nas stane 16
3. združimo povezavo med Jano in Tejo, ki nas stane 16
4. združimo povezavo med Aljo in Tejo, ki nas stane 21
5. združimo povezavo med Sašo in Kajo, ki nas stane 31

Rešitev je povezava: J - K - U - T - A - S

Še skica minimalnega vpetega drevesa:

slika:MinimalnoVpetoDrevo.jpg

Osebna orodja