CS502 Assignment No 4 Spring 2012 solution


Give an example of a directed graph G = (V, E), a source vertex s  V, and a set of tree edges Eπ ⊆ E such that for each vertex v  V, the unique path in the graph (V, Eπ) from s to v is a shortest path in G, yet the set of edges Eπ cannot be produced by running BFS on G, no matter how the vertices are ordered in each adjacency list.


Let V = {s, 1, 2, 3, 4}, and let

E = {(s, 1), (s, 2), (1, 3), (1, 4), (2, 3), (2, 4)}.

Last, let

= {(s, 1), (s, 2), (1, 4), (2, 3)}.

If vertex 1 precedes vertex 2 on the queue for BFS, then any search will produce tree edges (1, 3) and (1, 4); otherwise, the tree will have edges (2, 3), (2, 4).

22.2-6. There are n professional wrestlers, and r pairs of wrestlers for which there are rivalries. Find an O(n + r)-time algorithm to see if the wrestlers can be divided into ’good guys’ and ’bad guys’, such that each rivalry is between a good and bad guy.

This question is equivalent to the following: given a graph on n vertices with r edges, determine whether the vertices can be divided into two parts, G, B such that no edge connects two vertices in G or two vertices in B.

It is easy to see that if such a division is possible, then there cannot be any odd length cycle; conversely, if there is no odd length cycle, a BFS can be used to construct the subdivision; start a BFS with any vertex s; call it ’good’; put all adjacent vertices on the queue, and call them ’bad’; whenever a good (resp. bad) vertex is at the head of the queue, label any new adjacent vertex in the opposite way and put it on the queue. If there is no odd length cycle, there will be no ambiguity as to the designation. Since BFS takes O(n + r) steps, we’re done.