The Gateway to Computer Science Excellence
+1 vote

Here i have option III is option III always counter example is if i choose a tree where s is root node and v1& v2 are its child node then above question property i.e the vertices V1 and V2 that are simultaneously on the function call stack at some point during the execution of depth-first search from vertex s in a digraph is satisfies.but there is no any path from v1 to v2 or from v2 to v1.

in Algorithms by Active (1.1k points)
edited by | 160 views

yup must not be true but may be true .

Sir may be true means False ans should be option a.but here option is c.
yes a will be ans
why is III not always true??....
there may be no path from V1 to V2
@srestha, i think it should be,

can you give a counter example in which both are not connected to each other and still both of them are in the stack...?
have u read the example given by sahu?
okk, i was confused with simultaneous ... if they will be connected then no meaning of simultaneous, hence option A is true...
the example given by @dileswar sahu is false as he has taken Tree but in question it mention directed GRAPH..hope it clear all your doubt
every tree is graph but graph need not tree.

Please log in or register to answer this question.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,741 questions
57,252 answers
104,698 users