Minimální kostra grafu, Kruskalův algoritmus

Příklad

• Máme za úkol propojit města $v_1,...,v_n$ elektrickým vedením, a to tak, aby výstavba vedení byla co nejlevnější. Musíme tedy rozhodnout, mezi kterými městy máme natáhnout elektrické dráty tak, aby se elektřina mohla dostat z každého města do každého jiného města. Přitom víme, že mezi některými dvojicemi měst přímé propojení postavit nelze. Pokud města $v_i$ a $v_j$ propojit lze, známe náklady na výstavbu vedení mezi $v_i$ a $v_j$.

• Kostra neorientovaného grafu $G$ je jeho podgraf $G^{\prime }$, který je stromem a obsahuje všechny vrcholy grafu $G$.
• Je-li $w:E\to {\mathbb{R}}^{+}$ hranové ohodnocení grafu $G=<V,E>$, nazývá se kostra $G^{\prime }=<V,E^{\prime }>$ minimální kostra, pokud má ze všech koster grafu $G$ nejmenší hodnotu $w(G^{\prime })$, kde $w(G^{\prime })={\sum }_{\{u,v\}\in E^{\prime }}w(\{u,v\})$

Kruskalův Algoritmus

• Vstup:
  • Souvislý neorientovaný graf $G=<V,E>$ s $n$ vrcholy a $m$ hranami
  • Ohodnocení $w:E\to {\mathbb{R}}^{+}$
• Výstup:
  • Množina hran $E^{\prime }\subseteq E$ takový, že $G^{\prime }=<V,E^{\prime }>$ je minimální kostra grafu $G$
• Postup:
  1. Setřiď hrany vzestupně podle ohodnocení, tj. utvoř posloupnost $e_1,...,e_m$ všech hran z $E$ tak, že $w(e_1)\le ...\le w(e_m)$
  2. $E_0=\varnothing ,i=0$
  3. Dokud $E_i$ neobsahuje $n-1$ hran, prováděj:
     1. $i=i+1$
     2. $$\begin{gathered} E_i=\text{cases}{E}_{i-1}\cup \{e_i\}\text{ pokud }<V,E_{i-1}\cup \{e_i\}>\text{neobsahuje kruzˇnici} \\ {E}_{i-1}\text{ v opacˇneˊm prˇıˊpadeˇ} \end{gathered}$$
  4. $E^{\prime }=E_i$

Příklad

graph LR
A -- "2" --- B;
A -- "3" --- D;
A -- "3" --- C;
B -- "4" --- C;
C -- "1" --- E;
B -- "3" --- E;
C -- "5" --- D;
D -- "7" --- F;
E -- "8" --- F;
F -- "9" --- G;

graph LR
A -- "2" --- B;
A -- "3" --- D;
A -- "3" --- C;
B -- "4" --- C;
C -- "1" --- E;
B -- "3" --- E;
C -- "5" --- D;
D -- "7" --- F;
E -- "8" --- F;
F -- "9" --- G;

linkStyle 4 stroke:Red;

graph LR
A -- "2" --- B;
A -- "3" --- D;
A -- "3" --- C;
B -- "4" --- C;
C -- "1" --- E;
B -- "3" --- E;
C -- "5" --- D;
D -- "7" --- F;
E -- "8" --- F;
F -- "9" --- G;

linkStyle 4 stroke:Red;
linkStyle 0 stroke:Red;

…

graph LR
A -- "2" --- B;
A -- "3" --- D;
A -- "3" --- C;
B -- "4" --- C;
C -- "1" --- E;
B -- "3" --- E;
C -- "5" --- D;
D -- "7" --- F;
E -- "8" --- F;
F -- "9" --- G;

linkStyle 4 stroke:Red;
linkStyle 0 stroke:Red;
linkStyle 1 stroke:Red;
linkStyle 2 stroke:Red;
linkStyle 7 stroke:Red;
linkStyle 9 stroke:Red;

• Minimální kostra grafu:

graph LR

A -- "3" --- D;
D -- "7" --- F;
F -- "9" --- G;
A -- "3" --- C;
C -- "1" --- E;
A -- "2" --- B;

linkStyle default stroke:Red;

Navigace

Předchozí: Hledání nejkratší cesty, Dijkstrův algoritmus Následující: Stromy, kořenové stromy, vztahy mezi výškou, počtem vrcholů, počtem listů Celý okruh: 1. Teoretické základy informačních technologií