StudySmarter AI is coming soon!

- :00Days
- :00Hours
- :00Mins
- 00Seconds

A new era for learning is coming soonSign up for free

Suggested languages for you:

Americas

Europe

Q27E

Expert-verifiedFound in: Page 803

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**

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

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}}\).

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)\)

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.

94% of StudySmarter users get better grades.

Sign up for free