Skip to main content\( \newcommand{\identity}{\mathrm{id}}
\newcommand{\notdivide}{{\not{\mid}}}
\newcommand{\notsubset}{\not\subset}
\newcommand{\lcm}{\operatorname{lcm}}
\newcommand{\gf}{\operatorname{GF}}
\newcommand{\inn}{\operatorname{Inn}}
\newcommand{\aut}{\operatorname{Aut}}
\newcommand{\Hom}{\operatorname{Hom}}
\newcommand{\cis}{\operatorname{cis}}
\newcommand{\chr}{\operatorname{char}}
\newcommand{\Null}{\operatorname{Null}}
\def\Z{\mathbb Z}
\def\R{\mathbb R}
\def\Q{\mathbb Q}
\def\N{\mathbb N}
\def\C{\mathbb C}
\def\W{\mathbb W}
\def\ba{{\mathbf{a}}}
\def\bb{\mathbf{b}}
\def\bh{{\mathbf{h}}}
\def\bu{{\mathbf{u}}}
\def\bv{{\mathbf{v}}}
\def\bw{{\mathbf{w}}}
\def\bx{{\mathbf{x}}}
\def\by{\mathbf{y}}
\def\bone{{\mathbf{1}}}
\def\bzero{\mathbf{0}}
\def\var{{\mbox{var}}}
\def\P{{\mathbb{P}}}
\def\E{{\mathbb{E}}}
\def\cA{{\mathcal{A}}}
\def\cB{{\mathcal{B}}}
\def\cC{{\mathcal{C}}}
\def\cP{\mathcal P}
\def\cN{\mathcal N}
\def\cE{\mathcal E}
\def\cO{\mathcal O}
\def\cF{\mathcal F}
\def\cX{\mathcal X}
\def\nimsum{\, \oplus \,}
\def\mex{{\mathrm{mex}}}
\newcommand{\pile}[1]{\bullet{#1}}
\def\g{g}
\def\kin{k^{\mathrm{in}}}
\def\kout{k^{\mathrm{out}}}
\newcommand{\indeg}[1]{k^{\mathrm{in}}_{#1}}
\newcommand{\outdeg}[1]{k^{\mathrm{out}}_{#1}}
\tikzset{->-/.style={decoration={
markings,
mark=at position .5 with {\arrow{latex}}},postaction={decorate}}}
\newcommand{\nimbleboard}[1]{
\begin{scope}[shift={(.25, .4)}]
\draw (0,-.3) -- (#1,-.3) -- (#1+.45, .7) -- (#1+.45, 1);
\draw (0,0) -- (#1,0);
\draw (.45,1) -- (#1+.45,1);
\foreach \i in {0, ..., #1} {
\draw (\i, -.3) -- (\i, 0) -- (\i+.45,1);
}
\foreach \i in {1, ..., #1} {
\node[style={font=\sffamily\scriptsize}] at (\i - .5, -.15) {\i};
}
\end{scope}
}
\newcommand{\coin}[1]{
\begin{scope}[shift={#1}]
\draw[color=white, fill=white] (-.4, 0) -- (-.4, -.1) -- (.4,-.1) -- (.4,0) -- cycle;
\draw[thick, fill=white] (0,0) ellipse (0.4 and 0.10);
\draw[thick, fill=white] (.4,-.1) arc (0:-180:0.4 and 0.10);
\draw[thick] (0.4,0) -- (0.4, -.1);
\draw[thick] (-0.4,0) -- (-0.4, -.1);
\end{scope}
}
\newcommand{\bean}[2]{
\begin{scope}[shift={#1}, rotate={#2}]
\draw [very thick, fill=gray!50] plot [smooth cycle] coordinates {(-.2,0) (-.175, .07) (-.1,.1) (0,.075) (.1,.1) (.175, .07) (.2,0) (.15, -.07) (0,-.1) (-.15, -.07)};
\end{scope}
}
\newcommand{\heap}[2]{
\begin{scope}[shift={#1}]
\draw[very thick] (0,0) circle ({#2});
\end{scope}
}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\)
Chapter 28 Minimum Spanning Trees
Exercises Practice Problems
1. Prim's Algorithm.
Prim's Algorithm "grows a minimum edge into a MST." Given weighted graph \(G=(V,E)\text{:}\)
Initialize \(T\) to be a vertex \(v\)
-
At each step, grow the tree:
Stop when you can't add more edges.
Use Prim's Algorithm to find the MST of the following weighted graph.
Solution.
2. Kruskal's Algorithm.
Kruskal's Algorithm grows a minimum forest until it is a MST. Given weighted graph \(G=(V,E)\text{:}\)
Initialize \(T\) to contain all the vertices of \(G\text{,}\) but no edges.
-
At each step, grow the forest:
Stop when you can't add more edges.
Solution.
3. MST Examples.
Give an example of a weighted graph on 6 vertices that \(\ldots\)
has a unique minimum spanning tree. Solution.
has exactly 2 minimum spanning trees. Solution.
has more than 2 minimum spanning trees. Solution.
4. A Minimum Edge.
Let \(G=(V,E)\) be a weighted graph.
Suppose that \(G\) contains a unique edge \(e\) of minimum weight in \(G\text{.}\) Prove that \(e\) is contained in every minimum spanning tree of \(G\text{.}\) Solution.
AFSOC that \(T\) is a minimum spanning tree that does not contain \(e\text{.}\) Then \(T+e\) contains a cycle \(C\text{.}\) The edge \(e\) has the unique minimum weight in this cycle. So let \(f\) be any other edge in \(C\text{.}\) The spanning tree \(T-f+e\) has smaller weight than \(T\text{,}\) a contradiction.
Suppose that \(G\) contains an edge \(e\) such that for every cycle \(C\) containing \(e\text{,}\) the weight \(w(e)\) is smaller than all the other edge weights in \(C-e\text{.}\) Prove that \(e\) is contained in every minimum spanning tree of \(G\text{.}\) Solution.
The proof is exactly the same as the previous part.
5. Minimum Spanning Forest.
Extend the concept of a minimum spanning tree to a disconnected, weighted graph. Define a "minimum spanning forest" and describe how you would find it. Solution.
A minimum spanning forest for a graph with components \(G_1, G_2, \ldots, G_k\) is a forest \(T_1, T_2, \ldots, T_k\) where \(T_i\) is a minimum spanning tree for component \(G_i\text{.}\) Kruskal's algorithm actually creates a minimum spanning forest for a disconnected graph.
