Free Trial

Safari Books Online is a digital library providing on-demand subscription access to thousands of learning resources.

  • Create BookmarkCreate Bookmark
  • Create Note or TagCreate Note or Tag
  • PrintPrint

13.7. Exercises

For help with exercises, please visit the web site, www.wiley.com/college/goodrich.

13.7.1. Reinforcement

R-13.1 Draw a simple undirected graph G that has 12 vertices, 18 edges, and 3 connected components. Why would it be impossible to draw G with 3 connected components if G had 66 edges?

R-13.2 Draw an adjacency list and adjacency matrix representation of the undirected graph shown in Figure 13.1.

R-13.3 Draw a simple connected directed graph with 8 vertices and 16 edges such that the in-degree and out-degree of each vertex is 2. Show that there is a single (nonsimple) cycle that includes all the edges of your graph, that is, you can trace all the edges in their respective directions without ever lifting your pencil. (Such a cycle is called an Euler tour.)

R-13.4 Repeat the previous problem and then remove one edge from the graph. Show that now there is a single (nonsimple) path that includes all the edges of your graph. (Such a path is called an Euler path.)

R-13.5 Bob loves foreign languages and wants to plan his course schedule for the following years. He is interested in the following nine language courses: LA15, LA16, LA22, LA31, LA32, LA126, LA127, LA141, and LA169. The course prerequisites are:

  • LA15: (none)

  • LA16: LA15

  • LA22: (none)

  • LA31: LA15

  • LA32: LA16, LA31

  • LA126: LA22, LA32

  • LA127: LA16

  • LA141: LA22, LA16

  • LA169: LA32

Find the sequence of courses that allows Bob to satisfy all the prerequisites.

R-13.6 Suppose we represent a graph G having n vertices and m edges with the edge list structure. Why, in this case, does the insertVertex function run in O(1) time while the eraseVertex function runs in O(m) time?

R-13.7 Let G be a graph whose vertices are the integers 1 through 8, and let the adjacent vertices of each vertex be given by the table below:

VertexAdjacent Vertices
1(2, 3, 4)
2(1, 3, 4)
3(1, 2, 4)
4(1, 2, 3, 6)
5(6, 7, 8)
6(4, 5, 7)
7(5, 6, 8)
8(5, 7)


Assume that, in a traversal of G, the adjacent vertices of a given vertex are returned in the same order as they are listed in the table above.

  1. Draw G.

  2. Give the sequence of vertices of G visited using a DFS traversal starting at vertex 1.

  3. Give the sequence of vertices visited using a BFS traversal starting at vertex 1.

R-13.8 Would you use the adjacency list structure or the adjacency matrix structure in each of the following cases? Justify your choice.

  1. The graph has 10,000 vertices and 20,000 edges, and it is important to use as little space as possible.

  2. The graph has 10,000 vertices and 20,000,000 edges, and it is important to use as little space as possible.

  3. You need to answer the query isAdjacentTo as fast as possible, no matter how much space you use.

R-13.9 Explain why the DFS traversal runs in O(n2) time on an n-vertex simple graph that is represented with the adjacency matrix structure.

R-13.10 Draw the transitive closure of the directed graph shown in Figure 13.2. R-13.11 Compute a topological ordering for the directed graph drawn with solid edges in Figure 13.8(d).

R-13.12 Can we use a queue instead of a stack as an auxiliary data structure in the topological sorting algorithm shown in Code Fragment 13.23? Why or why not?

R-13.13 Draw a simple, connected, weighted graph with 8 vertices and 16 edges, each with unique edge weights. Identify one vertex as a "start" vertex and illustrate a running of Dijkstra's algorithm on this graph.

R-13.14 Show how to modify the pseudo-code for Dijkstra's algorithm for the case when the graph may contain parallel edges and self-loops.

R-13.15 Show how to modify the pseudo-code for Dijkstra's algorithm for the case when the graph is directed and we want to compute shortest directed paths from the source vertex to all the other vertices.

R-13.16 Show how to modify Dijkstra's algorithm to not only output the distance from v to each vertex in G, but also to output a tree T rooted at v such that the path in T from v to a vertex u is a shortest path in G from v to u.

R-13.17 There are eight small islands in a lake, and the state wants to build seven bridges to connect them so that each island can be reached from any other one via one or more bridges. The cost of constructing a bridge is proportional to its length. The distances between pairs of islands are given in the following table.

 12345678
1-240210340280200345120
2--265175215180185155
3---260115350435195
4----160330295230
5-----360400170
6------175205
7-------305
8--------


Find which bridges to build to minimize the total construction cost.

R-13.18 Draw a simple, connected, undirected, weighted graph with 8 vertices and 16 edges, each with unique edge weights. Illustrate the execution of Kruskal's algorithm on this graph. (Note that there is only one minimum spanning tree for this graph.)

R-13.19 Repeat the previous problem for the Prim-Jarník algorithm.

R-13.20 Consider the unsorted sequence implementation of the priority queue Q used in Dijkstra's algorithm. In this case, why is this the best-case running time of Dijkstra's algorithm O(n2) on an n-vertex graph?

R-13.21 Describe the meaning of the graphical conventions used in Figure 13.6 illustrating a DFS traversal. What do the colors blue and black refer to? What do the arrows signify? How about thick lines and dashed lines?

R-13.22 Repeat Exercise R-13.21 for Figure 13.7 illustrating a BFS traversal.

R-13.23 Repeat Exercise R-13.21 for Figure 13.9 illustrating a directed DFS traversal.

R-13.24 Repeat Exercise R-13.21 for Figure 13.10 illustrating the Floyd-Warshall algorithm.

R-13.25 Repeat Exercise R-13.21 for Figure 13.12 illustrating the topological sorting algorithm.

R-13.26 Repeat Exercise R-13.21 for Figures 13.14 and 13.15 illustrating Dijkstra's algorithm.

R-13.27 Repeat Exercise R-13.21 for Figures 13.18 and 13.20 illustrating Kruskal's algorithm.

R-13.28 Repeat Exercise R-13.21 for Figures 13.21 and 13.22 illustrating the Prim-Jarník algorithm.

R-13.29 How many edges are in the transitive closure of a graph that consists of a simple directed path of n vertices?

R-13.30 Given a complete binary tree T with n nodes, consider a directed graph G having the nodes of T as its vertices. For each parent-child pair in T, create a directed edge in G from the parent to the child. Show that the transitive closure of G has O(nlogn) edges.

R-13.31 A simple undirected graph is complete if it contains an edge between every pair of distinct vertices. What does a depth-first search tree of a complete graph look like?

R-13.32 Recalling the definition of a complete graph from Exercise R-13.31, what does a breadth-first search tree of a complete graph look like?

R-13.33 Say that a maze is constructed correctly if there is one path from the start to the finish, the entire maze is reachable from the start, and there are no loops around any portions of the maze. Given a maze drawn in an n × n grid, how can we determine if it is constructed correctly? What is the running time of this algorithm?


  

You are currently reading a PREVIEW of this book.

                                                                                                                    

Get instant access to over $1 million worth of books and videos.

  

Start a Free Trial


  
  • Safari Books Online
  • Create BookmarkCreate Bookmark
  • Create Note or TagCreate Note or Tag
  • PrintPrint