Assume that the Hamiltonian cycle problem is NP-complete for undirectedgraphs.a. Prove

Find a topological ordering for the graph in Figure 9.81.

If a stack is used instead of a queue for the topological sort algorithm in Section 9.2, does a different ordering result? Why might one data structure give a better answer?

Write a program to perform a topological sort on a graph

An adjacency matrix requires O(|V| 2) merely to initialize using a standard double loop. Propose a method that stores a graph in an adjacency matrix (so that testing for the existence of an edge is O(1)) but avoids the quadratic running time.

a. Find the shortest path from A to all other vertices for the graph in Figure 9.82. b. Find the shortest unweighted path from B to all other vertices for the graph in Figure 9.82.

What is the worst-case running time of Dijkstras algorithm when implemented with d-heaps (Section 6.5)?

a. Give an example where Dijkstras algorithm gives the wrong answer in the presence of a negative edge but no negative-cost cycle. b. Show that the weighted shortest-path algorithm suggested in Section 9.3.3 works if there are negative-weight edges, but no negative-cost cycles, and that the running time of this algorithm is O(|E||V|).

Suppose all the edge weights in a graph are integers between 1 and |E|. How fast can Dijkstras algorithm be implemented?

Write a program to solve the single-source shortest-path problem.

a. Explain how to modify Dijkstras algorithm to produce a count of the number of different minimum paths from v to w. b. Explain how to modify Dijkstras algorithm so that if there is more than one minimum path from v to w, a path with the fewest number of edges is chosen.

Find the maximum flow in the network of Figure 9.81.

Suppose that G = (V, E) is a tree, s is the root, and we add a vertex t and edges of infinite capacity from all leaves in G to t. Give a linear-time algorithm to find a maximum flow from s to t.

A bipartite graph, G = (V, E), is a graph such that V can be partitioned into two subsets V1 and V2 and no edge has both its vertices in the same subset. a. Give a linear algorithm to determine whether a graph is bipartite. b. The bipartite matching problem is to find the largest subset E of E such that no vertex is included in more than one edge. A matching of four edges (indicated by dashed edges) is shown in Figure 9.83. There is a matching of five edges, which is maximum. Show how the bipartite matching problem can be used to solve the following problem: We have a set of instructors, a set of courses, and a list of courses that each instructor is qualified to teach. If no instructor is required to teach more than one course, and only one instructor may teach a given course, what is the maximum number of courses that can be offered? c. Show that the network flow problem can be used to solve the bipartite matching problem. d. What is the time complexity of your solution to part (b)?

a. Give an algorithm to find an augmenting path that permits the maximum flow. b. Let f be the amount of flow remaining in the residual graph. Show that the augmenting path produced by the algorithm in part (a) admits a path of capacity f/|E|. c. Show that after |E| consecutive iterations, the total flow remaining in the residual graph is reduced from f to at most f/e, where e 2.71828. d. Show that |E| ln f iterations suffice to produce the maximum flow

a. Find a minimum spanning tree for the graph in Figure 9.84 using both Prims and Kruskals algorithms. b. Is this minimum spanning tree unique? Why?

Does either Prims or Kruskals algorithm work if there are negative edge weights?

Show that a graph of V vertices can have VV2 minimum spanning trees.

Write a program to implement Kruskals algorithm.

If all the edges in a graph have weights between 1 and |E|, how fast can the minimum spanning tree be computed?

Give an algorithm to find a maximum spanning tree. Is this harder than finding a minimum spanning tree?

Find all the articulation points in the graph in Figure 9.85. Show the depth-first spanning tree and the values of Num and Low for each vertex.

Prove that the algorithm to find articulation points works.

a. Give an algorithm to find the minimum number of edges that need to be removed from an undirected graph so that the resulting graph is acyclic. b. Show that this problem is NP-complete for directed graphs.

Prove that in a depth-first spanning forest of a directed graph, all cross edges go from right to left.

Give an algorithm to decide whether an edge (v, w) in a depth-first spanning forest of a directed graph is a tree, back, cross, or forward edge.

