CODEWITHSUNDEEP
algorithmgraph
Pinkoo
Pinkoo

Reputation: 127

Topological Sorting for a Cycle

I studied from different sources that If a Hamiltonian path exists, the topological sort order is unique; no other order respects the edges of the path. If we consider a simple cycle of a directed graph , a Hamiltonian path exists but a topological ordering does not exist as every node requires the other node to be visited before it . Is there anything I missed in this or is it an exception or any other thing . Thanks in advance .

Upvotes: 2

Views: 553

Answers (2)

Ami Tavory
Ami Tavory

Reputation: 76396

IIUC, you're quoting partially. Take, e.g., the Wiki entry on this:

If a topological sort has the property that all pairs of consecutive vertices in the sorted order are connected by edges, then these edges form a directed Hamiltonian path in the DAG. If a Hamiltonian path exists, the topological sort order is unique; no other order respects the edges of the path. 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.

So your quote

If a Hamiltonian path exists

means "if a Hamiltonian path exists in the topological sort".

Thus your example's condition is void in this context, because the graph is not a DAG, and the topological sort simply does not exist

Upvotes: 3

David Eisenstat
David Eisenstat

Reputation: 65508

The proper theorem statement is that, if a Hamiltonian path exists and a topological order exists, then that topological order is unique. This is proved by the existence of a backward arc on the Hamiltonian path with respect to every other topological order.

Upvotes: 3

Related Questions