Discrete Mathematics (3140708) MCQs

MCQs of Graphs

Showing 21 to 30 out of 36 Questions
1 2 3 4
21.
Reachability is _____ relation. (1). reflexive (2). symmetric (3). transitive (4). anti symmetric
(a) 1 & 2
(b) 1 & 3
(c) 3 & 4
(d) 2 & 4
Answer:

Option (b)

22.
If v is reachable from u then d does not satisfy _____.
(a) d<u, v>⩾0
(b) d<u, u>=0
(c) d<u, v>+d<v, w>⩾d<u, w>
(d) d<u, v>+d<v, w>≤d<u, w>
Answer:

Option (a)

23.
Which of the following is incorrect?
(a) d<u, v>≠d<v, u>
(b) d<u, v>=d<v, u>
(c) d<u, u>=0
(d) d<u, u>≥0
Answer:

Option (a)

24.

The sum of each elements in the row of adjacency matrix indicates _____ of the corresponding vertex.

(a)

indegree
(b)

outdegree
(c)

total degree
(d)

diameter of graph
Answer:

Option (b)

25.
which of the following is the formula of Warshall's algorithm?
(a) Pk[i, j]=Pk-1[i, j]∧(Pk-1[i, k]∧Pk-1[k, j])
(b) Pk[i, j]=Pk-1[i, j]∨(Pk-1[i, k]∧Pk-1[k, j])
(c) Pk[i, j]=Pk-1[i, j]∧(Pk-1[i, k]∨Pk-1[k, j])
(d) Pk[i, j]=Pk-1[i, j]∨(Pk-1[i, k]∨Pk-1[k, j])
Answer:

Option (b)

26.
Which of the following is incorrect?
(a) A digraph which does not have any cycle is called acyclic graph.
(b) A tree is a connected acyclic graph.
(c) A set of trees is called a forest.
(d) A directed tree which has a node with out degree 0 is called root of a tree.
Answer:

Option (d)

27.
The level of the root of a directed tree is _____.
(a) 0
(b) 1
(c) 2
(d) 3
Answer:

Option (a)

28.

In a directed tree the out degree of every vertex is less than or equal to 2 is called _____.

(a)

a binary tree
(b)

a full binary tree
(c)

m-ary tree
(d)

full m-ary tree
Answer:

Option (a)

29.

The vertex which is reachable from u is called _____ of u.

(a)

son
(b)

descendant
(c)

root
(d)

simple vertex
Answer:

Option (b)

30.
Which of the following is not a type of tree traversal?
(a) pre-order
(b) in-order
(c) post-order
(d) multi-order
Answer:

Option (d)

Showing 21 to 30 out of 36 Questions
1 2 3 4