The Gateway to Computer Science Excellence
0 votes
178 views
Let T be a depth first search tree in an undirected graph G. Vertices u and ν are leaves of this tree T. The degrees of both u and ν in G are at least 2.

In such case in the graph there will be two cycles :- One Cycle will contain u and other one v.

There cannot be a graph containig a single cycle and containing both u and v and also satisfy above Constraint.

Am I right?
in Algorithms by Loyal (6.9k points) | 178 views
0
Have u applied DFS in the tree T and then reached on your desired outcome?Cycles aren't allowed. Because in case of a self loop too or under any circumstance the DFS shouldn't yield cycle. I hope this helps.
0

Its similar to Question depicted in http://gateoverflow.in/1824/gate2006_48

I have tried on various graphs.

Suppose there is a cycle in A graph then by applying DFS it will generate a non tree edge and in that DFS tree there would always be only one leaf node both u an v if present they cannot be a leaf node at the same moment(As i think)

Therefore i guess the answer to this question is D not C.

Am i right?

0
@Na462,the point to note is that it is mentioned here the nodes u and v are of 2 degrees. Hence,if u would have seen in the explanation in the diagram part the nodes of degree 2 form a leaf. The nodes u and v are leaves but not necessarily adjacent based on DFS traversal. Sorry for the late reply. I hope this helps. :)
0
I am sorry sir i cant get u properly U said   

" The nodes u and v are leaves but not necessarily adjacent based on DFS traversal."

So there can be a case where in a cycle u and v both are present and u and v both can be leaves. ?

I dont know but i cant get You. Can you explain with an example.Sorry for trouble :(
0
Look at first please don't call me Sir but brother will still be perfect. As the diagram is already drawn and example is given so I'll go with the one mentioned in the answer. As far as I mentioned what I'd wanted to convey was that u and v are leaves in tree T of graph G. Now coming to the DFS part,on the tree it's as simple as this, that if the degree of u and v is greater than 2 or at least 2 then certainly it'll be a part of cycle. The diagram drawn by Ahwan in there u can clearly see that vertex u contains it's neighbors. That's it. I hope now this serves you. Still not we'll go for a discussion again.
0
I got that brother and i knew that already that a vertex of degree 2 or atleast 2 will form a cycle.

My question was :- In above there is a cycle containing u and its neigbours and v is present in another cycle.

Can it be the case there there is only one cycle in the graph which contains both u and v. Then can u and v be the leaves of the DFS tree during the dfs traversal of the cycle.

In above diagram u and v both are part of different cycle therefore the answer is D(i.e. it will contain c and neighbours) but not C. Why not C?(Answer is according to me that There cannot be a graph containig a single cycle and containing both u and v and also satisfy above Constraint.)

You got my question wrong brother.

Ok then plz do tell that why the answer cannot be C.

Please log in or register to answer this question.

Related questions

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,647 questions
56,458 answers
195,368 comments
100,252 users