The GATE Grind

GATE 2021 CS – Question 46

Algorithms · Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths · 2 marks · Multiple choice

Let $G=(V,E)$ be an undirected unweighted connected graph. The diameter of $G$ is defined as $\text{diam}(G)=\max_{u,v\in V}\{\text{length of shortest path between } u \text{ and } v\}$. Let $M$ be the adjacency matrix of $G$. Define graph $G_2$ on the same set of vertices with adjacency matrix $N$, where $N_{ij}=1$ if $M_{ij}>0$ or $P_{ij}>0$, where $P=M^2$, and $N_{ij}=0$ otherwise. Which one of the following statements is true?

  1. $\text{diam}(G_2) \le \lceil \text{diam}(G)/2 \rceil$
  2. $\lceil \text{diam}(G)/2 \rceil < \text{diam}(G_2) < \text{diam}(G)$
  3. $\text{diam}(G_2) = \text{diam}(G)$
  4. $\text{diam}(G) < \text{diam}(G_2) \le 2\,\text{diam}(G)$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) $\text{diam}(G_2) \le \lceil \text{diam}(G)/2 \rceil$

Explanation

G2 has an edge between vertices at distance 1 or 2 in G, so each step covers up to 2 hops. A path of length d in G shrinks to length $\lceil d/2 \rceil$ in G2.