Chapter 9 Thus Under The Convention That Trees And

CHAPTER 9

Graph Algorithms

9.1 The following ordering is arrived at by using a queue and assumes that vertices appear on an adjacency list

9.2 Assuming the same adjacency list, the topological order produced when a stack is used is

9.4 The idea is the same as in Exercise 5.12.

9.5 (a) (Unweighted paths) A → B, A → C, A → B → G, A → B → E, A → C → D, A → B → E → F.

9.6 We’ll assume that Dijkstra’s algorithm is implemented with a priority queue of vertices that uses the

decreaseKey operation. Dijkstra’s algorithm uses |E| decreaseKey operations, which cost O(logd |V|) each,

and |V| deleteMin operations, which cost O(d logd |V|) each. The running time is thus O(|E| logd |V| + |V|d logd

9.7 (a) The graph shown here is an example. Dijkstra’s algorithm gives a path from A to C of cost 2, when the

path from A to B to C has cost 1.

9.8 See the comments for Exercise 9.19.

9.10 (a) Use an array count such that for any vertex u, count[u] is the number of distinct paths from s to u known

so far. When a vertex v is marked as known, its adjacency list is traversed. Let w be a vertex on the adjacency

list.

If dv + cv,w = dw, then increment count[w] by count[v] because all shortest paths from s to v with last edge

9.11 (This solution is not unique.)

First, send four units of flow along the path s, G, H, I, t. This gives the following residual graph:

Next, send three units of flow along s, D, E, F, t. The residual graph that results is as follows:

One unit of flow is then sent along s, D, A, E, C, t:

The preceding residual graph has no path from s to t. Thus the algorithm terminates. The final flow

graph, which carries 11 units, is as follows:

9.12 Let T be the tree with root r, and children r1, r2, . . . , rk, which are the roots of T1, T2, . . . , Tk, which have

maximum incoming flow of c1, c2, . . . , ck, respectively. By the problem statement, we may take the

If T is a leaf, then findMaxFlow returns incomingCap since we have assumed a sink of infinite capacity.

Otherwise, a standard postorder traversal can be used to compute the maximum flow in linear time.

// FlowType is an int or double

static FlowType findMaxFlow( Tree T, FlowType incomingCap )

}

9.13 (a) Assume that the graph is connected and undirected. If it is not connected, then apply the algorithm to the

connected components. Initially, mark all vertices as unknown. Pick any vertex v, color it red, and perform a

(b) Construct an undirected graph with a vertex for each instructor, a vertex for each course, and an edge

between (v, w) if instructor v is qualified to teach course w. Such a graph is bipartite; a matching of M edges

means that M courses can be covered simultaneously.

9.14 (a) This is a slight modification of Dijkstra’s algorithm. Let fi be the best flow from s to i at any point in the

algorithm. Initially, fi = 0 for all vertices, except s: fs = inf.

9.15 One possible minimum spanning tree is shown here. This solution is not unique.

9.16 Both work correctly. The proof makes no use of the fact that an edge must be nonnegative.

9.17 The proof of this fact can be found in any good graph theory book. A more general theorem follows:

Theorem.

9.19 The obvious solution using elementary methods is to bucket sort the edge weights in linear time. Then the

running time of Kruskal’s algorithm is dominated by the union/find operations and is O(|E|



(|E|, |V|)). The

Van-Emde Boas priority queues (see Chapter 6 references) give an immediate O(|E| log log |V|) running time

for Dijkstra’s algorithm, but this isn’t even as good as a Fibonacci heap implementation.

More sophisticated priority queue methods that combine these ideas have been proposed, including M.

9.20 Since the minimum spanning tree algorithm works for negative edge costs, an obvious solution is to replace

all the edge costs by their negatives and use the minimum spanning tree algorithm. Alternatively, change the

logic so that < is replaced by >, min by max, and vice versa.

num[E]; and F is an articulation point because low[G]  num[F]. The depth-first spanning tree is shown in the

following Figure.

9.22 The only difficult part is showing that if some nonroot vertex a is an articulation point, then there is no back

edge between any proper descendent of a and a proper ancestor of a in the depth-first spanning tree. We

prove this by a contradiction.

Let u and v be two vertices such that every path from u to v goes through a. At least one of u and v is a

9.23 (a) Do a depth-first search and count the number of back edges.

(b) This is the feedback edge set problem. See reference [1] or [20].

9.24 Let (v, w) be a cross edge. Since at the time w is examined it is already marked, and w is not a descendent of

9.25 Suppose the vertices are numbered in preorder and postorder.

