Log In
4 votes

Let $G=(V, E)$ be an undirected simple graph, and $s$ be a designated vertex in $G.$  For each $v\in V,$ let $d(v)$ be the length of a shortest path between $s$ and $v.$ For an edge $(u,v)$ in $G,$ what can not be the value of $d(u)-d(v)?$

  1. $2$
  2. $-1$
  3. $0$
  4. $1$
in Graph Theory
recategorized by

2 Answers

1 vote

Here $d(u)=2$  and $d(v) = 1$ so $d(u) - d(v) = 2-1 =1 $ so option $B$ eliminated.

here $d(u) = d(v) = 1 $ so $d(u) - d(v) = 0 $ so option $C$ eliminated.

Here $d(u)=1$  and $d(v) = 2$ so $d(u) - d(v) = 1-2 =-1 $ so option $D$ eliminated.


If you look at the above graphs then you would realize that we are just either calculating the shortest path of $s$ from either vertex $v$ or $u$(whichever is the shortest) and then just adding $1$ since both $u$ and $v$ are adjacent to each other so shortest path would increase by just $1$ edge distance.

Hence the difference between $d(u) - d(v)$ can never be greater than $1$.

So Option $A$ is the correct answer.

0 votes
max difference between d(u) and d(v) is 1. Bcz if d(u) not equal to d(v), then d(u)=d(v)+1( for edge u-v). As this is undirected graph, we do not need to think about direction. hence option A is the correct answer.

Related questions

0 votes
1 answer
Your college has sent a contingent to take part in a cultural festival at a neighbouring institution. Several team events are part of the programme. Each event takes place through the day with many elimination rounds. Your contingent is multi-talented and each ... is: Find a maximum length simple cycle Find a maximum size independent set Find a maximum matching Find a maximal connected component
asked Sep 13, 2019 in Graph Theory gatecse 107 views
1 vote
1 answer
Let $G$ be a simple graph on $n$ vertices. Prove that if $G$ has more than $\binom{n-1}{2}$ edges then $G$ is connected. For every $n>2$, find a graph $G_{n}$ which has exactly $n$ vertices and $\binom{n-1}{2}$ edges, and is not connected.
asked Sep 13, 2019 in Graph Theory gatecse 99 views
1 vote
0 answers
Let $G=(V,E)$ be an undirected graph and $V=\{1,2,\cdots,n\}.$ The input graph is given to you by a $0-1$ matrix $A$ of size $n\times n$ as follows. For any $1\leq i,j\leq n,$ the entry $A[i,j]=1$ ... which any two vertices are connected to each other by paths. Give a simple algorithm to find the number of connected components in $G.$ Analyze the time taken by your procedure.
asked Sep 13, 2019 in Graph Theory gatecse 70 views
0 votes
1 answer
Consider a weighted undirected graph $G$ with positive edge weights. Let $(u, v)$ be an edge in the graph. It is known that the shortest path from a vertex $s$ to $u$ has weight $53$ and the shortest path from $s$ to $v$ has weight $65.$ Which of the statements is always true? Weight ... $(u, v) = 12$ Weight of $(u, v) \geq 12$ Nothing can be said about the weight of $(u, v)$
asked Dec 30, 2016 in Graph Theory jothee 174 views