Vpeto drevo

Iz MaFiRaWiki

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

Kaj pomeni to opozorilo?

Vpeto Drevo

Vpeto drevo dobimo iz povezanega grafa G na n vozliščih tako, da odstranimo vse povezave razen n-1, da dobimo povezan graf G'. Graf G' je povezan in brez ciklov. Rečemo, da je G' vpeto drevo grafa G.

  • Zgled:

Če v ciklu odstranimo povezavo, dobimo vpeto drevo, ki je pot.

Minimalno vpeto drevo

Minimalno vpeto drevo grafa G je acikličen podgraf grafa G, ki vsebuje vsa vozlišča grafa G in je vsota uteži vseh povezav, ki jih podgraf vsebuje, minimalna.

  • Uporaba:
  • S problemom čim cenejše realizacije se največkrat srečamo pri načrtovanju komunikacijskih, elektroenergetskih ali prometnih omrežij. Želimo najti najcenejšo (najkrajšo, najugodnejšo...) možnost, katero nam predstavlja minimalno vpeto drevo.

  • Zgled
  • Primer grafa in njegovega minimalnega vpetega drevesa:
    Slika:Graf.jpg Slika:MinDrevo.jpg


    Glej tudi

    Osebna orodja