Minimalno vpeto drevo - zgled 1

Minimalno vpeto drevo - zgled 1

Avtor: Matija Lokar

Več o projektu...

Omrežje

(vpeto_zgled1_1.png)

(vpeto_zgled1_2.png)

(vpeto_zgled1_3.png)

(vpeto_zgled1_4.png)

(vpeto_zgled1_5.png)

(vpeto_zgled1_6.png)

(vpeto_zgled1_7.png)

(vpeto_zgled1_8.png)

(vpeto_zgled1_9.png)

(vpeto_zgled1_10.png)

(vpeto_zgled1_11.png)

(vpeto_zgled1_12.png)

(vpeto_zgled1_13.png)

(vpeto_zgled1_14.png)

(vpeto_zgled1_15.png)

(vpeto_zgled1_16.png)

(vpeto_zgled1_17.png)

(vpeto_zgled1_18.png)

(vpeto_zgled1_19.png)

(vpeto_zgled1_20.png)

(vpeto_zgled1_21.png)

(vpeto_zgled1_22.png)

(vpeto_zgled1_23.png)

(vpeto_zgled1_24.png)

(vpeto_zgled1_25.png)

(vpeto_zgled1_26.png)

(vpeto_zgled1_27.png)

(vpeto_zgled1_28.png)

(vpeto_zgled1_29.png)

Minimalno vpeto drevo po Primovem postopku

(vpeto_zgled1_30.png)

(vpeto_zgled1_31a.png) (vpeto_zgled1_31b.png)

(vpeto_zgled1_32.png)

Cena grafa: 32

Kurskalov algoritem

Po privzetku gradimo gozd in tekočo najcenejšo povezavo privzamemo, če ne naredi cikla. To pa bo natanko tedaj, ko nista obe vozlišči povezave (u,v) v istem drevesu, v isti (disjunktni) komponenti

Omrežje

(vpeto_zgled1_34.png)

(vpeto_zgled1_35.png)

(vpeto_zgled1_36.png)

(vpeto_zgled1_37.png)

(vpeto_zgled1_38.png)

(vpeto_zgled1_39.png)

(vpeto_zgled1_40.png)

(vpeto_zgled1_41.png)

(vpeto_zgled1_42.png)

(vpeto_zgled1_43.png)

(vpeto_zgled1_44.png)

(vpeto_zgled1_45.png)

(vpeto_zgled1_46.png)

(vpeto_zgled1_47.png)

Minimalno vpeto drevo po Kruskalovem postopku

(vpeto_zgled1_48.png)

(vpeto_zgled1_49a.png) (vpeto_zgled1_49b.png)

(vpeto_zgled1_50.png)

Primerjava končnih grafov

(vpeto_zgled1_51a.png)
Primov algoritem
(vpeto_zgled1_51b.png)
Kurskalov algoritem

Enakost minimalnih vpetih dreves

  • Enakost minimalnih vpetih dreves je slučaj, ne pravilo
  • Postopka v splošnem lahko vrneta različni minimalni vpeti drevesi
0%
0%