Kostra grafu
Proč to potřebuji?
Kostra grafu je klíčový pojem teorie grafů s přímými aplikacemi v praxi. Když potřebujete propojit všechna města silniční sítí s co nejmenším počtem silnic, nebo navrhnout počítačovou síť s minimálním počtem kabelů tak, aby byly všechny uzly propojené — hledáte právě kostru grafu. Kostra je nejúspornější způsob, jak udržet graf souvislý.
Předpoklady: Základní pojmy teorie grafů (vrcholy, hrany, souvislost), pojem stromu a jeho vlastnosti.
Teorie
4.1 Kostra grafu
Kostra souvislého grafu G je podgraf, který:
- Obsahuje všechny vrcholy grafu G
- Je strom (souvislý a bez kružnic)
Kostra je tedy faktorový podgraf, který je stromem.
Graf G (7 hran)
Kostra (4 hrany = n-1)
Každý souvislý graf obsahuje kostru.
Kostra grafu G s n vrcholy má vždy n - 1 hran.
Z grafu postupně odebírejte hrany, které leží na nějakém cyklu (jejich odebráním se graf nerozpadne). Pokračujte, dokud nezůstane strom.
4.2 Počet koster
| Graf | Počet koster t(G) |
|---|---|
| Strom T | 1 |
| Kn | nn-2 |
| K2,n | n · 2n-1 |
| Cn (kružnice) | n |
Pokud graf G tvoříme z hranově navzájem disjunktních podgrafů G1, G2, ..., pak:
Graf se skládá z K4, C3 a stromu T:
t(G) = t(K4) · t(C3) · t(T) = 42 · 3 · 1 = 16 · 3 = 48
Cvičení — Kostra grafu
Úkol 17 — Počet koster: Určete počet koster grafu, který se skládá z K4, C3, T a K2,3 jako hranově disjunktních podgrafů.
t(G) = t(K4) · t(C3) · t(T) · t(K2,3)
= 42 · 3 · 1 · 3·22
= 16 · 3 · 1 · 12 = 576
Úkol 18 — Souvislost a skóre: Může být (1,1,1,1,1,1,1,1,1,2,3,4,4,4,4,10) skóre souvislého grafu?
1) Je to skóre? ANO (ověřeno algoritmem).
2) Pro souvislý graf musí platit m ≥ n - 1.
n = 16, m = 40/2 = 20
20 ≥ 16 - 1 = 15? ANO ⇒ MŮŽE to být skóre souvislého grafu
Úkol 19 — Negace: Znegujte: ∀ G=(V,E): T je kostra souvislého grafu G ⇒ T obsahuje všechny mosty grafu G
∃ G=(V,E): T je kostra souvislého grafu G ∧ T neobsahuje všechny mosty grafu G (existuje most, který není v kostře)
Kvíz — Počet koster K4: Kolik koster má K4?
Správná odpověď: 16
Podle vzorce t(Kn) = nn-2, tedy t(K4) = 42 = 16.