GATE CSE
First time here? Checkout the FAQ!
x
+4 votes
1.5k views

Let $G = (V, E)$ be a simple undirected graph, and $s$ be a particular vertex in it called the source. For $x \in V$, let $d(x)$ denote the shortest distance in $G$ from $s$ to $x$. A breadth first search (BFS) is performed starting at $s$. Let $T$ be the resultant BFS tree. If $(u, v)$ is an edge of $G$ that is not in $T$, then which one of the following CANNOT be the value of $d(u) - d(v)$?

  1. $-1$
  2. $0$
  3. $1$
  4. $2$
asked in Algorithms by Veteran (29.2k points)  
edited by | 1.5k views

6 Answers

+18 votes
Best answer

$2$ is the answer. 

$d(u) - d(v) = 0$ is possible when both $u$ and $v$ have an edge from $t$ and $t$ is in the shortest path from $s$ to $u$ or $v$.

$d(u) - d(v) = 1$ is possible when $v$ and $t$ are in the shortest path from $s$ to $u$ and both $t$ and $v$ are siblings- same distance from $s$ to both $t$ and $v$ causing $t-u$ edge to be in BFS tree and not $v-u$. 

$d(u) - d(v) = -1$ is possible as explained above by interchanging $u$ and $v$.

$d(u) - d(v) = 2$ is not possible. This is because on BFS traversal we either visit $u$ first or $v$. Let's take $u$ first. Now, we put all neighbors of $u$ on queue. Since $v$ is a neighbour and $v$ is not visited before as assumed, $d(v)$ will become $d(u) + 1$. Similarly, for $v$ being visited first. 

answered by Veteran (283k points)  
edited by
edge weight is not defined. There is never a place where they say that edge weight is unity.

Isn't this an issue with this question?
I suppose that is a fair assumption given what all others we assume :)
they forget to add 'Unweighted' word i think.i wasted lot of time thinking about this question how to solve
how will we think without knowing that edge weight is unity? Is it default weight of any graph?
IIT key was ?
+9 votes

(B)Take distance from S

d(U) =1 from S

d(V)=1 from S

So, d(U) - d(V) =0 , d(X) is one shortest distance of the graph

and BFS traversal will not take edge UV

(C) Now for assuming d(U) and d(V) has a distance 1, we similarly calculate the distance from S(in next figure)

(A)In previous figure change the position of U and V, so get

d(U)-d(V) = -1

(D) but 2 not possible as there is a direct edge from U to V always, So, no graph possible with min distance 2. The max distance could be 1 

So, ans is (D)

answered by Veteran (53.1k points)  
edited by
+3 votes

By Option Elimination:-

Here (2,3) or (3,2)and (3,4) or (4,3) pairs eligible for (u,v) pair as per question bcz these edges are not part of BFS Tree.

lets take (2,3) here d(2)-d(3)=1-1=0 So Option B is feasible 

now (3,4) here d(3)-d(4)=1-2=-1 , So Option A is feasible

now (4,3) here d(4)-d(3)=2-1=1 So Option C is feasible

Hence Option D is Ans.

 

answered by Veteran (16.5k points)  
+2 votes
answer is d
answered by Active (1.3k points)  
+2 votes
option d... thanku arjun sir
answered by Loyal (4.8k points)  
edited by
both u and v can be child nodes of the same parent rt?
0 votes

By having known this property, answer is straight away 2 i.e. option D.

Source : https://www.cs.umd.edu/class/fall2009/cmsc451/lectures/Lec03-graphs.pdf

answered by Active (1.2k points)  


Top Users Apr 2017
  1. akash.dinkar12

    3796 Points

  2. Divya Bharti

    2716 Points

  3. Deepthi_ts

    2294 Points

  4. rude

    2142 Points

  5. Tesla!

    1888 Points

  6. Kapil

    1786 Points

  7. Sanjay Sharma

    1702 Points

  8. Debashish Deka

    1690 Points

  9. Prashant.

    1672 Points

  10. Arjun

    1614 Points

Monthly Topper: Rs. 500 gift card

22,149 questions
28,146 answers
63,542 comments
24,309 users