Suppose we want to lay out an electric power grid to connect locations .
In Graph shown in Figure 1, each vertex corresponds to one of the locations , and each edge represents that an electric power line is possible to construct between the locations at the endpoints of the edge, with which the digit indicates its cost.
Answer the following questions:
(1) Show the adjacency matrix where each element is or and the corresponding Laplacian matrix of Graph .
(2) A spanning tree of Graph can be defined as a connected electric power grid that visits each location exactly once, not forming a cycle.
Show how many different spanning trees are possible for Graph . Also state the reasons for your answer.
(3) Out of the possible spanning trees considered in Question (2) above, find the one with the least total cost and show that total cost.