This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Eulerian Tour”.
1. Which of the following refers to the circuit that uses every edge exactly once, also starts and ends at the same vertex?
a) Hamiltonian circuit
b) Eulerian path
c) Eulerian tour
d) Hamiltonian path
View Answer
Explanation: Eulerian tour is also called eulerian circuit or eulerian cycle. In a graph G, an eulerian cycle is a cycle that uses all the edges only once. The eulerian tour is a closed trail, which covers all the edges of the graph, also starts and ends at the same vertex.
2. Which algorithm can be used to find an eulerian cycle in a graph?
a) Fleury’s algorithm
b) Tarjan’s algorithm
c) Hirschberg’s algorithm
d) Hungarian algorithm
View Answer
Explanation: In a given connected graph G, fleury’s algorithm can be used to find an eulerian cycle. Bridges are the edges that connect two connected components of the graph. The basic idea of this algorithm is to cross the bridge edge as the last edge we have to cross.
3. For an euler tour of a tree, how many vertices are required to store euler tour?
a) 2 * V – 1
b) 2 * V + 1
c) 2 * V – E + 1
d) 2 * V
View Answer
Explanation: To find an euler tour in a tree with V vertices, we use DFS traversal to traverse the tree in such a way that every vertex, when visited is added to the tour. It starts from the root and moves towards the child or starts from the child vertex, returning to the root. To store euler tour, it requires 2 * V – 1 vertices.
4. Which among the following is the eulerian tour for the graph given below?
a) ABCDEC
b) ABCECBA
c) ACEDCA
d) ABCEDCA
View Answer
Explanation: In a graph G, an eulerian circuit or eulerian tour covers all the edges of the graph. The degree of all the vertices must be even as well as the edges shouldn’t repeat. Hence, the appropriate eulerian tour is A→B→C→E→D→C→A.
5. An undirected graph has an eulerian cycle if and only if all the vertices have an odd degree.
a) True
b) False
View Answer
Explanation: In an undirected graph, an eulerian cycle is a closed trail, which covers all the edges of the graph. It starts from one vertex and ends at the same vertex. Hence, if all the vertices have an even degree, then the eulerian tour exists for that graph.
6. Consider the given pseudocode for eulerizing a graph. Which of the following best suits the blank?
Pick up all the vertices of _______ Repeat edges between the vertices until the graph has no odd degree Repeat only pre-existing edges
a) Odd degree
b) Even degree
c) At least one degree
d) At most one degree
View Answer
Explanation: In a graph, the number of odd degree vertices will always be even. Eulerizing a graph is a process to make the degree of all the vertices even in the graph. It is done by adding a duplicate copy of edges to the odd degree vertices in the previous graph.
7. The graph which contains eulerian tour, is called an euler graph.
a) True
b) False
View Answer
Explanation: A trail in a graph is an alternate sequence of vertices and edges where vertices can be repeated but edges can’t. If a connected graph G contains a trail, whose starting and ending vertex are the same and covers all the edges of the graph (eulerian tour) is called an euler graph.
8. Which among the following best represents the time complexity to find an euler tour of a tree?
a) O(n)
b) O(1)
c) O(n2)
d) O(n log n)
View Answer
Explanation: A connected graph with N vertices and N – 1 edges is called a tree. For all the pair of vertices, there is only one edge between them. Starting from the root it will use a DFS traversal to traverse the tree and add the vertex every time it visits and reaches back to the root. Hence, if the tree is represented by an adjacency list, the time complexity to find an euler tour of a tree will be O(n).
Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.
To practice all areas of Data Structures & Algorithms, 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 Design and Analysis of Algorithms Books
- Practice Programming MCQs
- Check Programming Books
- Apply for Computer Science Internship
