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

Here our goal is to find shortest path so according to question the edge cost of G1 are 0 which leads to our goal shortest path so we try to contain max edge in G1 means we want to keep it connected.

---

I have a serious doubt here ... Can a single subgraph of a graph be disconnected ???

---

Consider this graph - 

---

In the mathematical area of graph theory, a clique is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent; that is, its induced subgraph is complete.

---

Anyone please clear my doubt what is the meaning of option a i.e  the number of edges in the shortest paths from v1 to all vertices of G

---

Option A can't be inferred because what if G is disconnected?

Option B can be inferred. Since all edge weights in $G_1$ is 0, but if we find a vertex of $G_1$ whose distance is more than 0 from another vertex of $G_1$, this would mean $G_1$ is disconnected. Otherwise, connected.

For Options C and D, data is insufficient, I think. Yes, the output of Dijkstra will form a tree, but we can't say $G_1$ is a tree from that. Because Dijkstra outputs a tree even when there are loops in the input graph.

---

are you saying that we can say whether G1 is connected or not ?? or that G1  must be connected

---

Formal Definition of Subgraph:

A  graph G'=(V', E') is a subgraph of another graph G=(V, E) iff

• V'⊆ V, and
• E'⊆ E ∧ ( (v1, v2)∈ E' → v1, v2∈ V').

A subgraph need not have all possible edges.

Hence, a subgraph can be disconnected.

Source.

---

If anyones there like me who didn’t really understood what the question is trying to say; this is for you : (Took me a long time to understand)

Its asking, If we apply SSSP on a vertex which is belonging to Graph G1(Which could be connected or disconnected), we would get shortest path cost from v1 to each vertex. Now, what can we comment by looking only at these path costs ? 

1. Can we say number of edges from this vertex to other vertices ? This cannot be done, because if you see cost “1” from v1 to v2, there is still a possibility that an edge with weight 0 could be anywhere between v1 to v2, so you cannot really say for sure that only 1 edge is there in between v1 to v2, there could be more !
2. Can we find out G1 subgraph is connected or disconnected? . Well, yes. If we see path costs “0” form v1 to all vertices in G1, that means G1 is connected. How ? Because there is no possibility of weight 1 in G1, so Shortest path must be 0. If we see “1” path cost, that would mean G1 is disconnected because somewhere I felt the need to take a vertex which is not in G1 to make my graph connected. 
3. We can say v1 belongs to a clique or not?  No, you cannot do that just by looking at the costs. You would need more information for that, like adjacent vertices. Just by looking at cost you cannot comment on that.
4. Can we say G1 is a tree or not? No, you cannot do that either just by looking at costs. You need to look at more information, but we’re only allowed to look at costs and interpret which is not possible.

---

@thewolf thanks a lot for the simple explanation ..this should be an answer ..best answer

---

Thanks for answer in the simpler way.

---

@JashanArora option A can be inferred . If the graph is disconnected then the distance from  source to destination vertex can be marked with infinity.

---

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 ❤️

---

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.