Prerequisite for graphs with unique topological sorting

Suppose that the graph in question is a DAG (directed acyclic graph).

Question : can I conclude that such a graph will have a unique topological form if and only if only one of its vertices does not have incoming edges?

In other words, has only one vertex without its boundaries (but not enough) to generate a unique topological sort?

+4
source share
5 answers

Haaaaa, approx. sorry for misunderstanding.

In this case, I assume that you are right, here is a sketch of the proof:

We have a unique topology. sot => We have only one vertex, which is to be highlighted first => For each vertex, except for one, we should not first set => For each vertex, except for one, we have inconsistent edges.

Hope I answered your question now ....

+4
source

A topological view will be unique if and only if there is a directed edge between each pair of consecutive vertices in a topological order (i.e., the digraph has a Hamiltonian path ). A source

The Hamiltonian path simply means that the path between two vertices will visit only each vertex once, this does not mean that one vertex should not have any incoming edges. You can have a Hamiltonian path, which is actually a cycle . This would still create a unique topological sort (of course, this would be a loop if that matters to you).

Hope this helps

+9
source

No! The graph below has only one vertex without incoming edges and has 2 possible solutions.

1 -> 2 3 -> 4 3 -> 1 4 -> 2 

Two solutions:

 2 0 3 1 2 3 0 1 
+1
source

Yes, you can say that as a necessary condition, as if there were several nodes with in-degree = 0, then there would be no Hamiltonian trajectory, therefore, there would be no unambiguous topological order. Only for initial node graphs (in-degree = 0) will not have an incoming edge, the remaining vertices MUST have an incoming edge from their topological ancestor, that is, the node immediately before the current node in topological order, If each consecutive node in the topological order does not have an edge then DAG will NOT have a unique order.

0
source

Someone gave an answer. Here I just want to give you a counter example: G = {(1,2), (1,3)}. In this case, there are 2 valid topological types: 1,2,3 and 1,3,2

0
source

Source: https://habr.com/ru/post/1380841/


All Articles