Find the strongly connected components in the graph of Figure 9.86.

Write a program to find the strongly connected components in a digraph

Give an algorithm that finds the strongly connected components in only one depthfirst search. Use an algorithm similar to the biconnectivity algorithm.

The biconnected components of a graph G is a partition of the edges into sets such that the graph formed by each set of edges is biconnected. Modify the algorithm in Figure 9.69 to find the biconnected components instead of the articulation points

Suppose we perform a breadth-first search of an undirected graph and build a breadth-first spanning tree. Show that all edges in the tree are either tree edges or cross edges.

Give an algorithm to find in an undirected (connected) graph a path that goes through every edge exactly once in each direction.

a. Write a program to find an Euler circuit in a graph if one exists. b. Write a program to find an Euler tour in a graph if one exists.

An Euler circuit in a directed graph is a cycle in which every edge is visited exactly once. a. Prove that a directed graph has an Euler circuit if and only if it is strongly connected and every vertex has equal indegree and outdegree. b. Give a linear-time algorithm to find an Euler circuit in a directed graph where one exists

a. Consider the following solution to the Euler circuit problem: Assume that the graph is biconnected. Perform a depth-first search, taking back edges only as a last resort. If the graph is not biconnected, apply the algorithm recursively on the biconnected components. Does this algorithm work? b. Suppose that when taking back edges, we take the back edge to the nearest ancestor. Does the algorithm work?

A planar graph is a graph that can be drawn in a plane without any two edges intersecting. a. Show that neither of the graphs in Figure 9.87 is planar. b. Show that in a planar graph, there must exist some vertex which is connected to no more than five nodes. c. Show that in a planar graph, |E| 3|V| 6

A multigraph is a graph in which multiple edges are allowed between pairs of vertices. Which of the algorithms in this chapter work without modification for multigraphs? What modifications need to be done for the others?

Let G = (V, E) be an undirected graph. Use depth-first search to design a linear algorithm to convert each edge in G to a directed edge such that the resulting graph is strongly connected, or determine that this is not possible.

You are given a set of N sticks, which are lying on top of each other in some configuration. Each stick is specified by its two endpoints; each endpoint is an ordered triple giving its x, y, and z coordinates; no stick is vertical. A stick may be picked up only if there is no stick on top of it. a. Explain how to write a routine that takes two sticks a and b and reports whether a is above, below, or unrelated to b. (This has nothing to do with graph theory.) b. Give an algorithm that determines whether it is possible to pick up all the sticks, and if so, provides a sequence of stick pickups that accomplishes this.

A graph is k-colorable if each vertex can be given one of k colors, and no edge connects identically colored vertices. Give a linear-time algorithm to test a graph for two-colorability. Assume graphs are stored in adjacency list format; you must specify any additional data structures that are needed.

Give a polynomial-time algorithm that finds V/2 vertices that collectively cover at least three-fourths (3/4) of the edges in an arbitrary undirected graph.

Show how to modify the topological sort algorithm so that if the graph is not acyclic, the algorithm will print out some cycle. You may not use depth-first search.

2 Let G be a directed graph with N vertices. A vertex s is called a sink if, for every v in V such that s = v, there is an edge (v,s), and there are no edges of the form (s, v). Give an O(N) algorithm to determine whether or not G has a sink, assuming that G is given by its N N adjacency matrix.

When a vertex and its incident edges are removed from a tree, a collection of subtrees remains. Give a linear-time algorithm that finds a vertex whose removal from an N vertex tree leaves no subtree with more than N/2 vertices.

Give a linear-time algorithm to determine the longest unweighted path in an acyclic undirected graph (that is, a tree).

Consider an N-by-N grid in which some squares are occupied by black circles. Two squares belong to the same group if they share a common edge. In Figure 9.88, there is one group of four occupied squares, three groups of two occupied squares, and two individual occupied squares. Assume that the grid is represented by a two-dimensional array. Write a program that does the following: a. Computes the size of a group when a square in the group is given. b. Computes the number of different groups. c. Lists all groups.

