• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon Suggested languages for you:

Europe

Answers without the blur. Sign up and see all textbooks for free! Q27E

Expert-verified Found in: Page 803 ### Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095 # Prove that Sollin’s algorithm produces a minimum spanning tree in a connected undirected weighted graph.

Sollin's algorithm produces a minimum spanning tree

See the step by step solution

## Step 1: Definition

Sollin's algorithm:

Let all vertices be ordered (which also produces a lexicographic ordering of the edges).Simultaneously choose the edge of least weight incident to every vertex (In case of ties, use the first edge in the ordering).Simultaneously choose an edge from a vertex in each tree (result of previous step) to a vertex in a different tree with minimum weight (In case of ties, use the first edge in the ordering).Repeat until $${\bf{n - 1}}$$ edges were chosen.

Given: $${\bf{G}}$$ is a connected undirected weighted graph

## Step 2: Using Sollin’s algorithm

To proof: Sollin's algorithm produces a minimum spanning tree of $${\bf{G}}$$

Let $${\bf{S}}$$ be the tree produced by Sollin's algorithm and let $${{\bf{e}}_{\bf{1}}}{\bf{,}}{{\bf{e}}_{\bf{2}}}{\bf{, \ldots ,}}{{\bf{e}}_{{\bf{n - 1}}}}$$ be its edges in the order chosen (edges at the same stage are ordered arbitrarily).Let $${\bf{T}}$$ be the minimum spanning tree that contains all the edges $${{\bf{e}}_{\bf{1}}}{\bf{,}}{{\bf{e}}_{\bf{2}}}{\bf{, \ldots ,}}{{\bf{e}}_{\bf{k}}}$$ (for the largest possible value of $${\bf{k}}$$ ).

$${\bf{0}} \le {\bf{k}} \le {\bf{n - 1}}$$

Let us assume that $${\bf{k}} \le {\bf{n - 1}}$$. Let $${{\bf{S}}^{}}{\bf{'}}$$ be the forest in the execution of Sollin's algorithm for $${\bf{S}}$$ at the stage before $${{\bf{e}}_{\left\{ {{\bf{k + 1}}} \right\}}}$$ is added and let $${\bf{C}}$$ be the component in $${{\bf{S}}^{}}{\bf{'}}$$ responsible for the addition of $${{\bf{e}}_{\left\{ {{\bf{k + 1}}} \right\}}}$$.

Let $${{\bf{e}}_{\left\{ {{\bf{k + 1}}} \right\}}}{\bf{ = }}\left( {{\bf{u,v}}} \right)$$ with $${\bf{u}} \in {\bf{C}}$$ and $${\bf{v}} \notin {\bf{C}}$$.

## Step 3: Using lexicographic order

Let $${\bf{P}}$$ be the unique path from $${\bf{u}}$$ to $${\bf{v}}$$ in $${\bf{T}}$$. Let $${\bf{e'}}$$ be the first edge in the path not in $${\bf{S'}}$$ (which has to exists since the two vertices are in different trees in $${\bf{S'}}$$ ). This then implies that $${\bf{e'}}$$ is incident to $${\bf{C}}$$ and since the algorithm added $${{\bf{e}}_{\left\{ {{\bf{k + 1}}} \right\}}}$$ on behalf of $${\bf{C}}$$, the weight of $${{\bf{e}}_{\left\{ {{\bf{k + 1}}} \right\}}}$$ has to be smaller than the weight of $${\bf{e'}}$$ (or come first in lexicographic order when equal weight).

$${\bf{w}}\left( {{{\bf{e}}_{{\bf{k + 1}}}}} \right) \le {\bf{w}}\left( {{\bf{e'}}} \right)$$

However,$${\bf{e'}}$$ will be added on behalf of the component containing vertex $${\bf{v}}$$. If $${\bf{e'}}$$ is not $${{\bf{e}}_{\bf{1}}}{\bf{,}}{{\bf{e}}_{\bf{2}}}{\bf{, \ldots ,}}{{\bf{e}}_{\bf{k}}}$$, we then continue on in the path $${\bf{P}}$$ in the same manner until we obtain an edge $${{\bf{e}}^{{\bf{(r)}}}}$$ not in $${{\bf{e}}_{\bf{1}}}{\bf{,}}{{\bf{e}}_{\bf{2}}}{\bf{, \ldots ,}}{{\bf{e}}_{\bf{k}}}$$ (which has to exists as we will create a circuit otherwise and we have proven in a previous exercise that this is not possible)

$${\bf{w}}\left( {{{\bf{e}}_{{\bf{k + 1}}}}} \right) \le {\bf{w}}\left( {{{\bf{e}}^{{\bf{(r)}}}}} \right)$$

## Step 4:Minimum spanning tree

Let $${\bf{T' = T}} \cup \left\{ {{{\bf{e}}_{{\bf{k + 1}}}}} \right\}{\bf{ - }}\left\{ {{{\bf{e}}^{{\bf{(r)}}}}} \right\}$$, then the weight of $${\bf{T'}}$$ is less than or equal to the weight of $${\bf{T}}\left( {{\bf{sincew}}\left( {{{\bf{e}}_{{\bf{k + 1}}}}} \right) \le {\bf{w}}\left( {{{\bf{e}}^{{\bf{(r)}}}}} \right)} \right)$$

$${\bf{w}}\left( {{\bf{T'}}} \right) \le {\bf{w(T)}}$$

Thus $${\bf{T'}}$$ containing the edges $${{\bf{e}}_{\bf{1}}}{\bf{,}}{{\bf{e}}_{\bf{2}}}{\bf{, \ldots ,}}{{\bf{e}}_{\bf{k}}}{\bf{,}}{{\bf{e}}_{{\bf{k + 1}}}}$$ is then also a minimum spanning tree. One then derived a contradiction as we assumed that $${\bf{k}}$$ was the largest possible value for which $${{\bf{e}}_{\bf{1}}}{\bf{,}}{{\bf{e}}_{\bf{2}}}{\bf{, \ldots ,}}{{\bf{e}}_{\bf{k}}}$$ is a minimum spanning tree (and we now obtained that $${{\bf{e}}_{\bf{1}}}{\bf{,}}{{\bf{e}}_{\bf{2}}}{\bf{, \ldots ,}}{{\bf{e}}_{\bf{k}}}{\bf{,}}{{\bf{e}}_{{\bf{k + 1}}}}$$ also forms a minimum spanning tree).This then means that $${\bf{k = n - 1}}$$, which implies $${\bf{S = T}}$$ and thus then $${\bf{S}}$$ is a minimum spanning tree. ### Want to see more solutions like these? 