GATEverse Practice, past papers & mock tests
GATE 2021 · Set-1
AlgorithmsGraph AlgorithmshardMCQ2 marks
Let G = (V,E) be an undirected unweighted connected graph. The diameter of G is defined as: diam(G) = max over u,v in V of {the length of shortest path between u and v}. Let M be the adjacency matrix of G. Define graph G2 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 0 otherwise. Which one of the following statements is true?
Save your progress

Related Algorithms PYQs