The Gateway to Computer Science Excellence
+29 votes
5.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$
in Algorithms by Boss (30.8k points)
edited by | 5.4k views
0
Q. - > Why edge weight is considered as 1 ?

Ans. -> I graph edge weight is 1 then BFS could be used for finding single source shortest path. If edge weight is not assumed to be then all options are possible. Please correct me if i am wrong.
0
If nothing is mentioned then we always consider singular weight.

7 Answers

+44 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.
by Veteran (431k points)
edited by
+7
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?
+8
I suppose that is a fair assumption given what all others we assume :)
+6
they forget to add 'Unweighted' word i think.i wasted lot of time thinking about this question how to solve
0
how will we think without knowing that edge weight is unity? Is it default weight of any graph?
IIT key was ?
+2
bfs works when all the edge weights are equal to find the shortest path not only when 1 .they should be equal thats it so if we take some value 2 then even D is possible they should have mentioned in the question but looking at the given options we should come to a consclusion that edge weights are assumed to be 1 .
+7

Extract from coremen

$\delta (u,v)$ indicates the shortest path from vertex u to v.

0
I'm unable to understand the solution here.. Is the BFS tree that's constructed not for the entire graph ? Because, if it is for the entire graph, then all the edges must be covered, right ? Is there anything here related to acyclicness of a tress that I'm missing ?
+34 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)

by Veteran (119k points)
edited by
0

srestha why we are assuming 1 for all ?

for any type of graph whose weights are distinct it is not satisfying the condition 

0

explaining option D bit more

In above diagram d(u) = 3 and d(v) = 1 hence difference is 2 , but is this diagram valid

No , because if V and U were connected then in DFS of graph U will come at level 2 and not at level 3 . and then distance of U = 2 and d(v) =1 hence difference will be 1 only.

Hence option d is not possible.

+23 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.

by Boss (23.9k points)
0
@ Rajesh Pradhan , very good solution
+15 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

by Boss (29.1k points)
+1 vote
answer is d
by Active (1.4k points)
0 votes
option d... thanku arjun sir
by Active (5k points)
edited by
0
both u and v can be child nodes of the same parent rt?
0 votes

BFS tree is constructed level by level. (We cover the whole level's breadth at one go)

If $u,v$ is an edge in the graph, then in BFS tree, either:-

  1. u and v are in the same level, or
  2. u is one level above v, or
  3. v is one level above u

In an unweighted graph(fair assumption), the distance between two nodes = number of edges between them. Clearly, the edges between u and v can't be 2.

Option D


 

Page 790, Kenneth H Rosen.

ago by Loyal (6.8k points)
Answer:

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,737 questions
57,370 answers
198,506 comments
105,272 users