\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
