GATE CSE 2022 | Graph Theory Question 13 | Discrete Mathematics

PREVIOUS NEXT

GATE CSE 2022

MCQ (Single Correct Answer)

-0.67

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

The diagonal entries of A² are the degrees of the vertices of the graph.

If the graph is connected, then none of the entries of A^{n $$-$$ 1} + I_n can be zero.

If the sum of all the elements of A is at most 2(n $$-$$ 1), then the graph must be acyclic.

If there is at least a 1 in each of A's rows and columns, then the graph must be connected.

GATE CSE 2021 Set 2

Numerical

-0

In a directed acyclic graph with a source vertex s, the quality-score of a directed path is defined to be the product of the weights of the edges on the path. Further, for a vertex v other than s, the quality-score of v is defined to be the maximum among the quality-scores of all the paths from s to v. The quality-score of s is assumed to be 1.

GATE CSE 2021 Set 2 Discrete Mathematics - Graph Theory Question 14 English

The sum of the quality-scores of all the vertices in the graph shown above is ______

Your input ____

GATE CSE 2021 Set 1

MCQ (More than One Correct Answer)

-0.67

An articulation point in a connected graph is a vertex such that removing the vertex and its incident edges disconnects the graph into two or more connected components.

Let T be a DFS tree obtained by doing DFS in a connected undirected graph G. Which of the following option is/are correct?

If u is an articulation point in G such that x is an ancestor of u in T and y is a descendent of u in T, then all paths from x to y in G must pass through u.

Root of T is an articulation point in G if and only if it has 2 or more children.

Root of T can never be an articulation point in G.

A leaf of T can be an articulation point in G.

GATE CSE 2021 Set 1

MCQ (Single Correct Answer)

-0.67

Let G be a group order 6, and H be a subgroup of G such that 1 < |H| < 6. Which one of the following options is correct?

G is always cyclic, but H may not be cyclic.

G may not be cyclic, but H is always cyclic.

Both G and H are always cyclic.

Both G and H may not be cyclic.

PREVIOUS NEXT