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

Lovely explanation ❤️

---

awesome!!

---

A clique in a graph is a subset of vertices such that every pair of distinct vertices is connected by an edge.

In simple words: A clique is a completely connected subgraph.

This may help.

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

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.

---

you didnt talk about vertces not in G1 but still have a path to source vertex. for entire graph, we initially set cost as INF. we use dikstra and s we compute path cost we redue the pah cost. whichever vertices have inf at end aare disconnected from the vertex v

Answer 2

yes. (b) is correct option!

Comments

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

Answer 5

Answer is option B.