1
GATE CSE 2021 Set 1
MCQ (Single Correct Answer)
+2
-0.67

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)
2
GATE CSE 2021 Set 1
Numerical
+2
-0

Consider the following matrix.

$$\left( {\begin{array}{*{20}{c}} 0&1&1&1\\ 1&0&1&1\\ 1&1&0&1\\ 1&1&1&0 \end{array}} \right)$$

The largest eigenvalue of the above matrix is ______

Your input ____
3
GATE CSE 2021 Set 1
Numerical
+1
-0
In an undirected connected planar graph G, there are eight vertices and five faces. The number of edges in G is ______
Your input ____
4
GATE CSE 2021 Set 1
MCQ (More than One Correct Answer)
+1
-0
In the context operating systems, which of the following statements is/are correct with respect to paging?
A
Paging incurs memory overheads.
B
Paging helps solve the issue of external fragmentation.
C
Page size has no impact on internal fragmentation.
D
Multi-level paging is necessary to support pages of different sizes.
EXAM MAP