GATE CSE 2003 | Question: 67

Question

Let $G =(V,E)$ be an undirected graph with a subgraph $G_1 = (V_1, E_1)$. Weights are assigned to edges of $G$ as follows.

$$w(e) = \begin{cases} 0 \text{,   if } e \in E_1 \\1 \text{,   otherwise} \end{cases}$$

A single-source shortest path algorithm is executed on the weighted graph $(V,E,w)$ with an arbitrary vertex $v_1$ of $V_1$ as the source. Which of the following can always be inferred from the path costs computed?

• A. The number of edges in the shortest paths from $v_1$ to all vertices of $G$
• B. $G_1$ is connected
• C. $V_1$ forms a clique in $G$
• D. $G_1$ is a tree

Comments

Answer: B.

Two claims:

Claim 1 : From $v_1$, If any vertex has shortest path distance 0 in G then that vertex is NECESSARILY in $V_1$.

Claim2 : If there is NonZero distance shortest path from $v_1$ to a vertex $b$ then either $b$ is Not in $V_1$ OR $b$ is NOT Connected to $v_1$ in $G_1$.

Corollary of above two claims:
From $v_1$, If all vertex of $V_1$ have distance 0 then $G_1$ is connected, Else $G_1$ is disconnected..

Good question it is.

Proof of above two claims is easy & should be tried.

---

Thanks @Deepak Poonia Sir for the claims to corollary approach!

---

Lovely explanation ❤️

Answer 1

After applying the shortest path algorithm, check cost of vertex from source to every vertex in $G_1$. If $G_1$ is connected all these costs must be $0$ as edge weights of subgraph $G_1$ is $0$ and that should be the shortest path. If cost is not $0$, to at least one vertex in $G_1$ (not necessarily $G$), then $G_1$ is disconnected.

Answer is B.

Comments

If cost is not 0, to at least one vertex in G1 (not necessarily G), then G1 is disconnected.

It is always in G because G1 is a subgraph of G, Tell me if I’m wrong...

---

hy,

According to definition  “A graph is said to be connected if there exist at least one path between every pair of vertices otherwise graph is said to be disconnected.” 

https://en.wikipedia.org/wiki/Connectivity_(graph_theory)

“If The number of edges is supposed to be the shortest paths from v to all vertices of G.” But if its not so we can intrepret that either few vertices in G1 are connected (which means as a whole G1 is disconnected) or all vertices in G1 is connected (which means it forms a tree or a cyle (clique) )

If we assume G1 is connected(if there exist is at least one path between every pair of vertices),

Either:

1. G1 forms a tree (Or) (option D)
2. G1 forms a cycle which in turns a clique (option C)

I think we cant really assume anything.

But if “option B was: G1 atleast 1 connected edge”. it would be more apt. since

“option B was: G1 atleast 1 connected edge” : FALSE: The number of edges is supposed to be the shortest paths from v to all vertices of G

“option B was: G1 atleast 1 connected edge” : TRUE: The number of edges is not supposed to be the shortest paths from v to all vertices of G since the existence of Zero edge.

Please do correct me if i am wrong.

 

 

---

@ASNR1010 You are correct about G1 being a subgraph of  G, hence all vertices of G1 is definitely in G.

 

But, in the  best answer the line is :-

 If cost is not 0, to at least one vertex in G1 (not necessarily G),

It does not say “If cost is not 0, to at least one vertex in G1 (not necessarily in G)” //The word ‘in’ is missing and plays a vital role.

So what does the line actually say?

It says that the cost must be 0 to all vertices in G1 in-order to be a connected graph. 

It says that the cost may not be 0 to all vertices in G.

Answer 2

yes. (b) is correct option!

Comments

What is the G itself is disconnected nothing is specified in the question about G if G is disconnected and is included in G1 then G1 won't be connected please help

---

 Which of the following can always be inferred from the path costs computed?

Answer =subgraph should be connected

which is actually wrong 

---

@Manu.What if g is not connected.?

---

If G is not connected then How can u apply single source shortest path algo on it on the basis of $G_{1}$ ?? according to the question ...

---

NICE EXPLAINATION

Answer 3

Ans is (B)

When we compute shortest path from one of the vertex v1 in V1.Then we can infer as
G1 is connected if the cost from v1 to any other vertex in V1 is 1.
G1 is disconnected otherwise

Comments

I didn't understand the phrase "G1 is connected if the cost from v1 to any other vertex in V1 is 1"

Since, edges between vertices in v1 are having weight 0, how can the cost of any other vertex in v1 can be 1?

G1 is disconnected is the cost to any other vertex in G1 is having cost more than 0.

Please clarify.

---

@khush Tak: i think that G1 is connected if the cost from v1 to any other vertex in V1 is 0 " should be there . 

:) 

---

ok got it b is correct becz tree is a connected

---

connected property is  valid but these connection of graph is as per that so there will no formation of  cycle  which implies it will be a tree where every vertex is cover and acyclic graph is form

ans D;

Answer 4

Here we assume G is a connected Graph(Single source shortest path applied). Otherwise this question can not be solved based on the Given options.

Option A is incomplete.

Note:- Just like a graph could be disconnected, a subgraph could also be disconnected. Reference- https://www.youtube.com/watch?v=dPHkyRvLtIU

Comments

Nice answer 

@Nitesh Singh 2   what is the meaning of option A

---

Ram Swaroop Option A is indeed incomplete. we can't infer anything.