Discrete Mathematics Multiple Choice Questions 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
Answer: b
Clarification: 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’)
Answer: a
Clarification: 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
Answer: a
Clarification: 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
Answer: d
Clarification: 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
Answer: c
Clarification: 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
Answer: d
Clarification: 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
Answer: c
Clarification: 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
Answer: a
Clarification: 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
Answer: b
Clarification: 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
Answer: c
Clarification: 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.