This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on “Graphs – Diagraph”.
1. A directed graph or digraph can have directed cycle in which ______
a) starting node and ending node are different
b) starting node and ending node are same
c) minimum four vertices can be there
d) ending node does not exist
View Answer
Explanation: If the start node and end node are same in the path of a graph then it is termed as directed cycle i.e, c0 = cn. For instance, a c b a is a simple cycle in which start and end nodes are same(a). But, a c b b a is not a simple cycle as there is a loop <b,b>.
2. Let, D = <A, R> be a directed graph or digraph,then D’ = <A’, R’> is a subgraph if ___________
a) A’ ⊂ A and R’ = R ∩ (A’ x A’)
b) A’ ⊂ A and R ⊂ R’ ∩ (A’ x A’)
c) R’ = R ∩ (A’ x A’)
d) A’ ⊆ A and R ⊆ R’ ∩ (A’ x A’)
View Answer
Explanation: A directed graph or digraph is an ordered pair D<A, R> where A(is a set of nodes of D) is a set and R(the elements of R are the arcs of D) is a binary relation on A. The relation R is called the incidence relation on D. Now, a digraph is a subgraph of D if i)A’ ⊂ A and ii)R’ = R ∩ (A’ x A’). If D’ D, D’ is a proper subgraph of D.
3. The graph representing universal relation is called _______
a) complete digraph
b) partial digraph
c) empty graph
d) partial subgraph
View Answer
Explanation: Consider, A is a graph with vertices {a, b, c, d} and the universal relation is A x A. The graph representing universal relation is called a complete graph and all ordered pairs are present there.
4. What is a complete digraph?
a) connection of nodes without containing any cycle
b) connecting nodes to make at least three complete cycles
c) start node and end node in a graph are same having a cycle
d) connection of every node with every other node including itself in a digraph
View Answer
Explanation: Every node should be connected to every other node including itself in a digraph is the complete digraph. Now, graphs are connected, strongly connected and disconnected
5. Disconnected components can be created in case of ___________
a) undirected graphs
b) partial subgraphs
c) disconnected graphs
d) complete graphs
View Answer
Explanation: By the deletion of one edge from either connected or strongly connected graphs the graph obtained is termed as a disconnected graph. It can have connected components separated by the deletion of the edges. The edge that has to be deleted called cut edge.
6. A simple graph can have _______
a) multiple edges
b) self loops
c) parallel edges
d) no multiple edges, self-loops and parallel edges
View Answer
Explanation: If a graph say G = <V, E> has no parallel or multiple edges and no self loops contained in it is called a simple graph. An undirected graph may have multiple edges and self-loops.
7. Degree of a graph with 12 vertices is _______
a) 25
b) 56
c) 24
d) 212
View Answer
Explanation: Number of edges incident on a graph is known as degree of a vertex. Sum of degrees of each vertex is called total degree of the graph. Total degree = 2 * number of vertices. So, if there are 24 vertices then total degree is 24.
8. In a finite graph the number of vertices of odd degree is always ______
a) even
b) odd
c) even or odd
d) infinite
View Answer
Explanation: In any finite graph, sum of degree of all the vertices = 2 * number of edges.
Sum of degree of all the vertices with even degree + sum of degree of all the vertices with odd degree = 2 * number of edges. Now, even number + sum of degree of all the vertices with odd degree = even number. It is possible if and only if number of odd degree vertices are even.
9. An undirected graph has 8 vertices labelled 1, 2, …,8 and 31 edges. Vertices 1, 3, 5, 7 have degree 8 and vertices 2, 4, 6, 8 have degree 7. What is the degree of vertex 8?
a) 15
b) 8
c) 5
d) 23
View Answer
Explanation: Vertices 1, 3, 5, 7 have degree 8 and vertices 2, 4, 6, 8 have degree 7. By definition, sum of degree= 2 * No of edges
Let x = degree of vertex 8
8 + 7 + 8 + 7 + 8 + 7 + 8 + x = 2 * 31
53 + x = 61
x = 8
Hence, degree of vertex 8 is 8.
10. G is an undirected graph with n vertices and 26 edges such that each vertex of G has a degree at least 4. Then the maximum possible value of n is ___________
a) 7
b) 43
c) 13
d) 10
View Answer
Explanation: Let m be min degree and M be a max degree of a graph, then m ≤ 2E/V ≤ M. Here, m=4, E=26, v=?
So, 4 ≤ (2*26)/V
V ≤ (52/4)
V ≤ 13 ⇒ V = 13.
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
- Check Discrete Mathematics Books
- Apply for Computer Science Internship
- Check Computer Science Books
- Practice Information Technology MCQs
