Make your own free website on Tripod.com

Exercise 22.2-1

Show the d and p values that result from running breadth-first search on the directed graph of Figure 22.2(a), using vertex 3 as the source.

Answer:                                    d Values

                                    Oval: ¥
Oval: 1Oval: ¥Oval: ¥Oval: 0Oval: 1Oval: S

 

 

 

 

 

 

 


 

           

 

 

 

 

 

 

 


                                                p Values

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


Exercise 22.2.2

Show the d and p values that result from running breadth-first search on the undirected graph of Figure 22.3, using vertex u as the source.

Answer: Similar to the answer in 22.1-1. After run through the algorithm BFS(G,s) we have the final results as follow:

 

               r                 s             t                  u

d Values

 
 

 

 

 

 

 


              v                 w            x                y

 

 

p Values

 
 

 

 

 

 

 

 

 


Exercise 22.2-6

There are two types of professional wrestlers: "good guys" and "bad guys." Between any pair of professional wrestlers, there may or may not be a rivalry. Suppose we have n professional wrestlers and we have a list of r pairs of wrestlers for which there are rivalries. Give an O(n + r)-time algorithm that determines whether it is possible to designate some of the wrestlers as good guys and the remainder as bad guys such that each rivalry is between a good guy and a bad guy. If it is possible to perform such a designation, your algorithm should produce it.

Answer:

Reference: http://www.cs.rpi.edu/~bushl2/portfolio/2_wrestlemania/wrestlemaniaD1.pdf

This answer is an abstract from the paper written by Larry Bush of Rensselaer Polytechnic Institute.

“Create an undirected graph G = (V,E) in which the vertices V are the wrestlers names and the edges represent rivalries (i.e. There is an edge (u, v)contained in E if and only if there is a rivalry between wrestler u and wrestler v). Thus |V | = n and |E| = r. Pick a vertex as a source vertex and begin running BFS, labeling the source vertex as “good” and each vertex adjacent to it as “bad.” For each such “bad” vertex label each of its adjacent white vertices as “good,” and continue in this way, alternating between “good” and “bad” according to whether the distance between the source and the vertex is even or odd. But if a vertex has an adjacent gray or black vertex that is labeled the same as itself, stop with the result that there is no solution. If this first BFS completes, it has successfully labeled all vertices in the connected component containing the chosen source vertex. Repeat this process for each of the connected components; i.e., choose any remaining white vertex as the source (skip the usual initialization loop that initializes all nodes to white). If all of these modified BFSs successfully complete, then the resulting labeling of the vertices as good or bad is a solution; if any of them fails, stop and report there is no solution.

Correctness argument: First, if the algorithm stops and says there is no solution, then there really is none, because for that component of the graph, everything is determined by the initial choice of “good” for the source vertex, and labeling it “bad” instead would lead to exactly the same situation in which the algorithm cannot continue (just with every vertex in the component having the opposite labeling). And choosing a different source vertex in that component wouldn’t help since the distances found between any pair of vertices are shortest path distances and are thus independent of the choice of source vertex. Second, if all of the modified BFSs complete, then by the alternation of assignment of good and bad, and the check performed as each adjacent gray or black node is considered, all edges (rivalries) have been considered and there is no rivalry between two good or two bad wrestlers.

Although this algorithm has an extra loop over all vertices in order to process all connected components, the total time is still O(V + E), since there is no overlap between the executions for each connected component. Thus the time is O(n + r), as specified.”