Izpitno vprašanje RAČ2PRA 16400

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

Vsebina

Vprašanje

Meta ima šest prijateljic: Aljo, Jano, Tejo, Sašo, Kajo in Uro. 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. Zanima nas, kako naj se novica najceneje prenese med vsemi prijateljicami. Če se torej Meta pogovarja neposredno z Aljo, so stroki klica 50 SIT. A novica od Mete do Alje lahko pride tudi tako, da Meta pokliče Jano (kar stane 21 SIT), Jana pa potem prenese novico Alji (kar stane 16 SIT) - torej skupno 37 SIT (ceneje) !

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:Klepetulje1.jpg

Za reševanje si pomagamo s Kruskalovim algoritmom. Kruskalov algoritem jemlje najcenejše povezave oz. tiste povezave, ki nosijo v našem primeru najmanjše stroške. Toda to ne pomeni, da smemo vzeti vse cenejše povezave, ki so nam ponujene. Za naš primer: Alja je povezana z Jano, Jana pa s Tejo, če bi v tabeli našli povezavo, ki je poceni in povezuje Aljo ter Tejo, te povezave ne bi mogli vzeti. Vzrok tega je, če sta Alja in Teja že povezani posredno, potem ju ne moremo neposredno povezati, ker bi nastal cikel. Na podlagi tabele združujemo najcenejše povezave, kajti želimo, da bi prijateljice tudi malo prihranile.

  • združimo povezavo med Meto in Kajo, ki nas stane 15
  • združimo povezavo med Aljo in Jano, ki nas stane 16
  • združimo povezavo med Aljo in Sašo, ki nas stane 15
  • združimo povezavo med Jano in Tejo, ki nas stane 20
  • združimo povezavo med Tejo in Kajo, ki nas stane 13
  • združimo povezavo med Kajo in Uršo, ki nas stane 16

Najugodnejša možna povezava, da izpeljejo pogovor preko mobilnikov, je 13 + 15 + 15 + 16 + 16 + 20 = 95 enot. In sicer, novico, ki jo izve Saša, lahko na najcenejši način razširijo takole: Saša novico sporoči Alji. Ta jo posreduje Jani, ki jo prenese Teji. Teja obvesti Kajo, ki pa obvesti tako Meto kot Uršo (to je le en izmed načinov kako lahko klepetajo za 95 enot).


Minimalno vpeto drevo:

Slika:KruskalovKlepetulje6.jpg


Definicija minimalnega vpetega drevesa

Imamo graf G(V,E), kjer je V množica vozlišc in E množica neusmerjenih povezav. Vsa vozlišča grafa so povezana (stopnja vsakega vozlišča je vsaj 1), povezave pa imajo uteži. Minimalno vpeto drevo T je acikličen podgraf grafa G, ki vsebuje vsa vozlišča grafa in zanj velja, da je njegova skupna teža (vsota uteži vseh povezav v njem) minimalna. Najmanjše vpeto drevo imenujemo najcenejše vpeto drevo ali minimalno vpeto drevo.

Cena je vsota drevesa vrednosti vseh povezav tega drevesa. Potem je minimalno vpeto drevo tisto vpeto drevo, ki ima manjšo ali enako ceno vsem drugim vpetim drevesom.

Kruskalov postopek

Kruskalov postopek pa gradi minimalni vpeti gozd. Na začetku je vsako vozlišče eno drevo. V enem koraku postopka združi dve minimalni vpeti drevesi v eno minimalno vpeto drevo, tako da uporabi minimalno povezavo med dvema drevesoma. Paziti moramo le na to, da povezava ne povezuje dveh vozlišč v istem drevesu, saj sicer ustvarimo cikel. V povezanem grafu Kruskalov postopek zaporedoma združi vsa vpeta drevesa v eno minimalno vpeto drevo

Osebna orodja