Here is the DFS paradigm modified by adding a global variable time, and recordin

Question

Here is the DFS paradigm modified by adding a global variable time, and recording, for each vertex v, when v was colored gray and when it was colored black:

procedure DFS ( graph G = (V,E) )

/* G may or may not be directed. */

begin

for each v V do v.color WHITE ;

time 0 ;

for each v V do

if v.color = WHITE then Visit( v )

end .

procedure Visit( vertex v ) ;

begin

time time + 1 ;

v.start time ;

v.color GRAY ;

for each w s.t. (v, w) E do

if w.color = WHITE then Visit( w );

time time + 1 ;

v.finish time ;

v.color BLACK ;

end .

For each vertex v, define active(v) = {t : v.start t v. finish} .

For each of the following sentences regarding these active intervals after the DFS has terminated, answer “true” or “false;” prove your answers.

(a) ( v, w V)[ v w (active(v) active(w) or active(w) active(v) or active(w) active(v) = ) ]

(b) ( v, w V) [(active(w) active(v) = ) (v is neither a descendant nor an ancestor of w in the DFS forest) ]

Explanation / Answer

(a) Ans:

the anser is "True " because the abve statement clearly shows that subset of v,ware not equal means these are not same colors and these are not mutually equals so in order to intersect both v,w there is no element same in that finally the result shows null value

(b)Ans:

It is also true because the above statement can clearly shown there is no intersecting bitween both v,w so these are not siblings becaus no same color on the two element .

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.