madeasy

Question

Consider 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. Which of the following must be true?

I. There exist directed path from s to V1 and directed path from s to V2 .

II. There exist both a directed path from V1 to V2 and a directed path from V2 to V1

III. If there is no directed path from V1 to V2 then there exist a directed path from V2 to V1 .

The number of above statements is/are true ________ .

Answer 1

To solve such questions, try to take just opposite of the condition asked in options, and try to satisfy the conditions asked in question. 

Conditions in question: 

1. DFS started from vertex s.

2. V1 and V2 are simultaneously on the stack. (No order given).

------------------------------------

Option 1st:

I. There exist directed path from s to V1 and directed path from s to V2 .

Note here, they are saying path, not edge.

So, it is true because without path, how did we reach from S to V1 or V2.

//You may say graph is disconnected, but if it is so, then they would not have been on stack at same time.

Option 2nd:

S----->V1------>V2

Here there is no directed path from V2 to V1, but they will be in stack at same time.

Option 3rd:

True, there has to be a path orelse they will not be in stack at same time.

Try drawing different graphs having path from v1 to v2, v2 to v1, not having path between them. And draw stack for that, you will get a clear picture. :)

so, 1st and 3rd are true here.

Answer 2

1 & 3 are true.

Comments

how??can u show me the help of diagram??

---

Take this example of directed graph

In this for II) to be considered as wrong ..we have an edge from  2 to 5 i.e in dfs stack both could occur  simultaneously.. But we have no edge from 5 to 2 ..... Hence this leads us to the III) to be true.... 

---

@Smriti suppose the path from 4 -->3  is not there and instead of it .. it is from 3-->4 and 2,3 are there in the stack ( it is possible that 2 and 3 are in the stack)  than the "option 3" will become false. am i ryt ?

---

But that wouldn't be a proper DFS
As it wouldn't go till the depth.... 

It would be like 1 then 2 backtrack to 1 visit 3 then visit 4 then 6 backtrack to 1 visit 2 again  visit 5... for 2 and 3 to occur simultaneously... this seems to be right..but is not according to me!!

A proper DFS is like visit 1-2-5-4-6-backtrack to 1 -visit 3 

Correct me if I am wrong