Chapter 7

From The Algorithm Design Manual Solution Wiki
Jump to navigation Jump to search

Graph Traversal

Simulating Graph Algorithms

7.1. For the following graphs Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle G_1} (left) and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle G_2} (right):
(see book for figures)
(a) Report the order of the vertices encountered on a breadth-first search starting from vertex Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle A} . Break all ties by picking the vertices in alphabetical order (i.e., Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle A} before Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle Z} ).
(b) Report the order of the vertices encountered on a depth-first search starting from vertex Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle A} . Break all ties by picking the vertices in alphabetical order (i.e., Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle A} before Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle Z} ).

Solution


7.2. Do a topological sort of the following graph Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle G} :
(see book for figure)

Traversal

7.3. Prove that there is a unique path between any pair of vertices in a tree.

Solution


7.4. Prove that in a breadth-first search on a undirected graph Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle G} , every edge is either a tree edge or a cross edge, where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x} is neither an ancestor nor descendant of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle y} in cross edge Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (x, y)} .


7.5. Give a linear algorithm to compute the chromatic number of graphs where each vertex has degree at most 2. Any bipartite graph has a chromatic number of 2. Must such graphs be bipartite?

Solution


7.6. You are given a connected, undirected graph Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle G} with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n} vertices and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle m} edges. Give an Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle O(n + m)} algorithm to identify an edge you can remove from Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle G} while still leaving Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle G} connected, if one exists. Can you reduce the running time to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle O(n)} ?


7.7. In breadth-first and depth-first search, an undiscovered node is marked discovered when it is first encountered, and marked processed when it has been completely searched. At any given moment, several nodes might be simultaneously in the discovered state.
(a) Describe a graph on Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n} vertices and a particular starting vertex Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle v} such that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \Theta(n)} nodes are simultaneously in the discovered state during a breadth-first search starting from Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle v} .
(b) Describe a graph on Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n} vertices and a particular starting vertex Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle v} such that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \Theta(n)} nodes are simultaneously in the discovered state during a depth-first search starting from Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle v} .
(c) Describe a graph on Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n} vertices and a particular starting vertex Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle v} such that at some point Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \Theta(n)} nodes remain undiscovered, while Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \Theta(n)} nodes have been processed during a depth-first search starting from Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle v} .(Note, there may also be discovered nodes.)

Solution


7.8. Given pre-order and in-order traversals of a binary tree (discussed in Section 3.4.1), is it possible to reconstruct the tree? If so, sketch an algorithm to do it. If not, give a counterexample. Repeat the problem if you are given the pre-order and post-order traversals.


7.9. Present correct and efficient algorithms to convert an undirected graph Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle G} between the following graph data structures. You must give the time complexity of each algorithm, assuming Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n} vertices and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle m} edges.
(a)Convert from an adjacency matrix to adjacency lists.
(b)Convert from an adjacency list to an incidence matrix. An incidence matrix Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle M} has a row for each vertex and a column for each edge, such that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle M[i,j]=1} if vertex Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle i} is part of edge Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle j} , otherwise Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle M[i,j] = 0} .
(c)Convert from an incidence matrix to adjacency lists.

Solution


7.10. Suppose an arithmetic expression is given as a tree. Each leaf is an integer and each internal node is one of the standard arithmetical operations Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (+, -, *, /)} . For example, the expression Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 2+3*4+(3*4)/5} is represented by the tree in Figure 7.17(a). Give an Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle O(n)} algorithm for evaluating such an expression, where there are Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n} nodes in the tree.


7.11. Suppose an arithmetic expression is given as a DAG (directed acyclic graph) with common subexpressions removed. Each leaf is an integer and each internal node is one of the standard arithmetical operations Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (+,-,*,/)} . For example, the expression Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 2+3*4+(3*4)/5} is represented by the DAG in Figure (see book)(b). Give an Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle O(n+m)} algorithm for evaluating such a DAG, where there are Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n} nodes and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle m} edges in the DAG. Hint: modify an algorithm for the tree case to achieve the desired efficiency.

Solution


7.12. The war story of Section 7.4 (page 210) describes an algorithm for constructing the dual graph of the triangulation efficiently, although it does not guarantee linear time. Give a worst-case linear algorithm for the problem.

Applications

