adplus-dvertising
frame-decoration

Question

If there are more than 1 topological sorting of a DAG is possible, which of the following is true.

a.

Many Hamiltonian paths are possible

b.

No Hamiltonian path is possible

c.

Exactly 1 Hamiltonian path is possible

d.

Given information is insufficient to comment anything

Answer: (b).No Hamiltonian path is possible

Engage with the Community - Add Your Comment

Confused About the Answer? Ask for Details Here.

Know the Explanation? Add it Here.

Q. If there are more than 1 topological sorting of a DAG is possible, which of the following is true.

Similar Questions

Discover Related MCQs

Q. Which of the given statement is true?

Q. For any two different vertices u and v of an Acyclic Directed Graph if v is reachable from u, u is also reachable from v?

Q. What is the value of the sum of the minimum in-degree and maximum out-degree of an Directed Acyclic Graph?

Q. In which of the following does a Directed Acyclic Word Graph finds its application in?

Q. What is time complexity to check if a string(length S1) is a substring of another string(length S2) stored in a Directed Acyclic Word Graph, given S2 is greater than S1?

Q. In which of the following case does a Propositional Directed Acyclic Graph is used for?

Q. Every Binary Decision Diagram is also a Propositional Directed Acyclic Graph.

Q. In a Propositional Directed Acyclic Graph Leaves maybe labelled with a boolean variable.

Q. Given Adjacency matrices determine which of them are PseudoGraphs?

i) {{1,0} {0,1}}

ii) {{0,1}{1,0}}

iii) {{0,0,1}{0,1,0}{1,0,0}}

Q. All undirected Multigraphs contain eulerian cycles.

Q. Determine the number of vertices for the given Graph or Multigraph?
G is a 4-regular Graph having 12 edges.

Q. Which of the following statement is true.

Q. Given Adjacency matrices determine which of them are PseudoGraphs?
i) {{1,0} {0,1}}

ii) {{0,1}{1,0}}

iii) {{0,0,1}{0,1,0}{1,0,0}}

Q. Possible number of labelled simple Directed, Pseudo and Multigarphs exist having 2 vertices?

Q. Which of the following is a HyperGraph, where V is the set of vertices, E is the set of edges?

Q. What would be the Incidence Matrix of the given HyperGraph?
V = {x,y,z} E = {{x,y}{y}{x,z}{z,y}}

Q. What is the degree sequence of the given HyperGraph, in non-increasing order.
V = {v1,v2,v3,v4,v5,v6} E = {{v1,v4,v5} {v2,v3,v4,v5} {v2} {v1} {v1,v6}}

Q. MultiGraphs having self-loops are called PseudoGraphs?

Q. Binary Decision Diagram is a type of __________

Q. In which of the following case does a Binary Decision Diagram is used for?