Uniqueness
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. Therefore, it is possible to test in polynomial time whether a unique ordering exists, and whether a Hamiltonian path exists, despite the NP-hardness of the Hamiltonian path problem for more general directed graphs (Vernet & Markenzon 1997).
Read more about this topic: Topological Sorting
Famous quotes containing the word uniqueness:
“Somehow we have been taught to believe that the experiences of girls and women are not important in the study and understanding of human behavior. If we know men, then we know all of humankind. These prevalent cultural attitudes totally deny the uniqueness of the female experience, limiting the development of girls and women and depriving a needy world of the gifts, talents, and resources our daughters have to offer.”
—Jeanne Elium (20th century)
“Until now when we have started to talk about the uniqueness of America we have almost always ended by comparing ourselves to Europe. Toward her we have felt all the attraction and repulsions of Oedipus.”
—Daniel J. Boorstin (b. 1914)