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

Consider solving the following system of simultaneous equations using LU decomposition.

x1 + x2 $$-$$ 2x3 = 4

x1 + 3x2 $$-$$ x3 = 7

2x1 + x2 $$-$$ 5x3 = 7

where L and U are denoted as

$$L = \left( {\matrix{ {{L_{11}}} & 0 & 0 \cr {{L_{21}}} & {{L_{22}}} & 0 \cr {{L_{31}}} & {{L_{32}}} & {{L_{33}}} \cr } } \right),\,U = \left( {\matrix{ {{U_{11}}} & {{U_{12}}} & {{U_{13}}} \cr 0 & {{U_{22}}} & {{U_{23}}} \cr 0 & 0 & {{U_{33}}} \cr } } \right)$$

Which one of the following is the correct combination of values for L32, U33, and x1 ?

A
L32 = 2, U33 = $$ - {1 \over 2}$$, x1 = $$-$$ 1
B
L32 = 2, U33 = 2, x1 = $$ - {1 \over 2}$$
C
L32 = $$ - {1 \over 2}$$, U33 = 2, x1 = 0
D
L32 = $$ - {1 \over 2}$$, U33 = $$ - {1 \over 2}$$, x1 = 0
2
GATE CSE 2022
MCQ (More than One Correct Answer)
+2
-0

Consider a simple undirected weighted graph G, all of whose edge weights are distinct. Which of the following statements about the minimum spanning trees of G is/are TRUE?

A
The edge with the second smallest weight is always part of any minimum spanning tree of G.
B
One or both of the edges with the third smallest and the fourth smallest weights are part of any minimum spanning tree of G.
C
Suppose S $$\subseteq$$ V be such that S $$\ne$$ $$\phi$$ and S $$\ne$$ V. Consider the edge with the minimum weight such that one of its vertices is in S and the other in V \ S. Such an edge will always be part of any minimum spanning tree of G.
D
G can have multiple minimum spanning trees.
3
GATE CSE 2022
MCQ (More than One Correct Answer)
+2
-0

The following simple undirected graph is referred to as the Peterson graph.

GATE CSE 2022 Discrete Mathematics - Graph Theory Question 14 English

Which of the following statements is/are TRUE?

A
The chromatic number of the graph is 3.
B
The graph has a Hamiltonian path.
C

The following graph is isomorphic to the Peterson graph.

GATE CSE 2022 Discrete Mathematics - Graph Theory Question 14 English Option 3

D
The size of the largest independent set of the given graph is 3. (A subset of vertices of a graph form an independent set if no two vertices of the subset are adjacent.)
4
GATE CSE 2022
MCQ (Single Correct Answer)
+2
-0.67

Which of the properties hold for the adjacency matrix A of a simple undirected unweighted graph having n vertices?

A
The diagonal entries of A2 are the degrees of the vertices of the graph.
B
If the graph is connected, then none of the entries of An $$-$$ 1 + In can be zero.
C
If the sum of all the elements of A is at most 2(n $$-$$ 1), then the graph must be acyclic.
D
If there is at least a 1 in each of A's rows and columns, then the graph must be connected.
EXAM MAP