Book edition 7th

Author(s) Kenneth H. Rosen

Pages 808 pages

ISBN 9780073383095

Answers without the blur.

Just sign up for free and you're in.

Short Answer

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 by Step Solution

TABLE OF CONTENTS :

TABLE OF CONTENTS

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.

Find Study Materials for

Create Study Materials

Select your language

Discrete Mathematics and its Applications

Answers without the blur.

Short Answer

Prove that Sollin’s algorithm produces a minimum spanning tree in a connected undirected weighted graph.

Step by Step Solution

Step 1: Definition

Step 2: Using Sollin’s algorithm

Step 3: Using lexicographic order

Step 4:Minimum spanning tree

Most popular questions for Math Textbooks

Want to see more solutions like these?

Recommended explanations on Math Textbooks

Select your language

Discrete Mathematics and its Applications

Answers without the blur.

Short Answer

Prove that Sollin’s algorithm produces a minimum spanning tree in a connected undirected weighted graph.

Step by Step Solution

Step 1: Definition

Step 2: Using Sollin’s algorithm

Step 3: Using lexicographic order

Step 4:Minimum spanning tree

Most popular questions for Math Textbooks

Want to see more solutions like these?

Recommended explanations on Math Textbooks

Decision Maths

Calculus

Probability and Statistics

Statistics

Mechanics Maths

Geometry

Pure Maths