• Imamo n računalnikov – poštnih strežnikov. Radi bi jih povezali tako, da je z vsakega mogoče pošiljati pošto vsakemu
• Med računalniki lahko izbiramo različne načine povezovanja (različne ponudnike) z različnimi stroški
• Kako se odločiti za ponudnike povezav, da bodo naši stroški najmanjši?

Meta ima 6 prijateljic: Aljo, Jano, Tejo, Sašo, Kajo in Uršo. Vse so navdušene uporabnice mobilnih telefonov. Ampak ker mora vsako novico, ki jo izve ena, izvedeti tudi ostalih 6, so telefonski računi zelo veliki. Ko so nekaj časa spremljale stroške povprečnega pogovora, so prišle do naslednje matrike stroškov posameznega klica

Če se torej Meta pogovarja z Aljo, so stroški klica 50 centov, če Saša kliče Uršo (ali obratno) 52 centov, če Urša govori s Kajo 16 centov, .... Ugotovi, kako naj se kličejo, da bo vsako novico izvedela vsaka in da bodo za razširitev ene novice porabile kar se da malo denarja.

• Denimo, da imamo le štiri prijateljice
• A – B: 10
• B – C: 15
• A – C: 12
• A – D: 6
• D – B: 7
• C in D pa se ne marata in ne govorita

• Vemo, kje moramo narediti postaje

  • Vsekakor tam, da ima pomembna osebnost dovolj blizu postajo
• Iz vsake postaje mora biti moč priti do druge
• Poznamo stroške za neposredno povezavo postaje i in postaje j.
• Kar se da poceni!

• Verjetnost, da prestrežejo sporočilo agenta i agentu j je p[i,j].
• Kako naj za sporočila izvedo vsi, tako, da bo verjetnost, da je sporočilo prestreženo, minimalna.

• Klepetave prijateljice
• Podzemna železnica
• Povezava poštnih strežnikov
• ...

• Dano je omrežje

  • Množica točk in povezav med njimi z določenimi vrednostmi
  • "vrednostni graf"

  • Želimo povezati vse točke

    • iz vsake želimo priti v vsako
    • n točk: torej n – 1 povezav

• N točk
• N – 1 povezav, povezano (iz vsake točke se da priti do vsake točke)
• To je značilnost drevesa (ne dvojiškega, ampak splošnega)
• Iščemo t.i. vpeto drevo grafa.

• Vpeto?

  • Uporabiti je potrebno vse točke grafa
  • smemo uporabiti samo obstoječe povezave

• Drevo?

  • Povezanost n točk z uporabo n – 1 povezav

• Vpetih dreves je lahko več

  • Primer

• Med n mesti želimo speljati kabelsko omrežje

  • Iz oddajne točke moramo znati spraviti signal v vsa mesto (neposredno ali preko drugih mest)

    • Iščemo vpeto drevo

  • Seveda čim ceneje

    • Iščemo minimalno vpeto drevo
    • Cena drevesa: Vsota vrednosti povezav

• Ali je potrebno začeti gradnjo tam, kjer bo centralna oddajna postaja?

  • Ne, saj je važna le dosegljivost vsake točke
• Začnimo v nekem mestu /tistemu, ki ima najboljše restavracije :) / - recimo, da je to mesto a
• Med tistimi mesti, do katerih je možno priti, izberemo tistega, do katerega lahko položimo kabel najceneje (recimo, da je to mesto c)
• Položimo kabel

• Spet bomo izbrali najcenejše

  • A od kje?
  • Iz mesta, kamor smo ravno potegnili kabel (c)?
  • Ne, potrebno je upoštevati vsa dosegljiva mesta
• Pregledamo, koliko nas stane gradnja do mest, dosegljivih iz a in c
• Torej – poiščemo najcenejšo povezavo med vozlišči v doslej zgrajenem vpetem drevesu in tistimi, ki tam še niso
• Dodamo najcenejše dosegljivo mesto – denimo x

