Question

Construct the minimal spanning tree that connects the vertices in the following graphically represented network model: D 15 F What is the minimal cost, clearly delineating which paths or edges were included in the optimal solution that yields this minimal cost? Document/detail the process utilized to minimize cost.

Answer 1

Use Kruskal's algorithm to construct the minimum spanning tree.

Include the arcs in the minimum spanning tree network starting from the minimum length arc with the length in the ascending order of magnitude.

Exclude an arc in the spanning tree if a closed loop is formed.

Stop when all the nodes have been included in a single spanning tree.

Arc	Length	Decision	Reason
D-J	5	Include
H-I	8	Include
C-I	10	Include
E-K	10	Include
A-B	12	Include
F-L	15	Include
B-H	15	Include
B-C	15	Exclude	Closed-loop B-H-I-C-B
K-L	16	Include
I-J	16	Include
C-D	18	Exclude	Closed-loop C-I-J-D-C
A-G	20	Include
D-E	21	Include	STOP (all nodes covered)

20 16

The overall length of the spanning tree = 148