Vaje 7.4.2022 Minimalna vpeta drevesa
Zahteve zaključka
Odprto: četrtek, 7 april 2022, 00:00 AM
Rok za oddajo: četrtek, 14 april 2022, 00:00 AM
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?