Suppose the Xs in the following table indicate locations where fire sprinkler heads need to be installed

Suppose the X’s in the following table indicate locations where fire sprinkler heads need to be installed in an existing building. The S indicates the location of the water source to supply these sprinklers. Assume that pipe can be run only vertically or horizontally (not diagonally) between the water source and the sprinkler heads.

a. Create a spanning tree showing how water can be brought to all the sprinkler heads using a minimal amount of pipe.
b. Suppose that it takes 10 feet of pipe to connect each cell in the table to each adjacent cell. How much pipe does your solutionrequire?

Transcribed Image Text:

4 12345678