From 67d9f01846a625597244ba2474253ebe9fee1ce4 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sat, 19 Apr 2008 20:01:10 +0200 Subject: [PATCH] More wordsmithing. --- mst.tex | 15 +++++++-------- 1 file changed, 7 insertions(+), 8 deletions(-) diff --git a/mst.tex b/mst.tex index 8d3f18a..445b6ce 100644 --- a/mst.tex +++ b/mst.tex @@ -168,7 +168,7 @@ minimum spanning trees according to the Cayley's formula \cite{cayley:trees}). However, as the following theorem shows, this is possible only if the weight function is not injective. -\thmn{MST uniqueness}% +\thmn{Uniqueness of MST}% If all edge weights are distinct, then the minimum spanning tree is unique. \proof @@ -181,6 +181,10 @@ we know that $w(T_1)=w(T_2)$, so the exchange sequence must be empty and indeed $T_1$ and $T_2$ must be identical. \qed +\nota\id{mstnota}% +When $G$ is a graph with distinct edge weights, we will use $\mst(G)$ to denote +its unique minimum spanning tree. + \rem\id{edgeoracle}% To simplify the description of MST algorithms, we will expect that the weights of all edges are distinct and that instead of numeric weights (usually accompanied @@ -192,13 +196,8 @@ minimum spanning trees, the unique MST of the new graph will still be a MST of t original graph. In the few cases where we need a more concrete input, we will explicitly state so. -\nota\id{mstnota}% -When $G$ is a graph with distinct edge weights, we will use $\mst(G)$ to denote -its unique minimum spanning tree. - Another useful consequence is that whenever two graphs are isomorphic and the -isomorphism preserves weight order, the isomorphism applies to their MST's -as well: +isomorphism preserves the relative order of weights, the isomorphism applies to their MST's as well: \defn A~\df{monotone isomorphism} of two weighted graphs $G_1=(V_1,E_1,w_1)$ and @@ -207,7 +206,7 @@ for each $u,v\in V_1: uv\in E_1 \Leftrightarrow \pi(u)\pi(v)\in E_2$ and for each $e,f\in E_1: w_1(e)