01ZTGA:Kapitola1 5

Z WikiSkripta FJFI ČVUT v Praze
Verze z 15. 1. 2012, 12:51, kterou vytvořil Karel.brinda (diskuse | příspěvky)

(rozdíl) ← Starší verze | zobrazit aktuální verzi (rozdíl) | Novější verze → (rozdíl)
Přejít na: navigace, hledání
PDF [ znovu generovat, výstup z překladu ] Kompletní WikiSkriptum včetně všech podkapitol.
PDF Této kapitoly [ znovu generovat, výstup z překladu ] Přeložení pouze této kaptioly.
ZIPKompletní zdrojový kód včetně obrázků.

Součásti dokumentu 01ZTGA

součástakcepopisposlední editacesoubor
Hlavní dokument editovatHlavní stránka dokumentu 01ZTGAKarel.brinda 15. 1. 201223:45
Řídící stránka editovatDefiniční stránka dokumentu a vložených obrázkůAdmin 7. 9. 201513:51
Header editovatHlavičkový souborKarel.brinda 15. 1. 201212:34 header.tex
Kapitola0 editovatÚvodKarel.brinda 15. 1. 201212:36 cast0.tex
Kapitola1_1 editovatZákladní pojmyKarel.brinda 15. 1. 201212:46 cast1_kapitola1.tex
Kapitola1_2 editovatSouvislostKarel.brinda 15. 1. 201212:49 cast1_kapitola2.tex
Kapitola1_3 editovatBipartitní grafyKarel.brinda 15. 1. 201212:50 cast1_kapitola3.tex
Kapitola1_4 editovatStromyKubuondr 5. 1. 201909:06 cast1_kapitola4.tex
Kapitola1_5 editovatHledání minimální kostry grafuKarel.brinda 15. 1. 201212:51 cast1_kapitola5.tex
Kapitola1_6 editovatJednotažkyKarel.brinda 15. 1. 201212:53 cast1_kapitola6.tex
Kapitola1_7 editovatHamiltonovské kružnice a grafyKarel.brinda 15. 1. 201213:34 cast1_kapitola7.tex
Kapitola1_8 editovatPárování v grafechKarel.brinda 15. 1. 201213:40 cast1_kapitola8.tex
Kapitola1_9 editovatToky v sítíchKarel.brinda 15. 1. 201213:44 cast1_kapitola9.tex
Kapitola1_10 editovatHranové obarvení grafuKarel.brinda 15. 1. 201213:48 cast1_kapitola10.tex
Kapitola1_11 editovatVrcholové obarvení grafuKarel.brinda 15. 1. 201213:52 cast1_kapitola11.tex
Kapitola1_12 editovatPlanární grafyKarel.brinda 15. 1. 201213:56 cast1_kapitola12.tex
Kapitola1_13 editovatVlastní čísla adjacenční matice grafuKarel.brinda 15. 1. 201213:57 cast1_kapitola13.tex
Kapitola2_1 editovatBrouwerova věta o pevném boděKarel.brinda 15. 1. 201214:11 cast2_kapitola1.tex
Kapitola2_2 editovatPravděpodobnostní důkazy v teorii grafůKarel.brinda 15. 1. 201214:12 cast2_kapitola2.tex
Kapitola2_3 editovatExtremální teorie grafůKarel.brinda 15. 1. 201214:16 cast2_kapitola3.tex
Kapitola2_4 editovatRamseyovská číslaKarel.brinda 15. 1. 201214:18 cast2_kapitola4.tex
Kapitola3_1 editovatObyčejné mocninné řadyKarel.brinda 15. 1. 201214:22 cast3_kapitola1.tex
Kapitola3_2 editovatExponenciální generující funkceKarel.brinda 15. 1. 201214:22 cast3_kapitola2.tex

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}

Citováno z „https://wikiskripta.fjfi.cvut.cz/wiki/index.php?title=01ZTGA:Kapitola1_5&oldid=4511“