— — Minimální kostra grafu

Minimální kostra grafu

Kostra grafu

Kostra souvislého grafu G = (V, E) je libovolný strom T = (V, E′), kde E′ ≤ E.

Poznámka:

Každý souvislý graf má kostru: dokud v G existuje kružnice, odebíráme z G hranu kružnice, dostaneme tak nakonec kostru grafu.

Příklad:

Prasátko. (Na onom grafu se vysvětluje i minimální kostra.)

Graf s ohodnocenými hranami: G = (V, E), w: E → ℝ^{+} .

Problém minimální kostry:

Pro daný souvislý graf G = (V, E), w: E → ℝ^{+} máme nalézt minimální kostru, tj. kostru K = (V, E′) takovou, že její váha w(K) = w(E′) = ∑_{e∈E′} w(e) je minimální.

Kruskulův (hladový) algoritmus

Mějme souvislý G = (V, E), w: E → ℝ^{+} . Předpokládejme, že E = {e_{1}, e_{2}, …, e_{m}}, přičemž

w(e_{1}) ≤ w(e_{2}) ≤ ⋯ ≤ w(e_{m})

1. E_{0} = ∅

2. Pro i = 1, 2, …, m pokládáme

E_{i} = \{ \begin{matrix}E_{i−1} ∪ \{e_{i}\} & pokud (V, E_{i−1} ∪ \{e_{i}\}) nemá kružnici \\ E_{i−1} & jinak \end{matrix}

3. (V, E_{m}) → výstup (minimální kostra)

VĚTA (kostra nalezená algoritmem je minimální):

DŮKAZ:

(V, K) nechť je výsledná kostra. Budiž (V, L) libovolná jiná kostra, pak chceme w(L) ≥ w(K). Indukcí podle \underbrace{d = |KΔL| = |(K \ L) ∪ (L \ K)|}_{mohutnost symetrické diference} :

(d = 0) K = L, platí

(d > 0) Předpokládáme, že tvrzení platí pro všechny menší hodnoty d.

d > 0 ⟹ K ≠ L, |K| = |L| ⟹ ∃ e ∈ L \ K

(V, L \ {e}) pak má dvě komponenty (graf s hranou byl strom). Obrázek. (V, K) kostra ⟹ (V, K ∪ {e}) má (jedinou) kružnici C obsahující e. Exi-

stuje e′ ≠ e ∈ C:

\begin{aligned}|e′ ∩ V_{1}| & = 1 \\ |e′ ∪ V_{2}| & = 1 \end{aligned}

Tvrdíme:

w(e′) ≤ w(e)

(jinak w(e) < w(e′), algoritmus tedy uvažoval e dříve než e′, ovšem pokud ho nezařadil, mohl ho odmítnout jedině kvůli C (to je jediná kružnice v K ∪ e), ale e′ ∈ C nebylo ještě uvažováno).

L′ = (L \ {e}) ∪ {e′}

Tvrdíme, že (V, L′) je kostra. (Viz náš virtuální obrázek. Měli jsme dvě komponenty spojené hranou e, teď je jen spojíme místo toho jinou hranou e′.)

|L′ΔK| < |LΔK|
w(L) ≥ w(L′) ≥^{ind. předp.} w(K)

Q.E.D.

Jarníkův algoritmus na minimální kostru

1. V_{0} := {v}, kde v je libovolný vrchol z V.

2. Pro i = 1, 2, …, n − 1 (n = |V |) nechť e_{i} je hrana minimální váhy vedoucí z V_{i−1} do V \ V_{i−1}. Obrázek. V_{i} = V_{i−1} ∪ e_{i} (přidáme koncový vrchol hrany e_{i}).

3. s trom(V, {e_{1}, …, e_{n−1}}) je výstup (minimální kostra grafu).

Borůvkův algoritmus

Předpokládáme, že libovolné dvě hrany mají různou váhu: w(e) ≠ w(e′) ∀e ≠ e′.

1. Spojíme každý vrchol hranou s nejbližším sousedem: (obrázek).

2. Spojme každou komponentu hranou s nejbližší jinou komponentou: (obrázek). Opakujeme, dokud nedostaneme jednu komponentu — to je výstup.