7.13. The Chutes and Ladders game has a board with n cells where you seek to travel from cell 1 to cell . To move, a player throws a six-sided dice to determine how many cells forward they move. This board also contains chutes and ladders that connect certain pairs of cells. A player who lands on the mouth of a chute immediately falls back down to the cell at the other end. A player who lands on the base of a ladder immediately travels up to the cell at the top of the ladder. Suppose you have rigged the dice to give you full control of the number for each roll. Give an efficient algorithm to find the minimum number of dice throws to win.

Solution


7.14. Plum blossom poles are a Kung Fu training technique, consisting of large posts partially sunk into the ground, with each pole at position . Students practice martial arts techniques by stepping from the top of one pole to the top of another pole. In order to keep balance, each step must be more than meters but less than meters. Give an efficient algorithm to find a safe path from pole to if it exists.


7.15. You are planning the seating arrangement for a wedding given a list of guests, . For each guest you have a list of all other guests who are on bad terms with them. Feelings are reciprocal: if is on bad terms with , then is on bad terms with . Your goal is to arrange the seating such that no pair of guests sitting at the same table are on bad terms with each other. There will be only two tables at the wedding. Give an efficient algorithm to find an acceptable seating arrangement if one exists.

Solution

Algorithm Design

7.16. The square of a directed graph is the graph such that iff there exists such that and ; i.e., there is a path of exactly two edges from to .
Give efficient algorithms for both adjacency lists and matrices.


7.17. A vertex cover of a graph is a subset of vertices such that each edge in is incident on at least one vertex of .
(a)Give an efficient algorithm to find a minimum-size vertex cover if is a tree.
(b)Let be a tree such that the weight of each vertex is equal to the degree of that vertex. Give an efficient algorithm to find a minimum-weight vertex cover of .
(c)Let be a tree with arbitrary weights associated with the vertices. Give an efficient algorithm to find a minimum-weight vertex cover of .

Solution


7.18. A vertex cover of a graph is a subset of vertices such that every edge in contains at least one vertex from . Delete all the leaves from any depth-first search tree of . Must the remaining vertices form a vertex cover of ? Give a proof or a counterexample.


7.19. An independent set of an undirected graph is a set of vertices $U$ such that no edge in is incident on two vertices of .
(a)Give an efficient algorithm to find a maximum-size independent set if is a tree.
(b)Let be a tree with weights associated with the vertices such that the weight of each vertex is equal to the degree of that vertex. Give an efficient algorithm to find a maximum independent set of .
(c)Let be a tree with arbitrary weights associated with the vertices. Give an efficient algorithm to find a maximum independent set of .

Solution


7.20. A vertex cover of a graph is a subset of vertices such that every edge in contains at least one vertex from . An independent set of graph is a subset of vertices such that no edge in contains both vertices from .
An independent vertex cover is a subset of vertices that is both an independent set and a vertex cover of . Give an efficient algorithm for testing whether contains an independent vertex cover. What classical graph problem does this reduce to?


7.21. Consider the problem of determining whether a given undirected graph contains a triangle or cycle of length 3.
(a)Give an to find a triangle if one exists.
(b)Improve your algorithm to run in time . You may assume .
Observe that these bounds gives you time to convert between the adjacency matrix and adjacency list representations of .

Solution


7.22. Consider a set of movies . There is a set of customers, each one of which indicates the two movies they would like to see this weekend. Movies are shown on Saturday evening and Sunday evening. Multiple movies may be screened at the same time.
You must decide which movies should be televised on Saturday and which on Sunday, so that every customer gets to see the two movies they desire. Is there a schedule where each movie is shown at most once? Design an efficient algorithm to find such a schedule if one exists.


7.23.The diameter of a tree is given by
(where is the number of edges on the path from to ). Describe an efficient algorithm to compute the diameter of a tree, and show the correctness and analyze the running time of your algorithm.

Solution


7.24. Given an undirected graph with vertices and edges, and an integer , give an algorithm that finds the maximum induced subgraph of such that each vertex in has degree , or prove that no such graph exists. An induced subgraph of a graph is a subset of of the vertices of , and all edges of such that both vertices of each edge are in .


7.25. Let and be two vertices in a directed graph . Design a linear-time algorithm to find the number of different shortest paths (not necessarily vertex disjoint) between and . Note: the edges in are unweighted.

Solution


