From d1065a27b4d63220167c49017153b8f083a7b5d4 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Tue, 21 Nov 2006 21:53:52 +0100 Subject: [PATCH] Zjednoduseni formulace lemmatu. --- 5-mst/5-mst.tex | 11 +++++------ 1 file changed, 5 insertions(+), 6 deletions(-) diff --git a/5-mst/5-mst.tex b/5-mst/5-mst.tex index 8dd362f..6ef95c8 100644 --- a/5-mst/5-mst.tex +++ b/5-mst/5-mst.tex @@ -65,8 +65,8 @@ Po~kone \qed \s{Monotónní lemma o~swapování:} -Jsou-li $T$ a $T'$ kostry bez lehkých hran, pak lze od~$T$ k~$T'$ pøejít posloupností -swapù, pøi které váha kostry neklesá. (Od~$T'$ k~$T$ tedy také, tak¾e $w(T)=w(T')$.) +Je-li $T$ kostra, k~ní¾ neexistují ¾ádné lehké hrany, a~$T'$ libovolná kostra, +pak lze od~$T$ k~$T'$ pøejít posloupností swapù, pøi které váha kostry neklesá. \s{Dùkaz:} Podobnì jako u~pøedchozího lemmatu budeme postupovat indukcí podle $\vert T \symdiff T' \vert$. @@ -75,9 +75,7 @@ $\check{T}:=\(T,e,e')$ b jeliko¾ $e'$ nemù¾e být lehká vzhledem k~$T$, tak¾e speciálnì $w(e')\ge w(e)$. Aby mohla indukce pokraèovat, potøebujeme je¹tì dokázat, ¾e ani k~nové kostøe neexistují -lehké hrany v~$T'\setminus \check{T}$.\foot{Ony nebudou lehké ani ostatní hrany, ale to -pro indukci nepotøebujeme a museli bychom to dokazovat pracnìji.} K~tomu nám pomù¾e -zvolit si ze~v¹ech mo¾ných hran~$e'$ tu s~nejmen¹í vahou. +lehké hrany v~$T'\setminus \check{T}$. K~tomu nám pomù¾e zvolit si ze~v¹ech mo¾ných hran~$e'$ tu s~nejmen¹í vahou. Uva¾me nyní hranu~$f\in T'\setminus \check{T}$. Cesta $\check{T}[f]$ pokrytá touto hranou v~nové kostøe je buïto pùvodní $T[f]$ (to pokud $e\not\in T[f]$) nebo $T[f] \symdiff C$, kde $C$ je kru¾nice $T[e']+e$. První pøípad je triviální, @@ -97,7 +95,8 @@ Kostra $T' := \(T,e,e')$ je leh \:$\Leftarrow$ Pokud k~$T$ neexistuje lehká hrana, je $T$ minimální. Uva¾me minimální kostru $T_{min}$. Podle právì dokázané implikace k~ní neexistují lehké hrany, -tak¾e mù¾eme pou¾ít monotónní swapovací lemma na~$T$ a $T_{min}$ a z~nìj plyne $w(T)=w(T_{min})$. +tak¾e mù¾eme pou¾ít monotónní swapovací lemma na~$T$ a $T_{min}$ a z~nìj plyne $w(T)\le w(T_{min})$, +a~tedy $w(T)=w(T_{min})$. \endlist \qed -- 2.39.2