Součásti dokumentu 01ZTGA
Zdrojový kód
%\wikiskriptum{01ZTGA}
\section{Hledání minimální kostry grafu}
Nechť je dán souvislý graf $G=(V,E)$ a zobrazení $c:E\mapsto(0,+\infty)$,
které přiřazuje hranám jejich \emph{cenu}. Úkolem je najít takovou
podmnožinu $\tilde{E}\subset E$, že graf $\tilde{G}=(V,\tilde{E}$)
je souvislý a přitom cena \[
c\tilde{(E)}:=\sum_{e\in\tilde{E}}c(e)\]
je minimální. Této úloze říkáme úloha na nalezení minimální kostry
grafu.
\begin{obs*}
$\tilde{G}$ bude strom.
\end{obs*}
\begin{proof}
Pokud $\tilde{G}$ není strom, pak v $\tilde{G}$ je kružnice. Je
tedy možné ubrat hranu, aniž se poruší souvislost grafu, a cena $c(\tilde{E})$
se přitom sníží.
\end{proof}
Pro hledání minimální kostry v grafu je možno použít následující algoritmus,
který je příkladem tzv. hladového (greedy) algoritmu.
\begin{algorithm}
\textbf{\emph{(Kruskalův algoritmus konstrukce minimální kostry)}}
\begin{enumerate}
\item Uspořádej hrany z $E$ podle jejich ceny od nejlevnější k nejdražší.
Buď $T$ množina hran, inicializovaná na $T:=\emptyset$.
\item Obsahuje-li $T$ hrany $f_{1},...,f_{i}$, vyber nejlevnější hranu
$f_{i+1}$ takovou, že graf $G_{i+1}=(V,T\cup\{ f_{i+1}\})$ neobsahuje
kružnici, a zařaď ji do $T$. Tento krok opakuj, dokud to jde.
\end{enumerate}
\end{algorithm}
Je zřejmé, že v okamžiku ukončení bude $\tilde{G}=(V,T)$ souvislý
a bude to tedy strom. Druhý krok algoritmu se bude opakovat právě
$(n-1)$-krát.
\begin{thm}
Kruskalův algoritmus konstruuje strom s minimální cenou.
\end{thm}
\begin{proof}
Označme $T_{Kr}$ množinu $n-1$ hran dodaných Kruskalovým algoritmem.
Definujme množinu\[
\mathcal{T}=\left\{ \left.T\subset E\right|\textrm{graf }(V,T)\textrm{ je souvislý a }c(T)\textrm{ je minimální }\right\} ,\]
tj. jako množinu všech vhodných výběrů $n-1$ hran, na nichž se nabývá
minima ceny. Důkaz provedeme sporem: předpokládejme tedy, že $T_{Kr}\notin\mathcal{T}$.
Potom lze korektně definovat zobrazení $g:\mathcal{T}\mapsto\{1,2,...,n-1\}$
vztahem\[
g(T)=\min\left\{ \left.i\right|f_{i}\notin T_{Kr}\right\} .\]
Nechť $\tilde{T}\in\mathcal{T}$ je taková množina hran, že $k:=g(\tilde{T})=\max_{T\in\mathcal{T}}g(T)$.
Přidáme-li hranu $f_{k}$ do $\tilde{T}$, vznikne množina $n$ hran,
a tedy graf $(V,\tilde{T})$ obsahuje kružnici. V ní musí ležet nějaká
hrana $e\notin T_{Kr}$, protože jinak by graf $(V,T_{Kr})$ nemohl
být strom. Sestrojme novou množinu vrcholů\[
\tilde{\tilde{T}}=\tilde{T}\cup\{ f_{k}\}\backslash\{ e\},\]
tj. vyjměme hranu $e$ ze zmiňované kružnice. Potom graf $(V,\tilde{\tilde{T}})$
zůstává souvislý, navíc $\#\tilde{\tilde{T}}=n-1$, a je to tedy strom.
Pro cenu platí\[
c(\tilde{\tilde{T}})=c(\tilde{T})+c(f_{k})-c(e).\]
Abychom zjistili, jak vysoká je cena $\tilde{\tilde{T}}$ v porovnání
s cenou $\tilde{T}$, uvažujme takto: V $k$-tém kroku se Kruskalův
algoritmus rozhodl pro hranu $f_{k}$ a nikoli pro hranu $e$, přičemž
se pro $e$ rozhodnout mohl, protože hrany$\{ f_{1},...,f_{k-1},e\}\subset\tilde{T}$
a tyto hrany tedy netvoří kružnici. Důvodem, proč se algoritmus rozhodl
pro $f_{k}$, musí tedy být $c(f_{k})\leq c(e)$. Z toho plyne, že
také\[
c(\tilde{\tilde{T}})\leq c(\tilde{T}),\]
ale protože už $c(\tilde{T})$ byla minimální, musí zde platit rovnost.
Každopádně $\tilde{\tilde{T}}\in\mathcal{T}$. Ovšem $\tilde{\tilde{T}}$
obsahuje i hranu $f_{k}$, takže $g(\tilde{\tilde{T}})>k$, což je
spor s volbou $k$.
\end{proof}
