72. In the accompanying graphs, the number in the circle for each vertex is the cost of installing equipment at the vertex if relaying must be done at the vertex, while the number on an edge indicates the cost of providing service between the endpoints of the edge.

In each case, find the minimum cost (allowing relays) for sending messages between any pair of vertices, taking vertex relay costs into account.

77

Would your answer be different if vertex relay costs were neglected? (Warning: Kruskal’s algorithm cannot be used to answer the first question. This problem illustrates the value of having an algorithm over relying on “brute force.”)