Excel Project

Download all Excel spreadsheets for this chapter.

As we have seen, spreadsheets can be used to represent graphs. The basic idea of the incidence representation is to label the edges by letters (A, B, C,...) and the vertices by numbers (1,2,3,...). We then think of each row in the spreadsheet as representing a vertex and each column as representing an edge.

Suppose we would like to use such a spreadsheet representation to decide if a graph has a Hamilton circuit. Unfortunately, given an arbitrary graph, it is not simple to decide if it has a Hamilton circuit. However, in some cases, we may be able to apply a theorem due to Dirac.

Theorem 6.1 Dirac's Theorem If each vertex of a connected graph with 3 or more vertices is adjacent to at least half of the remaining vertices, then the graph has a Hamilton circuit. Recall that two vertices are adjacent if there is an edge connecting them.

Since each vertex is adjacent to at least 3 of the other vertices, the graph in Figure 6.1 has a Hamilton circuit by Dirac's theorem.

Figure 6.1: By Dirac's theorem, this graph has a Hamilton circuit.

We now use a spreadsheet representation of a graph to decide if Dirac's theorem, which shows that a Hamilton circuit exists, applies. The incidence representation for the graph in Figure 6.1 is shown in Figure 6.2. Notice, for example, that column D has a '1' occuring in row 3 and row 4 since edge D in the graph connects vertices 3 and 4. In fact, this is exactly how the spreadsheet in Figure 6.2 was constructed. Notice that the graph in Figure 6.1 is simple. That is, every edge is incident with exactly two distinct vertices and no two edges are incident to the same pair of vertices.

Figure 6.2: The incidence representation of the graph in Figure 6.1.

For a simple graph, such as the one in Figure 6.1, it is easy to decide if Dirac's theorem is applicable. We simply need to determine the degree of each vertex in the graph and check that it is at least (7-1)/2=3 (here, 7 is the number of vertices in the graph). To do this in the spreadsheet of Figure 6.2, we put =SUM(A1:M1) in cell O1 and copy this formula down column O. These outputs are the degrees of each vertex. Figure 6.3 shows the resulting spreadsheet. Since the value in every cell of column O is obviously greater than or equal to 3, Dirac's theorem applies and a Hamilton circuit exists. For larger incidence representations, the SORT tool in the spreadsheet may replace a visual inspection of this last column.

Figure 6.3: Deciding whether Dirac's theorem is applicable to the graph in Figure 6.1.

Willy Loman, a traveling salesman, has customers in 5 cities (A, B, C, D, and E) and is planning a sales trip to visit each. Willy needs to start and end the trip in his hometown city A; other than that there are no restrictions as to the order in which he should visit the other 4 cities. Figure 6.4 shows the cost of one-way travel between cities A, B, C, D, and E. How can we use a spreadsheet to try to minimize the cost of Willy's trip?

Figure 6.4: One-way cost of travel between cities on Willy's trip.

We start with the incidence representation for the weighted graph on these five vertices A, B, C, D, and E. Note that this is a complete graph on five vertices so that a Hamilton circuit exists. Also, note that we are using letters to represent the vertices (rows) in this case and we are not labeling the edges since so many exist. However, we will associate a cost to each edge (column) as shown in row 7 of Figure 6.5.

Figure 6.5: Incidence representation of Willy's graph problem.

Next, we select cells B1 through K7 and SORT them according to the value in row 7 of the spreadsheet (see Figure 6.6). The output of this sort is shown in Figure 6.7.

Figure 6.6: Sorting the weights in Willy's graph problem.

We will then apply the nearest-neighbor algorithm to this spreadsheet. We move from left to right and begin at the first instance that A (home) occurs. Column B shows we want to choose to go to city C at a cost of $119. From A, the cheapest city to go to (reading left to right of course) is city E at a cost of $120. Column E shows that the cheapest city to go to is A. But since A has already been visited, we need to move to the next '1' occuring in the row for city E which occurs in column J. Column J tells us to visit city D next at a cost of $199. Reading left to right, we see the cheapest city to go to from city D is city B at a cost of $150. Since we have visited each city, we now return home to city A to complete the circuit. Hence, Willy's travels will take him to A-C-E-D-B-A. A diagram which will help describe how this process works visually on a spreadsheet is given in Figure 6.7.

