**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**

**p Values**

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.”

** **