Let G = (V, E) be an undirected graph with a subgraph G₁ = (V₁, E₁). Weights…
2003
Let G = (V, E) be an undirected graph with a subgraph G₁ = (V₁, E₁). Weights are assigned to edges of G as follows:
w(e) = 0, if e ∈ E₁
w(e) = 1, if e ∉ E₁
A single-source shortest path algorithm is executed on the weighted graph (V, E, w) with an arbitrary vertex v₁ of V₁ 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₁ to all vertices of G
- B.
G₁ is connected
- C.
V₁ forms a clique in G
- D.
G₁ is a tree
Attempted by 56 students.
Show answer & explanation
Correct answer: B
Edges in E₁ have weight 0, while all other edges have weight 1.
Starting from v₁ ∈ V₁, a vertex u ∈ V₁ has shortest path cost 0 exactly when u is reachable from v₁ using only edges from E₁. Such paths are entirely inside the subgraph G₁.
Therefore:
- If every vertex of V₁ has distance 0 from v₁, then all vertices of G₁ are connected to v₁, so G₁ is connected.
- If some vertex of V₁ has distance greater than 0, then it is not reachable from v₁ using only E₁ edges, so G₁ is not connected.
Thus, the computed path costs allow us to infer whether G₁ is connected.
The costs do not give the total number of edges in shortest paths, and they do not show that V₁ forms a clique or that G₁ has no cycles.
Therefore, the correct answer is Option B.