Let G = (V, E) be an undirected unweighted connected graph. The diameter of G is defined as: diam(G) = \max \limits_{u,x \in V} {the length of shortest path between u 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_{i j}={\\begin{array}{c}1 \\\\text{ if }\\ M_{i j\end{array}>0 \text{ or } P_{i j}>0, \text{ where } P=M^2 ; 0, \text{ otherwise }}. Which one of the following statements is true?

Correct Answer is : diam(G2) ≤ ⌊diam(G)∕2⌋

diam(G) < diam(G 2 ) ≤ diam(G)

\lfloor \diam(G)\/ 2 \rfloor < diam(G 2 ) < diam(G)

diam(G 2 ) ≤ \lfloor diam(G)\/ 2 \rfloor

GATE Computer Science (CS) 2021 Shift 1 Solved Paper

Question : 46 of 65

Marks: +1, -0

Let G = (V, E) be an undirected unweighted connected graph. The diameter of G is defined as:
diam(G) =

\max \limits_{u,x ∈ V}

{the length of shortest path between u and v}
Let M be the adjacency matrix of G.
Define graph G₂ on the same set of vertices with adjacency matrix N, where

N_{i j}={\{\table 1 \;\text " if "\; M_{i j}>0 \;\text " or "\; P_{i j}>0, \;\text " where "\; P=M^2 ; 0, \;\text " otherwise "\;}.

Which one of the following statements is true?

diam(G) < diam(G₂) ≤ diam(G)
$⌊\diam(G)\/ 2 ⌋$ < diam(G₂) < diam(G)
diam(G₂) ≤ $⌊diam(G)\/ 2 ⌋$
diam(G₂) = diam(G)

Validate

Go to Question:

Prev Question

Next Question