If (v, w) is a tree edge, then v must have a smaller preorder number than w. It is easy to see that the

converse is true.

9.26 The first depth-first spanning tree is

Gr, with the order in which to perform the second depth–first search, is shown next. The strongly

connected components are F and all other vertices.

9.28 This is the algorithm mentioned in the references.

9.29 Because an edge (v, w) is implicitly processed, it is placed on a stack. If v is determined to be an articulation

9.30 Let (u, v) be an edge of the breadth-first spanning tree. (u, v) are connected, thus they must be in the same

tree. Let the root of the tree be r; if the shortest path from r to u is du, then u is at level du; likewise, v is at

9.31 Perform a depth-first search. The return from each recursive call implies the edge traversal in the opposite

direction. The time is clearly linear.

9.33 If there is an Euler circuit, then it consists of entering and exiting nodes; the number of entrances clearly must

9.34 Neither of the proposed algorithms works. For example, as shown, a depth-first search of a biconnected graph

that follows A, B, C, D is forced back to A, where it is stranded.

9.35 These are classic graph theory results. Consult any graph theory text for a solution to this exercise.

9.37 Obviously, G must be connected. If each edge of G can be converted to a directed edge and produce a

strongly connected graph G, then G is convertible.

9.38 (b) Define a graph where each stick is represented by a vertex. If stick Si is above Sj and thus must be

9.39 Use a depth-first search, marking colors when a new vertex is visited, starting at the root, and returning false

if a color clash is detected along a backedge.

9.40 Use a greedy algorithm: At each step, choose the vertex with the highest connectivity to vertices not already

chosen. Proof that only 1/4 of the edges are not touched can be done with a straightforward calculation of

9.41 If no vertex has indegree 0, we can find a cycle by tracing backwards through vertices with positive indegree;

since every vertex on the trace back has a positive indegree, we eventually reach a vertex twice, and the cycle

has been found.

9.44 This is essentially the algorithm described in Section 9.3.4 for critical paths.

9.45 These are all recursive depth first searches.

9.48 (a) Use the same ideas from the shortest path algorithm, but place unmarked adjacent squares at the front of a

double-ended queue, and unmarked adjacent wall-separate squares at the end. Note that when dequeues are

9.49 The following implementation does not use the map class. The use of ArrayList instead will speed up the

algorithm since access now takes O(1) instead of O(log N), if the list of words can fit in main memory. One

could use maps to also solve the problem. Using maps with keys and data both as strings allows the maps to

{

Vertex()

{

adj = new ArrayList<Integer>();

weight = new ArrayList<Integer>();

}

public ArrayList<Integer> adj; // Adjacency list

public ArrayList<Integer> weight; // Weight list

public boolean known;

public int dist;

public String name;

public int path;

};

/**

int smallestVertex;

Vertex v, s, t;

int n = Vertices.size();

Vertices.get(sIndex).dist = 0;

for ( ; ; )

{

v = Vertices.get(smallestVertex);

for ( int j = 0; j < v.adj.size(); j++ )

{

if ( !(Vertices.get( v.adj.get(j) ).known) )

{

if ( v.dist + v.weight.get(j) < Vertices.get( v.adj.get(j)

).dist )

{

w.name = oneLine;

w.known = false;

w.path = -1;

w.dist = INFINITY;

v.add( w ) ;

}

if( word1.charAt(i) ! = word2.charAt(i) )

if( + + diffs > 1 )

return 0;

if (diffs == 1)

return 1;

}

return p;

}

return 0;

}

// fills the adjacency lists for all words in the dictionary

static void fillAdjacencies(ArrayList<Vertex> words, int p)

{

int cost;

int w1Index, w2Index;

String w1 = new String();

String w2 = new String();

Scanner input = new Scanner(System.in);

Scanner dict;

try

{

w1 = input.next();

w2 = input.next();

// Find their indices (here is where a map would be superior

// However all other accesses are now in 0(1) time

for (w1Index = 0; w1Index < words.size()

&& (words.get(w1Index).name).compareTo(w1) ! = 0 ;

w1Index++);

}

9.50 Each team is a vertex; if X has defeated Y, draw an edge from X to Y.

9.52 Each course is a vertex; if X is a prerequisite for Y, draw an edge from X to Y Find the longest path in the

acyclic graph.

9.54 Given an instance of clique, form the graph G that is the complement graph of G: (v, w) is an edge in G if

9.55 A proof can be found in Garey and Johnson [20].

9.56 Clearly, the baseball card collector problem (BCCP) is in NP, because it is easy to check if K packets contain