|
|
|
|
Download all Excel spreadsheets for this chapter. The previous three chapters have shown how spreadsheets can be used to represent graphs. A natural question that arises is whether spreadsheets can also be used to represent directed graphs. Luckily, the answer is 'yes' and the process is quite similar to that of representing undirected graphs. The basic idea of the incidence representation of a directed graph is to label the edges by letters (A, B, C,...) and the vertices by numbers (1,2,3,...). Just as for the incidence representation of an undirected graph, we think of each row in the spreadsheet as representing a vertex and each column as representing an edge. The difference in this representation is that instead of placing two '1's in each column representing an arc, we instead place a '-1' and a '1' in each column. The '-1' is placed in the row which represents the vertex the arc is incident from and the '1' is placed in the row representing the vertex the arc is incident to. An example of a directed graph and its incidence representation is given in Figure 8.1.
Figure 8.1: A directed graph and its incidence representation.The incidence representation of a directed graph lends itself to some easy computations. For example, in order to compute the outdegree of each vertex, we can use the COUNTIF command. Figure 8.2 shows the results of entering the formula =COUNTIF(A1:H1,-1) into cell J1 and copying it down column J so as to compute the outdegree of each vertex for the directed graph shown in Figure 8.1.
Figure 8.2: Computing the outdegree of each vertex using the incidence representation of a directed graph.One might ask whether the incidence representation for a project digraph could be used to find the critical path time for the project. Figure 8.3 shows one method of doing this. Columns A through X are used to represent the arcs of the digraph. To carry out this particular method, we order the arcs (columns) in such a way that the '1's form a 'downward staircase' as we move left to right. Column Z is used to represent the processing time of each vertex. In column AA, we compute the critical times for each vertex working from the bottom up. Cell AA1 will then contain the value of the time for the critical path of the entire project. To compute the values in column AA, we begin in cell AA17 and work our way up the column. In AA17, we place the value of cell Z17 (namely 0) since there are no '-1's in this row. In cells AA16, AA15, and AA14, we place the formulas =Z16+AA17, Z15+AA17, and Z14+AA17 respectively. The reason for this formula in cell AA16 is that row 16 has one '-1' in it. In that column, namely X, there is a '1' in row 17. This is saying that the only vertex incident from vertex 16 is vertex 17. Hence, the critical time for vertex 16 is the sum of the processing time for vertex 16 and the critical time for vertex 17. Next, we construct the formula for cell AA13. Row 13 has only one '-1' in it. It is found in column U. Column U also has a '1' in row 16. Hence, the only vertex incident from vertex 13 is vertex 16. The critical time for vertex 13 is thus the sum of the processing time for vertex 13 and the critical time for vertex 16. We thus choose to use the formula =Z13+AA16. Cell AA12 is more interesting and illustrates how the process continues. Row 12 contains three '-1's in columns Q, S, and T. In these columns, we find '1's in rows 13, 14, and 15 respectively. The critical time for vertex 12 is thus the sum of the processing time for vertex 12 and the maximum of the critical times for vertices 13, 14, and 15. Hence, in cell AA12 we use the formula =Z12+MAX(AA13,AA14,AA15). We continue this process up column AA until reaching cell AA1 where the formula =Z1+MAX(AA2,AA3,AA4,AA5) is used giving a critical time for vertex 1 of 34. On your own, try to figure out the formula used in cell AA7. If you decided on =Z7+MAX(AA8,AA10), you are headed down the correct path (pun intended).
Figure 8.3: Computing the critical path time using the incidence representation of a project digraph.The reader should notice that if any processing time in column Z is changed, the output of column AA is automatically updated. Once again, we see the power and beauty of the modern dynamic spreadsheet. Walking Exercise 8.1 Figure 8.4 shows the incidence representation of a directed graph.
Figure 8.4: The incidence representation of a directed graph used in Exercise 8.1.(a) From the representation, find all vertices that are incident to vertex 5. Exercise 8.2 Figure 8.5 shows the incidence representation of a directed graph.
Figure 8.5: The incidence representation of a directed graph used in Exercise 8.2.(a) From the representation, find all vertices that are incident to vertex 5. Exercise 8.3 Use a spreadsheet and the incidence representation of the directed graph shown in Figure 8.1 to compute the indegree of each vertex. Exercise 8.4 Draw your favorite directed graph. (a) Compute the incidence representation of this directed graph and use a spreadsheet to compute the indegree and outdegree of each vertex. Exercise 8.5 Design a spreadsheet that will allow the user to input the number of processors working on a project and will output to another cell Ron Graham's error bound (as a percentage) for the largest possible percentage error incurred by using the critical-path algorithm. How many processors M are necessary in order to be assured that the critical-path algorithm will produce a result that is at most 30% more than the optimal schedule? Jogging Exercise 8.6 Given the incidence representation of a directed graph, how can you decide whether a particular arc is part of a cycle or not? Exercise 8.7 Replicate the spreadsheet shown in Figure 8.3. Be sure to use formulas to generate the values in column AA. How does the critical path time of the project change if the processing time at vertex 13 is changed to 3? What if the processing time at vertex 13 is changed to 4? Can you draw any conclusions? What happens if the processing time at vertex 11 is changed from 3 to 4? Exercise 8.8 Consider the incidence representation of a project digraph as shown in Figure 8.6.
Figure 8.6: The incidence representation of a project digraph used in Exercise 8.8.Using a spreadsheet, find the critical times for each vertex. What is the critical path time for the project? Based on the representation, can you draw the project digraph? Exercise 8.9 Consider the incidence representation of a project digraph as shown in Figure 8.7.
Figure 8.7: The incidence representation of a project digraph used in Exercise 8.9.(a) Using a spreadsheet, find the critical times for each vertex. What is the critical path time for the project? Running Exercise 8.10 A directed graph with n vertices can also be represented as a spreadsheet of n rows and n columns. The cell in the ith row and the jth column contains the number of edges incident from vertex i and incident to vertex j. This is called an adjacency representation of a directed graph. (a) Find the adjacency representation of the directed graph shown in Figure 8.1.
|
