Example 7

EXAMPLE 7 Cable TV Service

Imagine that cable TV (CT) service will be set up on one large university campus. The graph in Figure 2.12 shows the possible links that might be included in the CT network, with each edge showing the cost in hundreds of thousands of dollars to create that particular link. To send video between two locations, a direct cable link is not necessary because it is possible to send a video indirectly via another site. Thus, in Figure 2.12, sending a video from A to C could be achieved by sending the video from A to B, from B to E, and from E to C, provided the links AB, BE, and EC are part of the network. We assume that the cost of relaying a video, compared with the cost of the direct communication link, is so small that we can neglect this amount. The problem that concerns us, therefore, is to provide service between any pair of locations in a way that minimizes the total cost of the links.

When students are given access to local cable TV networks, minimizing the cost of creating such networks might involve the techniques of finding a minimum-cost spanning tree.

Figure 2.12: Figure 2.12 Costs of installing cable service among five locations.

Our first guess at a solution is to put in the cheapest possible links between locations first, until all sites could send video to any other site. Such an approach is analogous to the sorted-edges method that was used to study the traveling salesman problem. in our example, if the cheapest links are added until all locations are joined, we obtain the connections shown in Figure 2.13a.

Figure 2.13: Figure 2.13 (a) Sites are linked in order of increasing cost until all locations are connected. (b) Circuit in part (a) highlighted. (c) Most expensive link in circuit in part (a) deleted. (d) Highlighted edges show, as a subgraph of the original graph, those links connecting the locations with minimum cost, obtained using Kruskal’s algorithm. The numbers show the order in which Kruskal’s algorithm selects the edges.

The links were added in the order ED,AD,AE,AB,DC. However, because this graph contains the circuit ADEA (wiggly edges in Figure 2.13b), it has redundant edges: We can still send videos between any pair of sites using relays after omitting the most expensive edge in the circuit—AE. After an edge of a circuit is deleted, a video can still be relayed among the sites of the circuit by sending signals the long way around. After AE is deleted, videos going from A to E can be sent via D (Figure 2.13c). These ideas constitute a procedure developed by Joseph Kruskal (1928-2010) in 1956.

Kruskal’s Algorithm PROCEDURE

Kruskal’s algorithm: Add links in order of cheapest cost so that no circuits form and so that every vertex belongs to some link added (Figure 2.13d).

In Kruskal’s procedure, as in the sorted-edges method for the TSP, the edges that are added need not be connected to each other until the end. A subgraph formed in this way is a tree; that is, it consists of one piece and contains no circuits. it also includes all the vertices of the original graph. A subgraph that is a tree and that contains all the vertices of the original graph is called a spanning tree of the original graph.

To understand these concepts better, consider the graph G in Figure 2.14a. The wiggly edges in Figure 2.14b constitute a subgraph of G that is a tree (because it is connected and has no circuit), but this tree is not a spanning tree of G because the vertices D and E are not included. On the other hand, the wiggly edges in Figure 2.14c and 2.14d show subgraphs of G that include all the vertices of G but are not trees because the first is not connected and the second contains a circuit. Figure 2.14e shows a spanning tree of G; the wiggly edges are connected and contain no circuit, and every vertex of the original graph is an endpoint of some wiggly edge.

Figure 2.14: Figure 2.14 (a) A graph to help illustrate the concept of a spanning tree. (b) The wiggly edges are a tree, but not a spanning tree, because vertices D and E are not part of the tree. (c) The wiggly edges are not a tree because they are not connected. All of the vertices of the graph are, however, endpoints of wiggly edges. (d) The wiggly edges are not a tree, because they contain the edges of the circuit BDCAB. All the vertices of the graph are, however, endpoints of wiggly edges. (e) The wiggly edges form a tree and include all of the vertices of the graph as endpoints of wiggly edges. Thus, the wiggly edges are a spanning tree.