01ZTGA:Kapitola1 5: Porovnání verzí
Z WikiSkripta FJFI ČVUT v Praze
(Založena nová stránka: %\wikiskriptum{01ZTGA}) |
|||
Řádka 1: | Řádka 1: | ||
%\wikiskriptum{01ZTGA} | %\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} |
Aktuální verze z 15. 1. 2012, 12:51
[ 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. |
ZIP | Kompletní zdrojový kód včetně obrázků. |
Součásti dokumentu 01ZTGA
součást | akce | popis | poslední editace | soubor | |||
---|---|---|---|---|---|---|---|
Hlavní dokument | editovat | Hlavní stránka dokumentu 01ZTGA | Karel.brinda | 15. 1. 2012 | 23:45 | ||
Řídící stránka | editovat | Definiční stránka dokumentu a vložených obrázků | Admin | 7. 9. 2015 | 13:51 | ||
Header | editovat | Hlavičkový soubor | Karel.brinda | 15. 1. 2012 | 12:34 | header.tex | |
Kapitola0 | editovat | Úvod | Karel.brinda | 15. 1. 2012 | 12:36 | cast0.tex | |
Kapitola1_1 | editovat | Základní pojmy | Karel.brinda | 15. 1. 2012 | 12:46 | cast1_kapitola1.tex | |
Kapitola1_2 | editovat | Souvislost | Karel.brinda | 15. 1. 2012 | 12:49 | cast1_kapitola2.tex | |
Kapitola1_3 | editovat | Bipartitní grafy | Karel.brinda | 15. 1. 2012 | 12:50 | cast1_kapitola3.tex | |
Kapitola1_4 | editovat | Stromy | Kubuondr | 5. 1. 2019 | 09:06 | cast1_kapitola4.tex | |
Kapitola1_5 | editovat | Hledání minimální kostry grafu | Karel.brinda | 15. 1. 2012 | 12:51 | cast1_kapitola5.tex | |
Kapitola1_6 | editovat | Jednotažky | Karel.brinda | 15. 1. 2012 | 12:53 | cast1_kapitola6.tex | |
Kapitola1_7 | editovat | Hamiltonovské kružnice a grafy | Karel.brinda | 15. 1. 2012 | 13:34 | cast1_kapitola7.tex | |
Kapitola1_8 | editovat | Párování v grafech | Karel.brinda | 15. 1. 2012 | 13:40 | cast1_kapitola8.tex | |
Kapitola1_9 | editovat | Toky v sítích | Karel.brinda | 15. 1. 2012 | 13:44 | cast1_kapitola9.tex | |
Kapitola1_10 | editovat | Hranové obarvení grafu | Karel.brinda | 15. 1. 2012 | 13:48 | cast1_kapitola10.tex | |
Kapitola1_11 | editovat | Vrcholové obarvení grafu | Karel.brinda | 15. 1. 2012 | 13:52 | cast1_kapitola11.tex | |
Kapitola1_12 | editovat | Planární grafy | Karel.brinda | 15. 1. 2012 | 13:56 | cast1_kapitola12.tex | |
Kapitola1_13 | editovat | Vlastní čísla adjacenční matice grafu | Karel.brinda | 15. 1. 2012 | 13:57 | cast1_kapitola13.tex | |
Kapitola2_1 | editovat | Brouwerova věta o pevném bodě | Karel.brinda | 15. 1. 2012 | 14:11 | cast2_kapitola1.tex | |
Kapitola2_2 | editovat | Pravděpodobnostní důkazy v teorii grafů | Karel.brinda | 15. 1. 2012 | 14:12 | cast2_kapitola2.tex | |
Kapitola2_3 | editovat | Extremální teorie grafů | Karel.brinda | 15. 1. 2012 | 14:16 | cast2_kapitola3.tex | |
Kapitola2_4 | editovat | Ramseyovská čísla | Karel.brinda | 15. 1. 2012 | 14:18 | cast2_kapitola4.tex | |
Kapitola3_1 | editovat | Obyčejné mocninné řady | Karel.brinda | 15. 1. 2012 | 14:22 | cast3_kapitola1.tex | |
Kapitola3_2 | editovat | Exponenciální generující funkce | Karel.brinda | 15. 1. 2012 | 14: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}