

MCQOPTIONS
Saved Bookmarks
1. |
Let G = (V, E) be an undirected unweighted connected graph. The diameter of G is defined as:diam(G) = \(\displaystyle\max_{u, x\in V}\) {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} =\left\{ {\begin{array}{*{20}{c}} {1 \ \ \text{if} \ \ {M_{ij}} > 0 \ \ \text{or} \ \ P_{ij} > 0, \ \text{where} \ \ P = {M^2}}\\ {0, \ \ \ \ \ \text{otherwise}} \end{array}} \right.\)Which one of the following statements is true? |
A. | diam(G) < diam(G2) ≤ diam(G) |
B. | \(\left\lceil {diam(G)/2} \right\rceil \) < diam(G2) < diam(G) |
C. | diam(G2) ≤ \(\left\lceil {diam(G)/2} \right\rceil \) |
D. | diam(G2) = diam(G) |
Answer» D. diam(G2) = diam(G) | |