Povzetek
|
Poiskali smo torej minimalno vpeto drevo v povezanem neusmerjenem grafu. Rešitev smo gradili kot "gozd" - v začetku smo imeli n dreves, na vsakem koraku smo dve drevesi združili, in sicer z najcenejšo dopustno povezavo. Po natanko n-1 korakih smo dobili povezan graf brez ciklov - iskano minimalno vpeto drevo. S tem smo rešili problem najcenejšega železniškega ali telefonskega omrežja, najučinkovitejše vohunske mreže, za računalniško mrežo smo porabili kar najmanj kabla ... O čakanju pri avtomehaniku in gradnji viaduktov pa kdaj drugič, Kruskal le ni čarobna rešitev za vse probleme. |
|