Question

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

Short answer

Maximum spanning tree contains edges

\((a,m),(b,f),(c,g),(d,p),(e,i),(f,j),(h,l),(i,j),(i,m),(j,k),(j,n),(g,k),(k,l),(k,o),(o,p)\).

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.

Edge weight

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

The largest weight of \(4\) in the given graph\(G\) occurs between \(j\) and \(n\), between \(j\) and \(k\)and between \(g\) and\(k\). Since neither edge will cause a circuit in\(T\), add all three edges to the graph \(T\) and remove them from \(G\).

\((j,n),(j,k),(g,k) \in T\)

The largest weight of \(3\)in the remaining graph\(G\)occurs between many pairs of edges. Only \((f,g)\) will cause a circuit when added together with \((f,j)\), thus add all edges with weight\(3\) except \((f,h)\)to the graph \(T\)and remove them from\(G\).

\((b,f),(c,g),(f,j),(h,l),(i,j),(i,m),(k,l),(k,o),(o,p) \in T\)

Edge incident with vertex

One then only need to connect \((a,e)\) and \(p\) to the graph. Each of these vertices has an edge incident with the vertex which has weight \(2\), thus add one such edge for each of the vertices.

\((a,m),(d,p),(e,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\)).