Minimální kostra (MST)
Prerekvizity: [L0.4] Strom, kostra, les, DAG (kostra = strom na všech vrcholech).
Od kostry k nejlevnější kostře
V [L0.4] jsme viděli, že souvislý graf má kostru — a typicky jich má hodně (úplný graf na pouhých 4 vrcholech jich má $4^{2}=16$, obecně $n^{n-2}$). Jakmile mají hrany váhy (weights) $c(e)$, nejsou si kostry rovné: každá má cenu $c(T) = \sum_{e \in T} c(e)$. Minimum spanning tree — MST (minimální kostra) je kostra s nejmenší cenou. Definice ze slidů (03_SPT, slide 6): „In an undirected graph with the weights associated to arcs, find a spanning tree of minimum weight or decide that the graph is not connected.“
Zkus sám: najdeš v grafu nahoře kostru levnější než 15? Jak bys ji hledal, abys nemusel zkoušet všechny?
Jde to mnohem líp — nejlevnější kostra má cenu 9. A hledat ji můžeš hladově (greedy): ber hrany od nejlevnější a přidávej je, pokud nevytvoří kružnici. Přesně to dělá Kruskalův algoritmus — krokuj si ho níže.
Jak se MST počítá: hladově
MST je vzácný případ, kdy hladový postup zaručeně najde optimum. Dva klasické algoritmy:
- Kruskal: seřaď hrany podle váhy vzestupně; přidávej je do kostry, dokud nepřidáš $n-1$ hran; hranu, která by uzavřela kružnici, zahoď.
- Prim: rosti strom z jednoho vrcholu; vždy přidej nejlevnější hranu vedoucí ze stromu ven. (Slidy 03_SPT, slide 17 — domácí úkol: čím se liší Prim pro MST od Dijkstry pro strom nejkratších cest?)
Pro zkoušku nepotřebuješ důkazy správnosti — potřebuješ MST umět rychle spočítat na papíře (Kruskalem) a vědět, že je to polynomiální, „levný“ objekt.
Zkus sám: může mít graf víc různých minimálních koster? A může mít dvě MST s různou cenou?
Různých minimálních koster může být víc — když se váhy opakují (remízy), může Kruskal při stejné váze vybrat různé hrany a obě volby dopadnou stejně dobře. Ale cena MST je vždy jednoznačná: všechny minimální kostry mají z definice tentýž (nejmenší) součet. „MST grafu“ jako číslo $c(\mathrm{MST})$ je tedy dobře definované.
K čemu nám MST bude: dolní mez
V tomhle kurzu MST skoro nikdy není finální odpověď — je to stavební kámen a dolní mez (lower bound). Klíčové pozorování (06_TSP, slide 25): když z libovolného okruhu procházejícího všemi vrcholy odebereš jednu hranu, zbyde kostra. Ta nemůže být levnější než MST. Takže žádný okruh přes všechny vrcholy nemůže být levnější než $c(\mathrm{MST})$ — to je srdce 2-aproximace TSP, kterou rozvineme v [L3.8b] MST jako dolní mez (OPT ≥ c(MST)).
Zkus sám: proč po odebrání jedné hrany z okruhu přes všech $n$ vrcholů zbyde právě kostra?
Okruh přes všechny vrcholy má $n$ hran a je souvislý. Odebráním jedné hrany se souvislost nezruší (zbytek okruhu oba konce pořád spojuje) a zbyde $n-1$ hran — souvislý graf s $n-1$ hranami je podle ekvivalencí z [L0.4] strom na všech vrcholech, tedy kostra.
Key takeaways — L0.5- MST (minimum spanning tree) = kostra minimalizující $\sum_{e \in T} c(e)$; existuje, právě když je graf souvislý.
- Počítá se hladově a polynomiálně: Kruskal (hrany od nejlevnější, kružnice zahazuj) nebo Prim (rosti strom nejlevnější hranou ven).
- Cena $c(\mathrm{MST})$ je jednoznačná, i když minimálních koster může být při remízách vah víc.
- MST je dolní mez: okruh přes všechny vrcholy minus jedna hrana = kostra, tedy $c(\mathrm{MST}) \le \mathrm{OPT}$ — rozvineme u TSP v [L3.8b].
“Minimum Spanning Tree — MST: In an undirected graph with the weights associated to arcs, find a spanning tree of minimum weight or decide that the graph is not connected. … The spanning tree in the middle (SPT from central node) has weight 8 and diameter 4 (the longest path between two nodes) while the spanning tree on the right side (MST) has weight 5 and diameter 5.” For the graph drawn below (four outer nodes in a ring, edges of weight 1; central node $s$ joined to each outer node by an edge of weight 2), find the MST and verify both claimed weights and diameters.
a) Co je v zadání?
Graf „čtverec se středem“: kružnice $v_1 v_2 v_3 v_4$ z hran váhy 1, střed $s$ napojený na každý rohový vrchol hranou váhy 2. Najdi minimální kostru, spočítej její váhu a průměr (délku nejdelší cesty mezi dvojicí vrcholů) a srovnej se stromem nejkratších cest ze středu (SPT = všechny čtyři hrany ze středu).
b) Co k tomu budeme potřebovat?
- Tato lekce — definice MST, Kruskal.
- [L0.4] Strom, kostra, les, DAG — kostra má $n-1$ hran.
c) Jak nad úlohou uvažovat?
Kostra na $n=5$ vrcholech má 4 hrany. Kruskal: kolik hran váhy 1 můžeš vzít, než vznikne kružnice? Kolik hran váhy 2 pak ještě potřebuješ? Pro průměr si výslednou kostru nakresli a najdi nejdelší cestu (váženou).
d) Úplné řešení
Kruskal: hrany váhy 1 jsou čtyři: $v_1v_2, v_2v_3, v_3v_4, v_4v_1$. Vezmu $v_1v_2$, $v_2v_3$, $v_3v_4$; čtvrtá hrana $v_4v_1$ by uzavřela kružnici — zahodím. Zbývá připojit $s$: libovolná hrana $s v_i$ váhy 2, např. $s v_1$. MST $= \{v_1v_2, v_2v_3, v_3v_4, s v_1\}$, váha $1+1+1+2 = \mathbf{5}$ ✓. Průměr: nejdelší cesta je $s \to v_1 \to v_2 \to v_3 \to v_4$ s váhou $2+1+1+1 = \mathbf{5}$ ✓ (remízami může MST vyjít i jinak, váha je vždy 5).
SPT ze středu $= \{s v_1, s v_2, s v_3, s v_4\}$: váha $4 \cdot 2 = \mathbf{8}$ ✓, průměr = cesta $v_i \to s \to v_j$ s váhou $2+2=\mathbf{4}$ ✓. Pointa slidu: strom nejkratších cest a minimální kostra jsou různé objekty — SPT minimalizuje vzdálenosti od kořene (a je dražší), MST minimalizuje celkovou váhu (a má delší cesty).
“2. while deleting one edge in the circuit, we create the tree. Therefore, inequality $\mathrm{OPT}(K_n, c) \ge c(E(T))$ holds”, where $T$ is a minimum weight spanning tree of $K_n$ and $\mathrm{OPT}(K_n,c)$ is the cost of the cheapest circuit visiting all $n$ nodes. Justify this inequality in detail (assume non-negative edge costs $c$).
a) Co je v zadání?
Dokaž, že cena nejlevnějšího okruhu přes všechny vrcholy je aspoň cena MST. (Je to jeden krok důkazu 2-aproximace TSP — tady ho trénujeme samostatně.)
b) Co k tomu budeme potřebovat?
- Tato lekce — MST je nejlevnější ze všech koster.
- [L0.4] Strom, kostra, les, DAG — souvislý graf s $n-1$ hranami je strom.
c) Jak nad úlohou uvažovat?
Vezmi optimální okruh a odeber z něj jednu hranu. Co za objekt ti zbyl (kolik má hran, je souvislý)? Jak se jeho cena srovnává (i) s cenou okruhu a (ii) s cenou MST?
d) Úplné řešení
Nechť $H$ je optimální okruh přes všech $n$ vrcholů, $c(H) = \mathrm{OPT}(K_n, c)$. Odeberu z $H$ libovolnou hranu $e$ a dostanu podgraf $P = H - e$: je souvislý (zbytek okruhu spojuje oba konce $e$), obsahuje všech $n$ vrcholů a má $n-1$ hran — je to tedy kostra (cesta přes všechny vrcholy), viz ekvivalence (c) z [L0.4].
Dvě nerovnosti: $$c(\mathrm{MST}) \;\le\; c(P) \;=\; c(H) - c(e) \;\le\; c(H) = \mathrm{OPT}(K_n,c).$$ První platí, protože MST je nejlevnější kostra a $P$ je nějaká kostra; druhá protože $c(e) \ge 0$. Dohromady $c(E(T)) = c(\mathrm{MST}) \le \mathrm{OPT}(K_n, c)$. $\blacksquare$