Question

Use Kruskal’s algorithm to design the communicationsnetwork described at the beginning of the section

Short answer

Minimum spanning tree contains edges

(Chicago, Atlanta)

(Chicago, San Francisco)

(San Francisco, Denver)

(Atlanta, 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.

The smallest weight of \({\bf{\$ 700}}\) occurs between Chicago and Atlanta, thus we add this edge to the graph \({\bf{T}}\) (and remove it from \({\bf{G}}\) ).

The smallest weight of \({\bf{\$ }}8{\bf{00}}\) in the remaining graph is between New York and Atlanta, thus one adds this edge to the graph \({\bf{T}}\) (and remove it from \({\bf{G}}\) ).

The smallest weight of \({\bf{\$ }}9{\bf{00}}\) in the remaining graph is between San Francisco and Denver, thus one adds this edge to the graph \({\bf{T}}\) (and remove it from \({\bf{G}}\) ).

Obtaining the graph

The smallest weight of \({\bf{\$ }}10{\bf{00}}\) in the remaining graph is between New York and Chicago. However, adding this edge would cause a circuit in \({\bf{T}}\) and thus we just remove the edge from \({\bf{G}}\) (without adding it to \({\bf{T}}\) ).

The smallest weight of \({\bf{\$ }}12{\bf{00}}\) in the remaining graph is between San Francisco and Chicago. As this edge does not cause a simple circuit, we can add it to the graph \({\bf{T}}\).

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