In: Computer Science
A DAG is a directed graph that contains no directed cycles.
Define G = (V, E) in which V is the set of all nodes as {v1, v2, ..., vi , ...vn} and E is the set of edges E = {ei,j = (vi , vj ) | vi , vj ∈ V} .
A topological order of a directed graph G = (V, E) is an ordering of its nodes as {v1, v2, ..., vi , ...vn} so that for every edge (vi , vj ) we have i < j.
There are several lemmas can be inferred from the definition of DAG. One lemma is: if G is a DAG, then G has a node with no incoming edges. Given the above lemma, prove the following two lemmas:
If the graph G is a DAG, then G has a topological ordering.
If the graph G has a topological order, then G is a DAG.