This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on “Properties of Tree”.
1. An undirected graph G which is connected and acyclic is called ____________
a) bipartite graph
b) cyclic graph
c) tree
d) forest
View Answer
Explanation: An undirected graph G which is connected and acyclic is termed as a tree. G contains no cycles and if any edge is added to G a simple cycle is formed.
2. An n-vertex graph has ______ edges.
a) n2
b) n-1
c) n*n
d) n*(n+1)/2
View Answer
Explanation: Suppose G is a connected graph which has no cycles. Every subgraph of G includes at least one vertex with zero or one incident edges. It has n vertices and n-1 edges. Generally, the order-zero graph is not considered to be a tree.
3. What is a star tree?
a) A tree having a single internal vertex and n-1 leaves
b) A tree having n vertices arranged in a line
c) A tree which has 0 or more connected subtrees
d) A tree which contains n vertices and n-1 cycles
View Answer
Explanation: A star tree of order n is a tree with as many leaves as possible or in other words a star tree is a tree that consists of a single internal vertex and n-1 leaves. However, an internal vertex is a vertex of degree at least 2.
4. A polytree is called _______________
a) directed acyclic graph
b) directed cyclic graph
c) bipartite graph
d) connected graph
View Answer
Explanation: A directed acyclic graph is known as a polytree whose underlying undirected graph is a tree. In other words, a directed tree is a directed graph which would be tree if the directions on the edges were ignored.
5. The tree elements are called __________
a) vertices
b) nodes
c) points
d) edges
View Answer
Explanation: Every tree element is called a node and the lines connecting the elements are called branches. A finite tree structure has a member that has no superior and is called the “root” Or root node. Nodes that have no child are called leaf nodes.
6. In an n-ary tree, each vertex has at most ______ children.
a) n
b) n4
c) n*n
d) n-1
View Answer
Explanation: An n-ary tree is a rooted tree in which each vertex has at most n children. 2-ary trees are termed as binary trees, 3-ary trees are sometimes called ternary trees.
7. A linear graph consists of vertices arranged in a line.
a) false
b) true
c) either true or false
d) cannot determined
View Answer
Explanation: A linear graph also known as a path graph is a graph which consists of k vertices arranged in a line, so that vertices from i and i+1 are connected by an edge for i=0,…, k-1.
8. Two labeled trees are isomorphic if ____________
a) graphs of the two trees are isomorphic
b) the two trees have same label
c) graphs of the two trees are isomorphic and the two trees have the same label
d) graphs of the two trees are cyclic
View Answer
Explanation: The number of labeled trees of k number of vertices is kn-2. Two labeled trees are isomorphic if their graphs are isomorphic and the corresponding points of the two trees have the same labels.
9. A graph which consists of disjoint union of trees is called ______
a) bipartite graph
b) forest
c) caterpillar tree
d) labeled tree
View Answer
Explanation: A forest is an undirected acyclic graph in which all the connected components are individual trees. This graph contains a disjoint union of trees.
10. What is a bipartite graph?
a) a graph which contains only one cycle
b) a graph which consists of more than 3 number of vertices
c) a graph which has odd number of vertices and even number of edges
d) a graph which contains no cycles of odd length
View Answer
Explanation: A graph is called a bipartite graph if and only if it contains no cycle of odd length. Every tree is a bipartite graph and a median graph.
Sanfoundry Global Education & Learning Series – Discrete Mathematics.
To practice all areas of Discrete Mathematics, here is complete set of 1000+ Multiple Choice Questions and Answers.
If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]
- Practice Computer Science MCQs
- Apply for Computer Science Internship
- Practice BCA MCQs
- Practice Information Technology MCQs
- Apply for BCA Internship
