INTRODUCTION TO COMPILER DESIGN
OVERVIEW OF COMPILERS
|
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: -5. 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: -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-3: -In a DAG, if there is a Hamiltonian path, the topological sort order of this DAG will then be unique. Otherwise, if a topological sort does not form a Hamiltonian path, this DAG will then have more than one valid topological orderings.