From f93e96e684a9d4185b3520dbb3052ef48b9d9c3d Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sat, 19 Jan 2008 20:43:09 +0100 Subject: [PATCH] Saving text which will be deleted :) --- mst.tex | 32 ++++++++++++++++++++++++++------ 1 file changed, 26 insertions(+), 6 deletions(-) diff --git a/mst.tex b/mst.tex index 354e0d6..7642ddb 100644 --- a/mst.tex +++ b/mst.tex @@ -459,10 +459,10 @@ use the multigraph version and show that we can easily reduce the multigraph to a simple graph later. (See \thmref{contract} for the exact definitions.) We only need to be able to map edges of the contracted graph to the original -edges, so each edge will carry a unique label $l(e)$ which will be preserved by +edges, so each edge will carry a unique label $\ell(e)$ which will be preserved by contractions. -\lemman{Flattening a multigraph}% +\lemman{Flattening a multigraph}\thmid{flattening}% Let $G$ be a multigraph and $G'$ its subgraph such that all loops have been removed and each bundle of parallel edges replaced by its lightest edge. Then $G'$~has the same MST as~$G$. @@ -484,10 +484,10 @@ modifications. \algo \algin A~graph~$G$ with an edge comparison oracle. \:$T\=\emptyset$. -\:$l(e)\=e$ for all edges~$e$. \cmt{Initialize the labels.} +\:$\ell(e)\=e$ for all edges~$e$. \cmt{Initialize the labels.} \:While $n(G)>1$: \::For each vertex $v_i$ of~$G$, let $e_i$ be the lightest edge incident to~$v_i$. -\::$T\=T\cup \{ l(e_i) \}$. \cmt{Remember labels of all selected edges.} +\::$T\=T\cup \{ \ell(e_i) \}$. \cmt{Remember labels of all selected edges.} \::Contract $G$ along all edges $e_i$, inheriting labels and weights. \::Flatten $G$, removing parallel edges and loops. \algout Minimum spanning tree~$T$. @@ -565,13 +565,33 @@ Graph contractions are a very powerful tool and they can be used in other MST algorithms as well. The following lemma shows the gist: \lemman{Contraction of MST edges} -Let $G$ be a weighted multigraph, $e$~an arbitrary edge of~$\mst(G)$, $G/e$ the multigraph -produced by contracting $G$ along~$e$ and $\pi$ the bijection between edges of~$G-e$, and +Let $G$ be a weighted graph, $e$~an arbitrary edge of~$\mst(G)$, $G/e$ the multigraph +produced by contracting $G$ along~$e$, and $\pi$ the bijection between edges of~$G-e$ and their counterparts in~$G/e$. Then: $$\mst(G) = \pi^{-1}[\mst(G/e)] + e.$$ \proof +% We seem not to need this lemma for multigraphs... +%If there are any loops or parallel edges in~$G$, we can flatten the graph. According to the +%Flattening lemma (\thmref{flattening}), the MST stays the same and if we remove a parallel edge +%or loop~$f$, then $\pi(f)$ would be removed when flattening~$G/e$, so $f$ never participates +%in a MST. +The right-hand side of the equality is a spanning tree of~$G$, let us denote it by~$T$ and +the MST of $G/e$ by~$T'$. If $T$ were not minimum, there would exist a $T$-light edge~$f$ in~$G$. +If the path $T[f]$ covered by~$f$ does not contain~$e$, then $\pi[T[f]]$ is a path covered by~$\pi(f)$ +in~$T'$. Otherwise $\pi(T[f]-e)$ is such a path. In both cases, $f$ is $T'$-light, which should +contradict the minimality of~$T'$, but we need a multigraph version of Theorem \thmref{mstthm} +which we did not prove. + +To avoid it, we consider the flattening~$F$ of~$G/e$ and apply the theorem to it. +According to the Flattening lemma (\thmref{flattening}), $F$~has the same MST as~$G/e$ +and therefore it contains all edges of~$T'$. If $\pi(f)\not\in E(F)$, it +has been removed in favor of some lighter edge~$f'$ and if $\pi(f)$ was +$T$-light, then $f'$ is even so. \qed +\rem +In the previous algorithm, the role of the mapping~$\pi^{-1}$ is played by the edge labels~$\ell$. + \section{Minor-closed graph classes} \section{Using Fibonacci heaps} -- 2.39.2