7.26. Design a linear-time algorithm to eliminate each vertex of degree 2 from a graph by replacing edges and by an edge . We also seek to eliminate multiple copies of edges by replacing them with a single edge. Note that removing multiple copies of an edge may create a new vertex of degree 2, which has to be removed, and that removing a vertex of degree 2 may create multiple edges, which also must be removed.

Directed Graphs

7.27. The reverse of a directed graph is another directed graph on the same vertex set, but with all edges reversed; that is, . Give an algorithm for computing the reverse of an -vertex -edge graph in adjacency list format.

Solution


7.28. Your job is to arrange ill-behaved children in a straight line, facing front. You are given a list of statements of the form “ hates .” If hates , then you do not want to put somewhere behind , because then is capable of throwing something at .
(a) Give an algorithm that orders the line (or says that it is not possible) in time.
(b) Suppose instead you want to arrange the children in rows such that if hates , then must be in a lower numbered row than . Give an efficient algorithm to find the minimum number of rows needed, if it is possible.


7.29. A particular academic program has required courses, certain pairs of which have prerequisite relations so that means you must take course before . How would you analyze the prerequisite pairs to make sure it is possible for people to complete the program?

Solution


7.30. Gotcha-solitaire is a game on a deck with distinct cards (all face up) and gotcha pairs such that card must be played sometime before card . You play by sequentially choosing cards, and win if you pick up the entire deck without violating any gotcha pair constraints. Give an efficient algorithm to find a winning pickup order if one exists.


7.31. You are given a list of words each of length in a language you don’t know, although you are told that words are sorted in lexicographic (alphabetical) order. Reconstruct the order of the α alphabet letters (characters) in that language.
For example, if the strings are , the character order must be before before .
(a) Give an algorithm to efficiently reconstruct this character order. (Hint: use a graph structure, where each node represents one letter.)
(b) What is its running time, as a function of , and ?

Solution


7.32. A weakly connected component in a directed graph is a connected component ignoring the direction of the edges. Adding a single directed edge to a directed graph can reduce the number of weakly connected components, but by at most how many components? What about the number of strongly connected components?


7.33. Design a linear-time algorithm that, given an undirected graph and a particular edge in it, determines whether has a cycle containing .

Solution


7.34. An arborescence of a directed graph is a rooted tree such that there is a directed path from the root to every other vertex in the graph. Give an efficient and correct algorithm to test whether contains an arborescence, and its time complexity.


7.35. A mother vertex in a directed graph is a vertex such that all other vertices can be reached by a directed path from .
(a) Give an algorithm to test whether a given vertex is a mother of , where and .
(b) Give an algorithm to test whether graph contains a mother vertex.

Solution


7.36. Let be a directed graph. We say that is k-cyclic if every (not necessarily simple) cycle in contains at most distinct nodes. Give a linear-time algorithm to determine if a directed graph is -cyclic, where and are given as inputs. Justify the correctness and running time of your algorithm.


7.37. A tournament is a directed graph formed by taking the complete undirected graph and assigning arbitrary directions on the edges—that is, a graph such that for all , exactly one of or is in . Show that every tournament has a Hamiltonian path—that is, a path that visits every vertex exactly once. Give an algorithm to find this path.

Solution

Articulation Vertices

7.38. An articulation vertex of a connected graph is a vertex whose deletion disconnects . Let be a graph with vertices and edges. Give a simple algorithm for finding a vertex of that is not an articulation vertex—that is, whose deletion does not disconnect .


7.39. Following up on the previous problem, give an algorithm that finds a deletion order for the vertices such that no deletion disconnects the graph. (Hint: think DFS/BFS.)

Solution


7.40. Suppose is a connected undirected graph. An edge whose removal disconnects the graph is called a bridge. Must every bridge be an edge in a depth-first search tree of ? Give a proof or a counterexample.


7.41. A city that only has two-way streets has decided to change them all into one-way streets. They want to ensure that the new network is strongly connected so everyone can legally drive anywhere in the city and back.
(a) Let be the original undirected graph. Prove that there is a way to properly orient/direct the edges of provided does not contain a bridge.
(b) Give an efficient algorithm to orient the edges of a bridgeless graph so the result is strongly connected.

Solution

Interview Problems

7.42. Which data structures are used in depth-first and breath-first search?


7.43. Write a function to traverse binary search tree and return the ith node in sorted order.

Solution


Back to Chapter List