Računalništvo 2

1) Ponovitev Primovega algoritma (vhod, izhod, ideja algoritma, časovna zahtevnost)

2) Simulacija Primovega algoritma na grafu:

3) Pokaži, da je MVD enolično, če so vse uteži. v grafu različne. Namig: protislovje

4) Kako bi poiskal najdražje vpeto drevo?

5) Naj bo T MVD in T' drevo najkrajših razdalj od vozlišča s do vseh ostalih. Vsaki uteži sedaj prištejemo 1. Ali se T in T' spremenita?

6) Recimo, da imamo utežen graf G in njegovo MVD T (eno izmed možnih). Sedaj določeni povezavi e spremenimo utež. Opiši čim bolj učinkovit algoritem, ki popravi T.

7)* Kako bi poiskal "drugo" najcenejše vpeto drevo? Tretje? Kako bi poiskal vsa MVD v grafu?