GATE CSE 2015 Set 1 | Question: 45

Question

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)$?

• A. $-1$
• B. $0$
• C. $1$
• D. $2$

Comments

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

---

Q8 here https://inst.eecs.berkeley.edu/~cs170/fa18/assets/exams/fa17-sol.pdf

Answer 1

$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.

Comments

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 ?

---

It is not mentoined that graph is acyclic...and all the nodes are covered but not all the edges...

Answer 2

(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)

Comments

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

Answer 3

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.

Comments

@ Rajesh Pradhan , very good solution

---

Best example which I understand.Nice

---

can we consider different edges here to satisfy different conditions

---

cool !

Answer 4

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