The GATE Grind

GATE 2021 CS (CS1) – 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

$G_2$ has an edge between $u,v$ whenever their distance in $G$ is 1 or 2, i.e. whenever $M_{uv}>0$ or $(M^2)_{uv}>0$.

A shortest path in $G$ of length $d$ can be shortened: every two consecutive edges of $G$ become one edge of $G_2$. So a path of $d$ edges in $G$ becomes a path of $\lceil d/2\rceil$ edges in $G_2$. Hence $\operatorname{diam}(G_2)\le\lceil\operatorname{diam}(G)/2\rceil$. Option (A) is the one that always holds..

More Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions

All Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions →