12,909 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$

I am not able to understand one thing. If there is a direct path of difference 2 from source to a node at level 2, then we will include that node in the queue, and in that case, the distance would be 2. Am I missing anything?  Edges of $G$ which are not in $T$ are $(t-x),(x-u),(u-y)$

Option $A,B,C$ Satisfied

Answer $:D$

The simplest logic is since there is edge between u  and v in  even u is at 100 units  then v will be at 101 logically as there is and edge so distance cannot be  2 in anyway

$2$ is the answer.

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

$d(u) - d(v) = 1$ is possible when $v$ and another node $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

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 . Extract from coremen

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

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 ?

(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

srestha why we are assuming 1 for all ?

for any type of graph whose weights are distinct it is not satisfying the condition 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.

Nice

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.

@ Rajesh Pradhan , very good solution
Best example which I understand.Nice
can we consider different edges here to satisfy different conditions

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