From 1338bb273fb83cb94e0aeb56782c089b345e0207 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sat, 19 Apr 2008 19:57:40 +0200 Subject: [PATCH] The Minimality Theorem has a nice name. --- PLAN | 1 - adv.tex | 4 ++-- dyn.tex | 4 ++-- mst.tex | 6 +++--- 4 files changed, 7 insertions(+), 8 deletions(-) diff --git a/PLAN b/PLAN index c768f97..3600b29 100644 --- a/PLAN +++ b/PLAN @@ -63,7 +63,6 @@ Spanning trees: - use the notation for contraction by a set - mention bugs in Valeria's verification paper - more references on decision trees -- rename theorem on Minimality by order - introduce Cut rule and Cycle rule earlier - Lemma: deletion of a non-MST edge does not alter the MST diff --git a/adv.tex b/adv.tex index 12c6346..b161b8a 100644 --- a/adv.tex +++ b/adv.tex @@ -558,7 +558,7 @@ needed, saving the actual efficient implementation for later. \para To verify that a~spanning~$T$ is minimum, it is sufficient to check that all -edges outside~$T$ are $T$-heavy (by Theorem \ref{mstthm}). In fact, we will be +edges outside~$T$ are $T$-heavy (by the Minimality Theorem, \ref{mstthm}). In fact, we will be able to find all $T$-light edges efficiently. For each edge $uv\in E\setminus T$, we will find the heaviest edge of the tree path $T[u,v]$ and compare its weight to $w(uv)$. It is therefore sufficient to solve the following problem: @@ -1259,7 +1259,7 @@ spanning tree problem which frequently arise in practice. When the edges are already sorted by their weights, we can use the Kruskal's algorithm to find the MST in time $\O(m\timesalpha(n))$ (Theorem \ref{kruskal}). We however can do better: As the minimality of a~spanning tree depends only on the -order of weights and not on the actual values (Theorem \ref{mstthm}), we can +order of weights and not on the actual values (The Minimality Theorem, \ref{mstthm}), we can renumber the weights to $1, \ldots, m$ and find the MST using the Fredman-Willard algorithm for integer weights. According to Theorem \ref{intmst} it runs in time $\O(m)$ on the Word-RAM. diff --git a/dyn.tex b/dyn.tex index 41a5e2d..a2bb4cc 100644 --- a/dyn.tex +++ b/dyn.tex @@ -68,8 +68,8 @@ therefore also of~$F$), we have to add~$e$ to~$F$. Otherwise, one of the followi Either $e$~is $F$-heavy and so the forest~$F$ is also the MSF of the new graph. Or it is $F$-light and we have to modify~$F$ by exchanging the heaviest edge~$f$ of the path $F[e]$ with~$e$. -Correctness of the former case follows immediately from the Theorem on Minimality by order -(\ref{mstthm}), because any $F'$-light would be also $F$-light, which is impossible as $F$~was +Correctness of the former case follows immediately from the Minimality Theorem (\ref{mstthm}), +because any $F'$-light would be also $F$-light, which is impossible as $F$~was minimum. In the latter case, the edge~$f$ is not contained in~$F'$ because it is the heaviest on the cycle $F[e]+e$ (by the Red lemma, \ref{redlemma}). We can now use the Blue lemma (\ref{bluelemma}) to prove that it should be replaced with~$e$. Consider the tree~$T$ diff --git a/mst.tex b/mst.tex index 820ba51..8d3f18a 100644 --- a/mst.tex +++ b/mst.tex @@ -149,7 +149,7 @@ $w(f)\ge w(e')$ due to the choice of $e'$ and all other edges on~$C$ are lighter than~$e'$ as $e'$ was not $T$-light. \qed -\thmn{Minimality by order}\id{mstthm}% +\thmn{Minimality of spanning trees}\id{mstthm}% A~spanning tree~$T$ is minimum iff there is no $T$-light edge. \proof @@ -214,8 +214,8 @@ their monotone isomorphism. Then $\mst(G_2) = \pi[\mst(G_1)]$. The isomorphism~$\pi$ maps spanning trees onto spanning trees and it preserves the relation of covering. Since it is monotone, it preserves the property of being a light edge (an~edge $e\in E(G_1)$ is $T$-light $\Leftrightarrow$ -the edge $\pi[e]\in E(G_2)$ is~$f[T]$-light). Therefore by Theorem~\ref{mstthm}, $T$ -is the MST of~$G_1$ if and only if $\pi[T]$ is the MST of~$G_2$. +the edge $\pi[e]\in E(G_2)$ is~$f[T]$-light). Therefore by the Minimality Theorem +(\ref{mstthm}), $T$ is the MST of~$G_1$ if and only if $\pi[T]$ is the MST of~$G_2$. \qed %-------------------------------------------------------------------------------- -- 2.39.2