\input /home/pasky/school/fastex/lib.tex

\subchapter{Minimální kostra grafu}{

	\scpart{Kostra grafu}{
		Kostra souvislého grafu $G=(V,E)$ je libovolný strom
		$T = (V,E')$, kde $E' \le E$.

		\note{
			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.
		}

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

	\shortdef{Graf s ohodnocenými hranami}{$G = (V,E), w\colon E \to \real^+$.}

	\scpart{Problém minimální kostry:}{
		Pro daný souvislý graf $G = (V,E), w\colon E \to \real^+$ máme
		nalézt {\bf minimální kostru}, tj. kostru $K = (V,E')$
		takovou, že její váha $w(K) = w(E') = \sum_{e \in E'} w(e)$
		je minimální.

		\scpart{Kruskulův (hladový) algoritmus}{
			Mějme souvislý $G=(V,E), w\colon E \to \real^+$.
			Předpokládejme, že $E = \{ e_1, e_2, \ldots, e_m \}$,
			přičemž
				$$ w(e_1) \le w(e_2) \le \cdots \le w(e_m) $$

			\list{
				\tlistItem{$E_0 = \emptyset$}
				\tlistItem{Pro $i = 1,2,\ldots,m$ pokládáme
					$$ E_i = \cases{E_{i-1} \cup \{e_i\}&pokud $(V,E_{i-1}\cup\{e_i\})$ nemá kružnici\cr
					                E_{i-1}             &jinak} $$
				}
				\tlistItem{$(V,E_m) \to $ výstup (minimální kostra)}
			}

			\theorem{}{kostra nalezená algoritmem je minimální}{
			\proof{
				$(V,K)$ nechť je výsledná kostra. Budiž $(V,L)$ libovolná
				jiná kostra, pak chceme $w(L) \ge w(K)$.
				Indukcí podle $\undernote{d = |K \Delta L| = |(K \setminus L) \cup (L \setminus K)|}
				{\textbox{mohutnost {\bf symetrické diference}}}$:

				\list{
					\namedListItem{$d=0$}{ $K=L$, platí }
					\namedListItem{$d>0$}{
						Předpokládáme, že tvrzení platí
						pro všechny menší hodnoty $d$.

						$$ d > 0 \Longrightarrow K \ne L,\ |K| = |L|
							\Longrightarrow \existss e \in L \setminus K $$

						$(V,L\setminus\{e\})$ pak má dvě komponenty
						(graf s hranou byl strom).
						Obrázek.

						$(V,K)$ kostra $\Longrightarrow$
						$(V,K\cup\{e\})$ má (jedinou) kružnici $C$ obsahující $e$.
						\hyphenation{Exi-stu-je} Existuje $e' \ne e \in C$:
							$$ \eqalign{|e'\cap V_1|&=1\cr
							            |e'\cup V_2|&=1} $$

						Tvrdíme:
							$$ w(e') \le 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 \cup e$), ale $e' \in C$ nebylo
						ještě uvažováno).

						$$ L' = (L \setminus \{e\}) \cup \{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' \Delta K| < |L \Delta K| $$
						$$ w(L) \ge w(L') \becauseof{ind. předp.}{\ge} w(K) $$
					}
				}

				\qed
			}
			}
		}


		\scpart{Jarníkův algoritmus na minimální kostru}{
			\list{
				\tlistItem{$V_0 := \{v\}$, kde $v$ je libovolný vrchol z $V$.}
				\tlistItem{
					Pro $i=1,2,\ldots,n-1$ ($n = |V|$)
					nechť $e_i$ je hrana minimální váhy
					vedoucí z~$V_{i-1}$ do $V\setminus V_{i-1}$.

					Obrázek.

					$V_i = V_{i-1} \cup e_i$ (přidáme koncový vrchol hrany $e_i$).
				}
				\tlistItem{
					${\mathop strom}(V, \{e_1,\ldots,e_{n-1}\})$ je výstup (minimální kostra grafu).
				}
			}
		}


		\scpart{Borůvkův algoritmus}{
			Předpokládáme, že libovolné dvě hrany mají různou váhu: $w(e) \ne w(e')\ \forall e \ne e'$.

			\list{
				\tlistItem{
					Spojíme každý vrchol hranou s nejbližším sousedem: (obrázek).
				}

				\tlistItem{
					Spojme každou komponentu hranou s nejbližší jinou komponentou: (obrázek).

					Opakujeme, dokud nedostaneme jednu komponentu --- to je výstup.
				}
			}
		}
	}
}

\bend