Question

Suppose that the computer network connecting the cities in Figure \({\bf{1}}\) must contain a direct link between New York and Denver. What other links should be included so that there is a link between every two computer centers and the cost is minimized?

Short answer

Minimum spanning tree containing link between New York and Denver contains edges:

(Chicago, Atlanta)

(New York, Atlanta)

(Denver, San Francisco)

(Denver, New York)

Step-by-step solution

Definition

A graph is connected if there exists a path between every pair of vertices.

Kruskal's algorithm:

Start from a graph \({\bf{T}}\) that contains only the vertices and no edges.Repeatedly select the edge in the given graph \({\bf{G}}\) with the smallest weight (that doesn't cause a circuit) and add it to the graph \({\bf{T}}\).Once the graph is connected, we have found a minimum spanning tree.

Weight of the edge

Let \({\bf{T}}\) be the graph with the vertices of the given graph \({\bf{G}}\) and with no edges between the vertices.

We first add the edge between New York and Denver. Next, we will apply Kruskal's algorithm to determine the remaining edges.

The smallest weight of \({\bf{\$ 700}}\) occurs between Chicago and Atlanta, thus we add this edge to the graph \({\bf{T}}\) (as the edge does not cause a circuit).

The smallest weight of \({\bf{\$ 800}}\) in the remaining graph is between New York and Atlanta, thus we add this edge to the graph \({\bf{T}}\) (as the edge does not cause a circuit).

Obtaining the graph

The smallest weight of \({\bf{\$ 900}}\) in the remaining graph is between San Francisco and Denver, thus one adds this edge to the graph \({\bf{T}}\) (as the edge does not cause a circuit).

One has then obtained a connected graph and thus the minimum spanning tree contains the edges mentioned above (that were added to \({\bf{T}}\)).