From 6f68c3cceeba460fe5bb689bbdecfe111b992db0 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sat, 19 Apr 2008 23:47:59 +0200 Subject: [PATCH] Added a section on the restrictions of graphs and weights. --- PLAN | 7 ++----- adv.tex | 8 ++++---- dyn.tex | 5 +++-- mst.tex | 52 ++++++++++++++++++++++++++++++++++++++++++---------- 4 files changed, 51 insertions(+), 21 deletions(-) diff --git a/PLAN b/PLAN index 3600b29..643251f 100644 --- a/PLAN +++ b/PLAN @@ -52,19 +52,17 @@ Preface: - move TOC to the beginning of the book - mention notation +- cite GA booklet Spanning trees: - cite Eisner's tutorial \cite{eisner:tutorial} -- move the remark on disconnected graphs? separate section? -- mention graphs with non-unique weights? also in the separate section? - Some algorithms (most notably Fredman-Tarjan) do not need flattening -- citation of mixed Boruvka-Jarnik - use the notation for contraction by a set - mention bugs in Valeria's verification paper - more references on decision trees -- introduce Cut rule and Cycle rule earlier - Lemma: deletion of a non-MST edge does not alter the MST +- mention that there are only a few algorithms based on the Red rule Related: - practical considerations: katriel:cycle, moret:practice (mention pairing heaps) @@ -101,6 +99,5 @@ Typography: Global: -- Intro: cite GA booklet - each chapter should make clear in which model we work - clean up bibliography diff --git a/adv.tex b/adv.tex index b161b8a..f9e0938 100644 --- a/adv.tex +++ b/adv.tex @@ -208,9 +208,9 @@ Hence $n_i\le 3/4\cdot n_{i-1}$ and therefore $n_i\le n\cdot (3/4)^i$ and the algorithm terminates after $\O(\log n)$ iterations. Each selected edge belongs to $\mst(G)$, because it is the lightest edge of -the trivial cut $\delta(v)$ (see the Blue Rule in \ref{rbma}). +the trivial cut $\delta(v)$ (see the Blue rule, Lemma \ref{rbma}). The steps 6 and~7 therefore correspond to the operation -described by the Lemma on contraction of MST edges (\ref{contlemma}) and when +described by the Contraction Lemma (\ref{contlemma}) and when the algorithm stops, $T$~is indeed the minimum spanning tree. It remains to analyse the time complexity of the algorithm. Since $G_i\in{\cal C}$, we have @@ -373,7 +373,7 @@ show a~faster integer algorithm soon.) As we already noted, the improved Jarn\'\i{}k's algorithm runs in linear time for sufficiently dense graphs. In some cases, it is useful to combine it with another MST algorithm, which identifies a~part of the MST edges and contracts -the graph to increase its density. For example, we can perform several Bor\v{u}vka +the graph to increase its density. For example, we can perform several Bor\o{u}vka steps and find the rest of the MST by the Active Edge Jarn\'\i{}k's algorithm. \algn{Mixed Bor\o{u}vka-Jarn\'\i{}k} @@ -1071,7 +1071,7 @@ subgraph, only a~small expected number of edges remains. Selecting a~subgraph at random will unavoidably produce disconnected subgraphs at occassion, so we will drop the implicit assumption that all graphs are connected for this section and we will always search for the minimum spanning forest. -As we already noted (Remark \ref{disconn}), with a~little bit of care our +As we already noted (\ref{disconn}), with a~little bit of care our algorithms and theorems keep working. Since we need the MST verification algorithm for finding the $T$-heavy edges, diff --git a/dyn.tex b/dyn.tex index 31beea1..f22d5d0 100644 --- a/dyn.tex +++ b/dyn.tex @@ -676,8 +676,9 @@ but adapted to use the better results on dynamic connectivity we have at hand. \paran{Dynamic MSF with limited edge weights}% Let us assume for a~while that our graph has edges of only two different weights (let us say -1~and~2). We will forget our rule that all edge weights are distinct for a~moment and we recall that -the basic structural properties of the MST's from Section \ref{mstbasics} still hold. +1~and~2). We will forget our rule that all edge weights are distinct for a~moment and we recall +the observation in \ref{multiweight} that the basic structural properties of +the MST's from Section \ref{mstbasics} still hold. We split the graph~$G$ to two subgraphs~$G_1$ and~$G_2$ according to the edge weights. We use one instance~$\C_1$ of the dynamic connectivity algorithm maintaining diff --git a/mst.tex b/mst.tex index 449d890..d5a6911 100644 --- a/mst.tex +++ b/mst.tex @@ -369,7 +369,7 @@ contains two or more original trees. \cor The algorithm stops in $\O(\log n)$ iterations. -\lemma +\lemma\id{borcorr}% Bor\o{u}vka's algorithm outputs the MST of the input graph. \proof @@ -571,13 +571,9 @@ Then $G'$~has the same MST as~$G$. Every spanning tree of~$G'$ is a spanning tree of~$G$. In the other direction: Loops can be never contained in a spanning tree. If there is a spanning tree~$T$ containing a~removed edge~$e$ parallel to an edge~$e'\in G'$, exchaning $e'$ -for~$e$ makes~$T$ lighter. \qed - -\rem Removal of the heavier of a pair of parallel edges can be also viewed -as an application of the Red rule on a two-edge cycle. And indeed it is, the -Red-Blue procedure works on multigraphs as well as on simple graphs and all the -classical algorithms also do. We would only have to be more careful in the -formulations and proofs, which we preferred to avoid. +for~$e$ makes~$T$ lighter. (This is indeed the multigraph version of the Red +lemma applied to a~two-edge cycle, as we will see in \ref{multimst}.) +\qed \algn{Contractive version of Bor\o{u}vka's algorithm}\id{contbor} \algo @@ -686,7 +682,7 @@ In the previous algorithm, the role of the mapping~$\pi^{-1}$ is of course playe Finally, we will show a family of graphs where the $\O(m\log n)$ bound on time complexity is tight. The graphs do not have unique weights, but they are constructed in a way that the algorithm never compares two edges with the same weight. Therefore, when two such -graphs are monotonely isomorphic (see~\ref{mstiso}), the algorithm processes them in the same way. +graphs are monotonically isomorphic (see~\ref{mstiso}), the algorithm processes them in the same way. \defn A~\df{distractor of order~$k$,} denoted by~$D_k$, is a path on $n=2^k$~vertices $v_1,\ldots,v_n$ @@ -740,7 +736,16 @@ to finish on the remaining complete graph. Each iteration runs on a graph with $ edges as every $H_{a,k}$ contains a complete graph on~$a$ vertices. \qed -\remn{Disconnected graphs}\id{disconn}% +%-------------------------------------------------------------------------------- + +\section{Lifting restrictions} + +In order to have a~simple and neat theory, we have introduced several restrictions +on the graphs in which we search for the MST. As in some rare cases we are going to +meet graphs that do not fit into this simplified world, let us quickly examine what +happens when the restrictions are lifted. + +\paran{Disconnected graphs}\id{disconn}% The basic properties of minimum spanning trees and the algorithms presented in this chapter apply to minimum spanning forests of disconnected graphs, too. The proofs of our theorems and the steps of our algorithms are based on adjacency @@ -755,4 +760,31 @@ for $F$-light). Edges connecting two different trees are always considered $F$-light. Again, a~spanning forest~$F$ is minimum iff there are no $F$-light edges. +\paran{Multigraphs}\id{multimst}% +All theorems and algorithms from this chapter work for multigraphs as well, +only the notation sometimes gets crabbed, which we preferred to avoid. The Minimality +theorem and the Blue rule stay unchanged. The Red rule is naturally extended to +self-loops (which are never in the MST) and two-edge cycles (where the heavier +edge can be dropped) as already suggested in the Flattening lemma (\ref{flattening}). + +\paran{Multiple edges of the same weight}\id{multiweight}% +In case when the edge weights are not distinct, the characterization of minimum +spanning trees using light edges is still correct, but the MST is no longer unique +(as already mentioned, there can be as much as~$n^{n-2}$ MST's). + +In the Red-Blue procedure, we have to avoid being too zealous. The Blue lemma cannot +guarantee that when a~cut contains multiple edges of the minimum weight, all of them +are in the MST. It will however tell that if we pick one of these edges, an~arbitrary +MST can be modified to another MST that contains this edge. Therefore the Blue rule +will change to ``Pick a~cut~$C$ such that it does not contain any blue edge and color +one of its lightest edges blue.'' The Red lemma and the Red rule can be handled +in a~similar manner. The modified algorithm will be then guaranteed to find one of +the possible MST's. + +The Kruskal's and Jarn\'\i{}k's algorithms keep working. This is however not the case of the +Bor\o{u}vka's algorithm, whose proof of correctness in Lemma \ref{borcorr} explicitly referred to +distinct weights and indeed, if they are not distinct, the algorithm will occasionally produce +cycles. To avoid the cycles, the ties in edge weight comparisons have to be broken in a~systematic +way. The same applies to the contractive version of this algorithm. + \endpart -- 2.39.2