Discrete Mathematics Questions and Answers – Trees – Cycles

«
»

This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on “Trees – Cycles”.

1. If two cycle graphs Gm and Gn are joined together with a vertex, the number of spanning trees in the new graph is ______
a) m+n-1
b) m-n
c) m*n
d) m*n+1
View Answer

Answer: c
Explanation: As there are n possible edges to be removed from G and m edges to be removed from G and the rest from a spanning tree so the number of spanning tree in the new graph is m*n.
advertisement

2. For an n-vertex undirected graph, the time required to find a cycle is ____________
a) O(n)
b) O(n2)
c) O(n+1)
d) O(logn)
View Answer

Answer: a
Explanation: The existence of a cycle in directed and undirected graphs can be determined by depth-first search (DFS) of the graph finds an edge that points to an ancestor of the current vertex. In an undirected graph, finding any already visited vertex will indicate a back edge. All the back edges which DFS skips over are part of cycles. In the case of undirected graphs, only O(n) time is required to find a cycle in an n-vertex graph, since at most n − 1 edges can be tree edges.

3. A binary cycle space forms a ______ over the two element field.
a) triangular graph
b) vector space
c) binary tree
d) hamiltonian graph
View Answer

Answer: b
Explanation: The term cycle refers to an element of the cycle space of a graph. There are many cycle spaces. The most common is the binary cycle space, which contains the edge sets that have even degrees at every vertex and it forms a vector space over the two-element field.

4. If G is a simple graph with n-vertices and n>=3, the condition for G has a Hamiltonian circuit is __________
a) the degree of each vertex is at most n/2
b) the degree of each vertex is equal to n
c) the degree of every vertex is at least n+1/2
d) the degree of every vertex in G is at least n/2
View Answer

Answer: d
Explanation: A simple circuit in a graph G that passes through every vertex exactly once is called a Hamiltonian circuit. If there is a vertex of degree one in a graph then it is impossible for it to have a Hamiltonian circuit. If G is a simple graph with n-vertices and n>=3 such that the degree of every vertex in G is at least n/2, then G has a Hamiltonian circuit.

5. What is a separable graph?
a) A disconnected graph by deleting a vertex
b) A disconnected graph by removing an edge
c) A disconnected graph by removing one edge and a vertex
d) A simple graph which does not contain a cycle
View Answer

Answer: a
Explanation: By deletion of a vertex the graph is disconnected and the graph is called separable graph and the vertex is called cut vertex.
advertisement

6. How many edges are there in a complete graph of order 9?
a) 35
b) 36
c) 45
d) 19
View Answer

Answer: b
Explanation: In a complete graph of order n, there are n*(n-1) number of edges and degree of each vertex is (n-1). Hence, for a graph of order 9 there should be 36 edges in total.

7. How many cycles are there in a wheel graph of order 5?
a) 6
b) 10
c) 25
d) 7
View Answer

Answer: d
Explanation: In a cycle of a graph G if we join all the vertices to the centre point, then that graph is called a wheel graph. There is always a Hamiltonian cycle in a wheel graph and there are n2-3n+3 cycles. So, for order 5 the answer should be 7.

8. The time complexity to find a Eulerian path in a graph of vertex V and edge E is _____________
a) O(V2)
b) O(V+E-1)
c) O(V+E)
d) O(E+1)
View Answer

Answer: c
Explanation: An undirected graph has Eulerian Path if the following two conditions are true: -a) All vertices with a non-zero degree are connected. A graph of vertices with zero degrees don’t belong to Eulerian Cycle or Path, b) If two vertices have odd degree and all other vertices have even degree. Thus, the time to find whether a graph has a Eulerian path or not is O(V+E) with V vertices and E edges.

9. The time complexity to find shortest distances by using Dijkstra’s algorithm is __________
a) O(E2)
b) O(V+1-E)
c) O(V+E)
d) O(E+VlogV)
View Answer

Answer: d
Explanation: Time complexity of finding shortest distance can be O(E + VLogV) using Fibonacci Heap. The reason is that Fibonacci Heap takes O(1) time for decrease-key operation while Binary Heap takes O(logn) time.
advertisement

10. Topological sorting of a graph represents _______ of a graph.
a) linear probing
b) linear ordering
c) quadrilateral ordering
d) insertion sorting
View Answer

Answer: b
Explanation: Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering. If the graph is not a DAG, topological sorting for a graph is not possible.

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.

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn