Question

Find a spanning tree with minimal total weight containing the edges \(\left\{ {{\bf{e, i}}} \right\}\) and \(\left\{ {{\bf{g, k}}} \right\}\) in the weighted graph in Figure \(3\).

Short answer

Answers could vary.

A possible such spanning tree contains the edges

\(\left( {{\bf{a, b}}} \right){\bf{,}}\left( {{\bf{a, e}}} \right){\bf{,}}\left( {{\bf{b, c}}} \right){\bf{,}}\left( {{\bf{b, f}}} \right){\bf{,}}\left( {{\bf{c, d}}} \right){\bf{,}}\left( {{\bf{c, g}}} \right){\bf{,}}\left( {{\bf{e, i}}} \right){\bf{,}}\left( {{\bf{f, j}}} \right){\bf{,}}\left( {{\bf{g, h}}} \right){\bf{,}}\left( {{\bf{g, k}}} \right){\bf{,}}\left( {{\bf{k, l}}} \right)\).

Step-by-step solution

Definition

A graph is connected if there exists a path between every pair of vertices.

Kruskal's algorithm:

Start from a graph \({\bf{T}}\) that contains only the vertices and no edges. Repeatedly select the edge in the given graph \({\bf{G}}\) with the smallest weight (that doesn't cause a circuit) and add it to the graph \({\bf{T}}\).Once the graph is connected, we have found a minimum spanning tree.

Using the Kruskal’s algorithm

Let \({\bf{T}}\) be the graph with the vertices of the given graph \({\bf{G}}\) and with no edges between the vertices.

We first add the edged \({\bf{(e,i)}}\) and \({\bf{(g,k)}}\). Next, we will apply Kruskal's algorithm to determine the remaining edges.

\({\bf{(e,i),(g,k)}} \in {\bf{T}}\)

The smallest weight of \(1\) occurs between \({\bf{b}}\)and \({\bf{f}}\), between \({\bf{c}}\) and \({\bf{d}}\)and between \({\bf{k}}\) and \({\bf{l}}\), thus we add these edges to the graph \({\bf{T}}\) (as none of these edges cause a circuit).

\({\bf{(b,f),(c,d),(k,l)}} \in {\bf{T}}\)

Weight of edge

The smallest weight of \(2\) in the remaining graph is between \({\bf{a}}\) and \({\bf{b}}\), between \({\bf{c}}\) and \({\bf{g}}\)and between \({\bf{f}}\) and \({\bf{j}}\), thus we add these edges to the graph \({\bf{T}}\) (as none of these edges cause a circuit).

\({\bf{(a,b),(c,g),(f,j)}} \in {\bf{T}}\)

The smallest weight in the remaining graph is \(3\). There are many edges with weight \(3\) , we still require \(3\) edges and thus we should select \(3\) edges that do not cause any circuits. For example, I will choose \({\bf{(a,e),(b,c)}}\) and \({\bf{(g,h)}}\) (note: you could choose different edges).

\({\bf{(a,e),(b,c),(g,h)}} \in {\bf{T}}\)

Step 4:Obtaining graph

One has then obtained a connected graph and thus the minimum spanning tree contains the edges mentioned above (that were added to T ).