Question

Use Sollin's algorithm to produce a minimum spanning tree for the weighted graph shown in

\({\bf{a}})\)Figure \(1\).

\(b)\)Figure \(3\).

Short answer

a. Minimum spanning tree contains edges

(San Francisco, Denver)

(San Francisco, Chicago)

(Chicago, Atlanta)

(New York, Atlanta)

b. Minimum spanning tree contains edges

\((a,b),(a,e),(b,c),(b,f),(c,d),(c,g),(f,j),(g,h),(g,k),(i,j),(k,I)\).

Step-by-step solution

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 \(n{\bf{ - 1}}\) edges were chosen.

Ordering the vertices

First,one needs to order all vertices:

\(\begin{array}{*{20}{r}}{{\bf{ Rank }}}&{{\bf{ Vertex }}}\\{\bf{1}}&{{\bf{ San Francisco }}}\\{\bf{2}}&{{\bf{ Chicago }}}\\{\bf{3}}&{{\bf{ New York }}}\\{\bf{4}}&{{\bf{ Denver }}}\\{\bf{5}}&{{\bf{ Atlanta }}}\end{array}\)

Next, one chooses the edge incident to each vertex with the smallest weight (or the edge first in lexicographic order in case of a tie).

Obtaining the graph

\(\begin{array}{*{20}{r}}{{\bf{ Vertex }}}&{{\bf{ Edge }}}\\{{\bf{ Francisco }}}&{{\bf{ (San Francisco,Denver) }}}\\{{\bf{ Chicago }}}&{{\bf{ (Chicago, Atlanta) }}}\\{{\bf{ New York }}}&{{\bf{ (New York, Atlanta) }}}\\{{\bf{ Denver }}}&{{\bf{ (San Francisco,Denver) }}}\\{{\bf{ Atlanta }}}&{{\bf{ (Chicago, Atlanta) }}}\end{array}\)

We add these \(3\) edges to the empty graph.

Step 4:Minimum spanning tree

Next,one needs to determine the edge connecting San Francisco or Denver to one of the other three cities with the smallest weight. The cheapest such connection is from San Francisco to Chicago, thus we add that edge to the graph.

Since we only have \({\bf{1}}\) tree in the image below, this tree is then the minimum spanning tree.

Edge incident

One uses the alphabetical ordering for the vertices.

Next one chooses the edge incident to each vertex with the smallest weight (or the edge first in lexicographic order in case of a tie).

\(\begin{array}{*{20}{r}}{{\bf{ Vertex }}}&{{\bf{ Edge }}}\\{\bf{a}}&{{\bf{(a,b)}}}\\{\bf{b}}&{{\bf{(b,f)}}}\\{\bf{c}}&{{\bf{(c,d)}}}\\{\bf{d}}&{{\bf{(c,d)}}}\\{\bf{e}}&{{\bf{(a,e)}}}\\{\bf{f}}&{{\bf{(b,f)}}}\\{\bf{g}}&{{\bf{(c,g)}}}\\{\bf{h}}&{{\bf{(h,g)}}}\\{\bf{i}}&{{\bf{(i,j)}}}\\{\bf{j}}&{{\bf{(f,j)}}}\\{\bf{k}}&{{\bf{(k,l)}}}\\{\bf{l}}&{{\bf{(k,l)}}}\end{array}\)

One adds these \(9\) edges to the empty graph.

Minimal spanning tree

One then need to connect the tree with vertices \(a,b,e,f,i\) and \(j\) to one of the other two trees. The weights of edges connecting the trees are always \(3\). Thus we need to choose the two edges that come first in the lexicographic order (note:the two edges cannot be between the same two tree). We then note that we need to add the edge \((b,c)\) and \((g,k)\)

One then obtained one single tree and thus one found the minimal spanning tree.