Graph Traversal

Simulating Graph Algorithms

7.1. For the following graphs [math]\displaystyle{ G_1 }[/math] (left) and [math]\displaystyle{ G_2 }[/math] (right):

(see book for figures)

(a)Report the order of the vertices encountered on a breadth-first search starting from vertex [math]\displaystyle{ A }[/math]. Break all ties by picking the vertices in alphabetical order (i.e., [math]\displaystyle{ A }[/math] before [math]\displaystyle{ Z }[/math]).

(b)Report the order of the vertices encountered on a depth-first search starting from vertex [math]\displaystyle{ A }[/math]. Break all ties by picking the vertices in alphabetical order (i.e., [math]\displaystyle{ A }[/math] before [math]\displaystyle{ Z }[/math]).

Solution

7.2. Do a topological sort of the following graph [math]\displaystyle{ G }[/math]:

(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 [math]\displaystyle{ G }[/math], every edge is either a tree edge or a cross edge, where [math]\displaystyle{ x }[/math] is neither an ancestor nor descendant of [math]\displaystyle{ y }[/math] in cross edge [math]\displaystyle{ (x, y) }[/math].

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 [math]\displaystyle{ G }[/math] with [math]\displaystyle{ n }[/math] vertices and [math]\displaystyle{ m }[/math] edges. Give an [math]\displaystyle{ O(n + m) }[/math] algorithm to identify an edge you can remove from [math]\displaystyle{ G }[/math] while still leaving [math]\displaystyle{ G }[/math] connected, if one exists. Can you reduce the running time to [math]\displaystyle{ O(n) }[/math]?

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 [math]\displaystyle{ n }[/math] vertices and a particular starting vertex [math]\displaystyle{ v }[/math] such that [math]\displaystyle{ \Theta(n) }[/math] nodes are simultaneously in the discovered state during a breadth-first search starting from [math]\displaystyle{ v }[/math].

(b) Describe a graph on [math]\displaystyle{ n }[/math] vertices and a particular starting vertex [math]\displaystyle{ v }[/math] such that [math]\displaystyle{ \Theta(n) }[/math] nodes are simultaneously in the discovered state during a depth-first search starting from [math]\displaystyle{ v }[/math].

(c) Describe a graph on [math]\displaystyle{ n }[/math] vertices and a particular starting vertex [math]\displaystyle{ v }[/math] such that at some point [math]\displaystyle{ \Theta(n) }[/math] nodes remain undiscovered, while [math]\displaystyle{ \Theta(n) }[/math] nodes have been processed during a depth-first search starting from [math]\displaystyle{ v }[/math].(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 [math]\displaystyle{ G }[/math] between the following graph data structures. You must give the time complexity of each algorithm, assuming [math]\displaystyle{ n }[/math] vertices and [math]\displaystyle{ m }[/math] edges.

(a)Convert from an adjacency matrix to adjacency lists.

(b)Convert from an adjacency list to an incidence matrix. An incidence matrix [math]\displaystyle{ M }[/math] has a row for each vertex and a column for each edge, such that [math]\displaystyle{ M[i,j]=1 }[/math] if vertex [math]\displaystyle{ i }[/math] is part of edge [math]\displaystyle{ j }[/math], otherwise [math]\displaystyle{ M[i,j] = 0 }[/math].

(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 [math]\displaystyle{ (+, -, *, /) }[/math]. For example, the expression [math]\displaystyle{ 2+3*4+(3*4)/5 }[/math] is represented by the tree in Figure 7.17(a). Give an [math]\displaystyle{ O(n) }[/math] algorithm for evaluating such an expression, where there are [math]\displaystyle{ n }[/math] 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 [math]\displaystyle{ (+,-,*,/) }[/math]. For example, the expression [math]\displaystyle{ 2+3*4+(3*4)/5 }[/math] is represented by the DAG in Figure (see book)(b). Give an [math]\displaystyle{ O(n+m) }[/math] algorithm for evaluating such a DAG, where there are [math]\displaystyle{ n }[/math] nodes and [math]\displaystyle{ m }[/math] 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.