Section 8.7 described the generating of mazes. Suppose we want to output the path in the maze. Assume that the maze is represented as a matrix; each cell in the matrix stores information about what walls are present (or absent). a. Write a program that computes enough information to output a path in the maze. Give output in the form SEN... (representing go south, then east, then north, etc.). b. Write a program that draws the maze and, at the press of a button, draws the path

Suppose that walls in the maze can be knocked down, with a penalty of P squares. P is specified as a parameter to the algorithm. (If the penalty is 0, then the problem is trivial.) Describe an algorithm to solve this version of the problem. What is the running time of your algorithm?

Suppose that the maze may or may not have a solution. a. Describe a linear-time algorithm that determines the minimum number of walls that need to be knocked down to create a solution. (Hint: Use a double-ended queue.) b. Describe an algorithm (not necessarily linear-time) that finds a shortest path after knocking down the minimum number of walls. Note that the solution to part (a) would give no information about which walls would be the best to knock down. (Hint: Use Exercise 9.47.)

Write a program to compute word ladders where single-character substitutions have a cost of 1, and single-character additions or deletions have a cost of p > 0, specified by the user. As mentioned at the end of Section 9.3.6, this is essentially a weighted shortest-path problem.

The input is a list of league game scores (and there are no ties). If all teams have at least one win and a loss, we can generally prove, by a silly transitivity argument, that any team is better than any other. For instance, in the six-team league where everyone plays three games, suppose we have the following results: A beat B and C; B beat C and F; C beat D; D beat E; E beat A; F beat D and E. Then we can prove that A is better than F, because A beat B, who in turn beat F. Similarly, we can prove that F is better than A because F beat E and E beat A. Given a list of game scores and two teams X and Y, either find a proof (if one exists) that X is better than Y, or indicate that no proof of this form can be found.

The input is a collection of currencies and their exchange rates. Is there a sequence of exchanges that makes money instantly? For instance, if the currencies are X, Y, and Z and the exchange rate is 1 X equals 2 Ys, 1 Y equals 2 Zs, and 1 X equals 3 Zs, then 300 Zs will buy 100 Xs, which in turn will buy 200 Ys, which in turn will buy 400 Zs. We have thus made a profit of 33 percent.

A student needs to take a certain number of courses to graduate, and these courses have prerequisites that must be followed. Assume that all courses are offered every semester and that the student can take an unlimited number of courses. Given a list of courses and their prerequisites, compute a schedule that requires the minimum number of semesters.

The object of the Kevin Bacon Game is to link a movie actor to Kevin Bacon via shared movie roles. The minimum number of links is an actors Bacon number. For instance, Tom Hanks has a Bacon number of 1; he was in Apollo 13 with Kevin Bacon. Sally Field has a Bacon number of 2, because she was in Forrest Gump with"Tom Hanks, who was in Apollo 13 with Kevin Bacon. Almost all well-known actors have a Bacon number of 1 or 2. Assume that you have a comprehensive list of actors, with roles,3 and do the following: a. Explain how to find an actors Bacon number. b. Explain how to find the actor with the highest Bacon number. c. Explain how to find the minimum number of links between two arbitrary actors."

"The clique problem can be stated as follows: Given an undirected graph G = (V, E) and an integer K, does G contain a complete subgraph of at least K vertices? The vertex cover problem can be stated as follows: Given an undirected graph G = (V, E) and an integer K, does G contain a subset V V such that |V | K and every edge in G has a vertex in V ? Show that the clique problem is polynomially reducible to vertex cover."

Assume that the Hamiltonian cycle problem is NP-complete for undirected graphs. a. Prove that the Hamiltonian cycle problem is NP-complete for directed graphs. b. Prove that the unweighted simple longest-path problem is NP-complete for directed graphs.

The baseball card collector problem is as follows: Given packets P1, P2, ... , PM, each of which contains a subset of the years baseball cards, and an integer K, is it possible to collect all the baseball cards by choosing K packets? Show that the baseball card collector problem is NP-complete.