Figure 6.7: Solving Willy's graph problem using the SORT tool.

Walking

Exercise 6.1 Design a spreadsheet that will allow the user to input a positive integer N and will output the total number of edges in a complete graph with N vertices.

Exercise 6.2 Design a spreadsheet that will allow the user to input a positive integer N and will output the total number of Hamilton circuits in a complete graph with N vertices. How large does N need to be before the number of Hamilton circuits is too large for your spreadsheet to handle? Hint: To compute a number such as 5! on a spreadsheet, use the FACT command =FACT(5).

Exercise 6.3 Find the incidence representation of the graph in Figure 6.8. Use it and a spreadsheet to compute the degree of each vertex.

Figure 6.8: Graph for Exercise 6.3.

Exercise 6.4 Draw a graph which has an incidence representation as given in Figure 6.9.

Figure 6.9: Spreadsheet for Exercise 6.4.

Jogging

Exercise 6.5 Use the incidence representation of the graph in Figure 6.10 on a spreadsheet to show that Dirac's theorem is applicable to this graph. Can you find one of the Hamilton circuits?

Figure 6.10: Graph for Exercise 6.5.

Exercise 6.6 Use the incidence representation of the graph in Figure 6.11 on a spreadsheet to show that Dirac's theorem is not applicable to this graph.

Figure 6.11: Graph for Exercise 6.6.

Exercise 6.7 Use the incidence representation of a graph shown in Figure 6.12 to show that Dirac's theorem is not applicable to this graph. Can you add one edge so as make Dirac's theorem applicable (and thus guaranteeing that Hamilton circuit exists)?

Figure 6.12: Incidence representation for a graph with 7 vertices used in Exercise 6.7.

Exercise 6.8 Use the incidence representation of the graph in Figure 6.13 to show that Dirac's theorem is applicable to this graph. Can you find one of the Hamilton circuits?

Figure 6.13: Incidence representation for a graph with 5 vertices used in Exercise 6.8.

Exercise 6.9 [Excursions, Chapter 6, Exercise 25] Figure 6.4 shows Willy's cost of one-way travel between cities A, B, C, D, and E.

(a) Use a spreadsheet and the nearest-neighbor algorithm with starting vertex B to find a Hamilton circuit for Willy.
(b) Use a spreadsheet and the nearest-neighbor algorithm with starting vertex C to find a Hamilton circuit for Willy.
(b) Use a spreadsheet and the nearest-neighbor algorithm with starting vertex D to find a Hamilton circuit for Willy.
(d) Use a spreadsheet and the nearest-neighbor algorithm with starting vertex E to find a Hamilton circuit for Willy.
(e) Based on the repetitive nearest-neighbor algorithm, if Willy is based in city A, what circuit should he follow?

Exercise 6.10 [Excursions, Chapter 6, Exercise 29] Darren is a traveling salesperson whose territory consists of the 6 cities shown in the mileage chart below. Use a spreadsheet with a SORT tool and the nearest-neighbor algorithm with starting vertex of Minneapolis to find a Hamilton circuit for Darren. Begin by finding an incidence representation for a complete weighted graph on 6 vertices.

Exercise 6.11 [Excursions, Chapter 6, Exercise 28] Use an implementation of the nearest-neighbor algorithm on a spreadsheet to find a Hamilton circuit starting at vertex 1 for the graph in Figure 6.14.

Figure 6.14: Graph for Exercise 6.11.

Exercise 6.12 Use an implementation of the repetitive nearest-neighbor algorithm on a spreadsheet to find a Hamilton circuit starting at vertex 1 for the incidence representation of a weighted graph shown in Figure 6.15.

Figure 6.15: Incidence representation for a graph used in Exercise 6.12.

Exercise 6.13 Graphs which have vertices of degree 1 cannot have Hamilton circuits. How would you use this idea together with the incidence representation of a graph and the SUM command in a spreadsheet to show that a particular graph has no Hamilton circuit? Use your ideas to show that the graph having 9 vertices with the incidence representation in Figure 6.16 has no Hamilton circuit.

Figure 6.16: Incidence representation for a graph used in Exercise 6.13.

Running

Exercise 6.14 Explain how you could use a spreadsheet and the incidence representation of a weighted graph (such as that given in Figure 6.5) to implement the cheapest-link algorithm.