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 (29k 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 (280k 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 (51.8k 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 (201 points)  
Top Users Feb 2017
  1. Arjun

    5386 Points

  2. Bikram

    4230 Points

  3. Habibkhan

    3952 Points

  4. Aboveallplayer

    3086 Points

  5. Debashish Deka

    2564 Points

  6. sriv_shubham

    2318 Points

  7. Smriti012

    2236 Points

  8. Arnabi

    2008 Points

  9. mcjoshi

    1696 Points

  10. sh!va

    1684 Points

Monthly Topper: Rs. 500 gift card

20,863 questions
26,021 answers
59,689 comments
22,131 users