From 285cf4909b333868d6f1a35cc3e695c697a58e00 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Thu, 24 Apr 2008 12:57:08 +0200 Subject: [PATCH] Connect K best to the introductory chapters. --- dyn.tex | 3 +++ mst.tex | 3 +++ 2 files changed, 6 insertions(+) diff --git a/dyn.tex b/dyn.tex index e7432fc..7197b22 100644 --- a/dyn.tex +++ b/dyn.tex @@ -957,5 +957,8 @@ to $\O(Km^{1/2})$ and improving Theorem \ref{kbestthm} to $\O(m\timesalpha(m,n) chapter could be modified to bring the complexity of finding the next tree down to polylogarithmic. +\paran{Multiple minimum trees}% +Another nice application of Theorem \ref{kbestthm} is finding all minimum spanning +trees in a~graph that does not have distinct edge weights. \endpart diff --git a/mst.tex b/mst.tex index efc4d63..1cf428e 100644 --- a/mst.tex +++ b/mst.tex @@ -208,6 +208,9 @@ input, we will explicitly state so. In case the weights are not distinct, we can easily break ties by comparing some unique identifiers of edges. According to our characterization of minimum spanning trees, the unique MST of the new graph will still be a~MST of the original graph. +Sometimes, we could be interested in finding all solutions, but as this is an~uncommon +problem, we will postpone it until Section \ref{kbestsect}. For the time being, +we will always assume distinct weights. \obs If all edge weights are distinct and $T$~is an~arbitrary tree, then for every tree~$T$ all edges are -- 2.39.2