0 like 0 dislike
35 views
Prove that for each DAG there is a topological ordering
| 35 views

0 like 0 dislike

Proof.

By induction, we need to show that in each DAG, there is a node without any ancestors.

Start with any node and move to one of its parents (if there are any).

You will never visit a parent that you have seen before (if you did there had been a directed cycle).

After at most $p-1$ steps you reach a node without any parent.

by Platinum (141,884 points)

0 like 0 dislike
0 like 0 dislike
0 like 0 dislike
1 like 0 dislike
0 like 0 dislike
1 like 0 dislike
1 like 0 dislike
0 like 0 dislike
1 like 0 dislike