GATE 2021 CS (CS1) – Question 46
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?
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
- GATE 2021 CS (CS1) Q51
- GATE 2020 CS Q41
- GATE 2020 CS Q50
- GATE 2020 CS Q59
- GATE 2019 CS Q48
- GATE 2018 CS Q40
All Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions →