0 \;\text " or "\; P_{i j}>0, \;\text " where "\; P=M^2 ; 0, \;\text " otherwise "\;}.Which one of the following statements is true?">

Test Index

GATE Computer Science (CS) 2021 Shift 1 Solved Paper

© examsnet.com

Question : 46

Total: 65

Let G = (V, E) be an undirected unweighted connected graph. The diameter of G is defined as:
diam(G) = max‌limitsu,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
Nij={

1‌ if ‌Mij>0‌ or ‌Pij>0	‌ where ‌P=M2
0	‌ 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)

Go to Question:

Prev Question

Next Question