Question

Find a maximum spanning tree for the weighted graph in Exercise\(3\).

Short answer

Maximum spanning tree contains edges \((a,b),(b,c),(b,e),(b,f),(d,e),(d,g),(d,h),(f,i)\).

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 \(T\) that contains only the vertices and no edges.Repeatedly select the edge in the given graph \(G\) with the largest weight (that doesn't cause a circuit) and add it to the graph \(T\).Once the graph is connected, we have found a minimum spanning tree.

Weight of the edge

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

The largest weight of \(8\) in the given graph \(G\) occurs between \(d\) and \(h\). Add the edge to the graph \(T\) and remove it from \(G\).

\((d,h) \in T\)

The largest weight of \(7\) in the given graph \(G\)occurs between \(d\) and \(e\). Add the edge to the graph\(T\)and remove it from\(G\).

\((d,e) \in T\)

Add both edges

The largest weight of \(6\) in the given graph \(G\) occurs between \(d\) and \(g\)and between \(b\) and \(f\). Since neither edge will cause a circuit in \(T\), add both edges to the graph \(T\) and remove them from \(G\).

\((d,g),(b,f) \in T\)

The largest weight of \(5\) in the remaining graph\(G\) occurs between \(a\) and \(b\), and between \(b\)and\(e\). Since neither edge will cause a circuit in \(T\), add both edges to the graph \(T\)and remove them from\(G\).

\((a,b),(b,e) \in T\)

Obtaining graph

Finally, one still require an edge incident to \(c\)and an edge incident to \(i\). The edge with the largest weight incident to both vertices has weight \(4\), thus add those edges \((b,c)\) and \((f,i)\).

\((b,c),(f,i) \in T\)

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