GATE CSE
First time here? Checkout the FAQ!
x
+4 votes
1.4k 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.1k points)  
edited by | 1.4k 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 (281k 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 (52.4k 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.3k 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 Junior (767 points)  


Top Users Mar 2017
  1. rude

    4768 Points

  2. sh!va

    3054 Points

  3. Rahul Jain25

    2920 Points

  4. Kapil

    2734 Points

  5. Debashish Deka

    2592 Points

  6. 2018

    1544 Points

  7. Vignesh Sekar

    1422 Points

  8. Akriti sood

    1342 Points

  9. Bikram

    1312 Points

  10. Sanjay Sharma

    1126 Points

Monthly Topper: Rs. 500 gift card

21,508 questions
26,832 answers
61,091 comments
23,146 users