Question

as you solve the problems below, consider how you can determine the most relevant edges for a minimum - weight spanning tree.
model
a local university is replacing the water pipes on campus. the pipes are a network, so water can flow between two locations through intermediary locations.
below is a map of campus locations. the number on a path between any two locations represents the expected amount of work time (in days) it will take to insert a new pipe between those two locations.
what is the smallest number of work days it will take to complete the project and connect all the campus locations with pipes? (assume that the lead engineer must be present each day. therefore, two different pipes cannot be inserted on the same day.)

Explanation:

Step1: Apply Kruskal's algorithm

We want to find a minimum - spanning tree. We start by sorting all the edge - weights in ascending order. The edge - weights are 1, 2, 2, 3, 4, 5, 6, 7, 9.

Step2: Select edges

We select edges one by one as long as they don't form a cycle. We first select the edge with weight 1 (between Dining Hall and Classrooms). Then we select the two edges with weight 2 (Library - Classrooms and Gym - Dorms). Then we select the edge with weight 3 (Gym - Classrooms).

Step3: Calculate total weight

The sum of the weights of the selected edges is \(1 + 2+2 + 3=8\).

Answer:

8