The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+35 votes
2.8k views

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?
 

  1. The number of edges in the shortest paths from $v_1$ to all vertices of $G$
  2. $G_1$ is connected
  3. $V_1$ forms a clique in $G$

  4. $G_1$ is a tree

asked in Algorithms by Veteran (59.4k points)
edited by | 2.8k views
+1
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.
+1
I have a serious doubt here ... Can a single subgraph of a graph be disconnected ???
+7

Consider this graph - 

+2

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.

0
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

3 Answers

+38 votes
Best answer

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.

Ans is B.

answered by Loyal (8k points)
selected by
+6
If cost of v1 to all the vertices in V1 is 0 connected, else disconnected.
0

According to question we are asked to apply single source shortest path algorithm on graph V and not on graph V1 using any vertex of subgraph V1 as source. So, Option (a) must be the correct answer because if we apply dijksta algorithm on graph V , we will always get number of edges in the shortest path from vertex V1 to all vertices of G.

+4

gshivam63 See We are calculating the cost of for v1 of graph G1

which is a subgraph of G1 

and we know we can calculate cost for connected edges only

Here G1 is subgraph of G , which must be connected.

But G can be disconnected.

A) is not true because we are calculating shortest path for every subgraph  G1 ,not for G always . As G can be disconnected.

If u have any better example, u can give

 

+6

The above example can help, where G and G1 are sample graphs in accordance with the specification in the question.

As we can clearly see the results of shortest path algorithm on G, we can say G1 is connected.

Ans-(b)

0

@srestha "which is a subgraph of G not  G1  i think ?

+8 votes

yes. (b) is correct option!

answered by Boss (39.2k points)
0
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
0

 

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

Answer =subgraph should be connected

which is actually wrong 

 

 

0
@Manu.What if g is not connected.?
0
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 ...
+5 votes

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

answered by Loyal (7.5k points)
+2
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.
0

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

:) 

0
ok got it b is correct becz tree is a connected
0
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;


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

35,527 questions
42,803 answers
121,618 comments
42,166 users