• Pregledamo, koliko nas stane gradnja do mest, dosegljivih iz a, x (zadnje dodano) in c
• Seveda upoštevamo samo tiste povezave iz a, c in x, ki gredo do "novih" mest – povezave med a, c in x nas NE zanimajo več (čeprav so morda poceni, a so nepotrebne)
• Torej – poiščemo najcenejšo povezavo med vozlišči v doslej zgrajenem vpetem drevesu in tistimi, ki tam še niso

• Iščemo vpeto drevo
• Vpetih dreves je (lahko) veliko
• Iščemo najcenejše
• Jih je lahko več?
• Iščemo eno!

• Začni s poljubnim vozliščem. To je začetno vpeto drevo.

• Dokler ne dodaš n-1 vozlišč, ponavljaj

  • Izberi najcenejšo povezavo med vozlišči v doslej zgrajenem vpetem drevesu in vozlišči, ki še niso del drevesa
  • Dodaj to povezavo v drevo

• Pripravi vrsto s prednostjo
• Vstavi začetno vozlišče

• Ponavljaj, dokler vrsta ni prazna

  • Poišči vse povezave med zadnjim dodanim vozliščem in vozlišči, ki niso v drevesu
  • Dodaj jih v vrsto s prednostjo

  • Vzemi najcenejšo povezavo

    • Če povezuje vozlišče v drevesu in vozlišče, ki ni v drevesu, jo dodaj v doslej zgrajeno vpeto drevo
    • Sicer jo zavrzi in ponovi ta korak

http://students.ceid.upatras.gr/~papagel/project/prim.htm

• Ker imamo n vozlišč, bo potrebno n - 1 povezav.
• Vzemimo najcenejšo in povežimo vozlišči.
• Vzemimo najcenejšo med preostalimi povezavami

• Dve možnosti:

  • Med povezanima vozliščema in novim
  • Med dvema novima vozliščema

• Kasneje

  • Po nekaj vozlišč skupaj že povezanih v vpeta drevesa (za tisti del omrežja), nekaj "osamljenih" vozlišč.

• Če je najcenejša povezava "notranja"
  (Povezuje vozlišči znotraj istega vpetega drevesa)

  • nas NE zanima

• Torej na tekočem koraku

  • Vzamemo najcenejšo med preostalimi povezavami

• Več možnosti:

  • "slabe"

    • Med vozlišči istega vpetega drevesa

  • dobre

    • Med "osamljenim vozliščem" in vpetim drevesom
    • Med dvema "osamljenim vozliščem"

• V bistvu sta obe "dobri" možnosti isti

  • Posamezno vozlišče je tudi vpeto drevo!
• Torej na tekočem koraku imamo nekaj minimalnih vpetih dreves
• Povežemo tisti vpeti drevesi, ki ju je najceneje povezati

http://students.ceid.upatras.gr/~papagel/project/kruskal.htm

• Omrežje
• N vozlišč, m povezav, vrednosti povezav
• Če povezave ni: vrednost
• Primov algoritem (1959)
• Kruskalov algoritem (1956)

http://www.cs.usask.ca/resources/tutorials/csconcepts/graphs/tutorial/advanced/prim/mst.html

• Prvi algoritem: Čeh Otakar Borůvka, 1926. Načrt češkega el-omrežja.
• Največ: Prim, Kruskal
• Najhitrejši znani: Chazell, 1999

• Še nekaj povezav:

  • http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/kruskal/Kruskal.shtml.en
  • http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/dijkstra/Prim.shtml.en
  • http://students.ceid.upatras.gr/~papagel/project/kef5_4.htm
  • http://www.guides.sk/suuri/Prim.html
  • http://www.guides.sk/suuri/kruskal/Kruskal.html
  • http://mscmga.ms.ic.ac.uk/jeb/or/graph.html
  • http://www.wikipedia.org/wiki/Minimum_spanning_tree