Izpitno vprašanje DIRI2005 16100

Iz MaFiRaWiki

Vprašanje

|Vpr. 16100| Kaj je minimalno vpeto drevo in uporaba slednjega.

Odgovor

Imamo graf G=(V,E), kjer je V množica vozlišč (vozlišče) in E množica neusmerjenih povezav (povezava). 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. Ker je T aciklična podmnožica, je to drevo.

Uporaba

Pri načrtovanju raznih omrežij (npr. komunikacijskih, prometnih, elektroenergetskih, ipd.) se srečujemo s problemom čim cenejše (krajše, ugodnejše…) realizacije. Kako torej čim ceneje povezati neko omrežje?

Vozlišča si lahko predstavljamo kot hiše, poti med hišami pa kot neusmerjene povezave v grafu. Vsaka povezava je opremljena z utežjo, to je ceno poti med izbranima hišama. Mi želimo čim ceneje med seboj povezati vse hiše. Za povezavo vseh hiš v mestu zadošča, da obstaja ena pot med vsakim mestom - to pa je ravno minimalno vpeto drevo.

Osebna orodja