You know how there are fire hydrants on most blocks? They need to be connected to a water-pumping station in order to get water. And the pipes leading to them have to be laid along streets so that they can be serviced easily (and so they stay on public land). And, laying pipe is expensive so the city would like to lay the least length of pipe possible. Figure 12.21 shows a city neighborhood with fire hydrants and a local water-pumping station. Each block is 5 units wide and 4 units tall.
(a) Make a graph corresponding to this situation.
(b) Put appropriate weights on the edges of your graph.
(c) Find the minimum length of pipe needed to supply the fire hydrants with water.
