CS502 Assignment # 4 Solution June 2012

 CS502 Assignment # 4 Solution

Question:

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.

Solution:

Let V={s,1,2,3,4}
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) and ( 2,4).
22.2-6. There are no 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’ , such as rivalry is between a good and bad guy.
This question is equivalent to the following:
Given a graph on an vertices with r edges, determine whether the vertices can be divided into two parts, G,B such that no edges connects two vertices in G or two vertices in B.
It is easy to see that if such a division on possible, then there cannot be any odd length cycle; conversely, if there is no odd length cycle, a BSF can be used to construct the subdivision, start a BSF 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 are done.