COMPUTER SCIENCE AND ENGINEERING
COMPILER DESIGN
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
|
|
Many Hamiltonian paths are possible
|
|
|
No Hamiltonian path is possible
|
|
|
Exactly 1 Hamiltonian path is possible
|
|
|
Given information is insufficient to comment anything
|
Detailed explanation-1: -If there are more than 1 topological sorting of a DAG is possible, which of the following is true. Explanation: For a Hamiltonian path to exist all the vertices must be connected with a path, had that happened there would have been a unique topological sort.
Detailed explanation-2: -Conversely, if a topological sort does not form a Hamiltonian path, the DAG will have two or more valid topological orderings, for in this case it is always possible to form a second valid ordering by swapping two consecutive vertices that are not connected by an edge to each other.
Detailed explanation-3: -Number of different topological orderings possible = 6.
Detailed explanation-4: -There can be multiple topological ordering for a Directed Acyclic Graph. In order to have a topological sorting, the graph must not contain any cycles and it must be directed i.e. the graph must be a DAG.
Detailed explanation-5: -A topological sort of a DAG G = ( V, E ) is a linear ordering of v V such that if ( u, v ) E then u appears before v in this ordering. If G is cyclic, no such ordering exists: Topological sort can also be viewed as placing all the vertices along a horizontal line so that all directed edges go from left to right.