Question

Use Prim's algorithm to find a minimum spanning tree for the given weighted graph.

Short answer

Minimum spanning tree contains edges \((a,b)\),\((a,e)\),\((d,e)\)and \((c,d)\).

Step-by-step solution

Definition

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

Prim's algorithm:

Start from a graph that contains only the vertices and no edges, select a root, add the edge from the root to another vertex with the smallest weight.Repeatedly add the edge from a vertex in the already constructed tree to another vertex (not yet included in the tree) with the smallest weight, once the graph is connected, we have found a minimum spanning tree.

Edges incident

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

Let us select the vertex \(a\) as the root

There are \(3\) edges incident to \(a\) in \(G\) and \((a,b)\) has the smallest weight between these two edges, thus we add the edge \((a,b)\) to \(T\)

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

There are \(2\) edges incident to \(a\) remaining in \(G\) and \(2\) edges incident to \(b\). The smallest weight of these 4 edges is \(2\), which belongs to the edge \((a,e)\). As this edge does not causes a circuit, we can add it to the graph.

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

Edge incident

There is \(1\) edge incident to \(a\) remaining in\((G,2)\) edges incident to \(b\) and \(3\) edges incident to \(e\). The smallest weight of these edges is \(2\), which belongs to the edge \((d,e)\). As this edge does not causes a circuit, we can add it to the graph.

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

There is \(1\) edge incident to \(a\) remaining in \((G,2)\) edges incident to \((b,3)\) edges incident to \(e\) and \(2\) edges incident to \(d\). The smallest weight of these edges is \(1\), which belongs to the edge \((c,d)\). As this edge does not causes a circuit, we can add it to the graph.

\((c,d) \in T\)

Step 4:Obtaining the graph

One has obtained a connected graph; thus, the minimum spanning tree then consists of the previous four edges.