Problem:
When does a directed graph have a unique topological ordering?
Solution:
(Option 1) Whenever it is directed acyclic
This is wrong 1->2, 3 has two topological order
(Option 2) Whenever it has a unique cycle
This is wrong, any graph with a cycle do not have a topological order.
(Option 3) Whenever it is a complete directed graph
A complete directed graph of size > 1 will necessarily have cycle, so no topological order at all.
(Option 4) None of the other options
This is the only possible solution now, and that's correct!
When does a directed graph have a unique topological ordering?
Solution:
(Option 1) Whenever it is directed acyclic
This is wrong 1->2, 3 has two topological order
(Option 2) Whenever it has a unique cycle
This is wrong, any graph with a cycle do not have a topological order.
(Option 3) Whenever it is a complete directed graph
A complete directed graph of size > 1 will necessarily have cycle, so no topological order at all.
(Option 4) None of the other options
This is the only possible solution now, and that's correct!
No comments:
Post a Comment