Minimální kostra grafu
5.1 Problém minimální kostry
Dán je souvislý graf G = (V, E) s ohodnocením hran w(e). Hledáme kostru H, pro kterou je součet ohodnocení všech hran minimální:
Kostra H se nazývá minimální kostra a w(H) cena kostry.
Problém vznikl při elektrifikaci jižní Moravy (1925–1926, Otakar Borůvka). Další algoritmy: Jarník (1930), Kruskal (1956).
5.2 Borůvkův algoritmus
Borůvkův algoritmus
- Začni s grafem T = (V, ∅) — všechny vrcholy, žádné hrany
- Opakuj dokud T má alespoň 2 komponenty:
- Pro každou komponentu Ti vyber nejlehčí incidentní hranu
- Všechny vybrané hrany přidej do T
- Výstup: minimální kostra T
5.3 Jarníkův algoritmus (Prim)
Jarníkův algoritmus
- Inicializace: V' = {x} (libovolný vrchol), E' = {}
- Opakuj dokud V' ≠ V:
- Vyber hranu (u,v) s minimální cenou takovou, že u ∈ V' a v ∉ V'
- Přidej v do V', přidej (u,v) do E'
- Výstup: T(V', E') je minimální kostra
Vytvoří se tabulka, kde pro každý nezařazený vrchol evidujeme nejlevnější hranu do již zařazené množiny. V každém kroku vybereme vrchol s nejmenší hodnotou.
Graf s 8 vrcholy (a–h), začneme z vrcholu a:
| Krok | Přidaný vrchol | Hrana | Cena |
|---|---|---|---|
| 1 | c | ac | 2 |
| 2 | d | ad | 5 |
| 3 | e | ce | 6 |
| 4 | b | ab | 7 |
| 5 | g | bg | 8 |
| 6 | h | dh | 11 |
| 7 | f | hf | 3 |
Cena kostry: 2 + 5 + 6 + 7 + 8 + 11 + 3 = 42
5.4 Kruskalův algoritmus
Kruskalův algoritmus
- Setřiď všechny hrany podle ohodnocení od nejmenšího
- T = (V, ∅)
- Pro každou hranu (od nejlehčí):
- Pokud přidání hrany nevytvoří kružnici (koncové vrcholy leží v různých komponentách), přidej ji do T
- Výstup: minimální kostra T
Setříděné hrany: ac-2, fh-3, ad-5, ce-6, ab-7, bd-8, bg-8, dh-11, df-12, ...
| Hrana | Cena | Komponenty | Přidána? |
|---|---|---|---|
| ac | 2 | {a,c}{b}{d}{e}{f}{g}{h} | ANO |
| fh | 3 | {a,c}{b}{d}{e}{f,h}{g} | ANO |
| ad | 5 | {a,c,d}{b}{e}{f,h}{g} | ANO |
| ce | 6 | {a,c,d,e}{b}{f,h}{g} | ANO |
| ab | 7 | {a,b,c,d,e}{f,h}{g} | ANO |
| bd | 8 | oba v {a,b,c,d,e} | NE (kružnice!) |
| bg | 8 | {a,b,c,d,e,g}{f,h} | ANO |
| dh | 11 | {a,b,c,d,e,f,g,h} | ANO |
Cena kostry: 2+3+5+6+7+8+11 = 42
Výsledná minimální kostra:
Cvičení — Minimální kostra
Úkol 20 — Vodovodní trubky: Vodovodní společnost propojuje domácnosti. Hrany s ohodnocením: ae-1, ac-1, bj-1, df-1, eg-1, hi-1, ab-2, cf-2, dj-2, ce-3, ai-4, dg-4, bh-5, bc-6, cj-7, cd-7. Najděte minimální kostru Kruskalovým algoritmem.
Seřazené hrany: ae-1, ac-1, bj-1, df-1, eg-1, hi-1, ab-2, cf-2, dj-2, ce-3, ai-4, dg-4, bh-5, bc-6, cj-7, cd-7
Přidáváme: ae(1), ac(1), bj(1), df(1), eg(1), hi(1), ab(2), cf(2), dj(2)
ce-3 by vytvořilo kružnici (a,c,e už jsou v jedné komponentě) ⇒ přeskočit
Po přidání dj-2 jsou všechny vrcholy v jedné komponentě.
Cena kostry: 1+1+1+1+1+1+2+2+2 = 14 (9 hran pro 10 vrcholů)
Úkol 21 — Chráněná lokalita (Jarník): 7 míst (a–g). Použijte Jarníkův algoritmus s tabulkou. Matice vzdáleností:
| a | b | c | d | e | f | g | |
|---|---|---|---|---|---|---|---|
| a | - | 2 | 3 | ||||
| b | - | 3 | |||||
| c | 2 | - | 1 | 3 | 3 | ||
| d | 1 | - | 4 | ||||
| e | 3 | 3 | - | ||||
| f | 3 | 3 | 4 | - | 2 | ||
| g | 2 | - |
Začneme z vrcholu a:
| Krok | Přidaný | Hrana | Cena |
|---|---|---|---|
| 1 | c | ac | 2 |
| 2 | d | cd | 1 |
| 3 | e | ce | 3 |
| 4 | b | eb | 3 |
| 5 | f | af nebo cf | 3 |
| 6 | g | fg | 2 |
Hrany kostry: ac, cd, ce, eb, af, fg
Cena: 2+1+3+3+3+2 = 14
Kvíz: Kruskalův algoritmus hrany zpracovává...
- a) náhodně
- b) od nejdražší po nejlevnější
- c) od nejlevnější po nejdražší
- d) podle abecedy
Správná odpověď: c) od nejlevnější po nejdražší
Kvíz: Při Kruskalově algoritmu hranu nepřidáme, když...
- a) je příliš drahá
- b) by vytvořila kružnici
- c) spojuje dva listy
- d) je most
Správná odpověď: b) by vytvořila kružnici