Posted by: atri | October 12, 2009

## Lect 16: Topological Ordering

(Guest post by Andrew Muraco)

Directed Graphs

• Model asymmetric relationships
• Precedence relationships: $u$ needs to be done before $v$ means $(u,v)$ edge
• Adjacency matrix is not symmetric
• Each vertex has two lists in Adjacency list rep.

Directed Acyclic Graph (DAG)

• No directed cycles
• Precedence relationship are consistent

Topological Ordering of a DAG

Order the vertices so that all edges go “forward.”

• $G$: directed graph
• Topological ordering: $v_1,v_2,\dots,v_n$, if for every edge $(v_i,v_j)$ then $i < j$.

Proposition: If $G$ has a topological ordering then $G$ is a DAG
Proof by Picture: No cycle possible as there is no way to “go back.” (formal proof + picture in book)

What can we say about edges incident on $v_1$? They are all outgoing, so it is the top of the topological ordering; no incoming edge. (Remember: $G$ need not be a connected graph!)

Theorem: If $G$ is a DAG then it has a topological ordering.

Proof idea: Present an O(m+n) time algorithm to compute topological ordering.

Lemma: If $G$ is a DAG, then there exists a $v$ such that $v$ has no incoming edge.

Algorithm idea: If $G$ is a DAG, then $G\setminus \{v\}$ is a DAG (Cannot add a cycle by deleting edges)

Algorithm: $G$: given as adj list

1. Find a vertex $v$ that has only outgoing edges. [$O(n)$]
2. Delete $v$ from $G$ to get $G' = G\setminus \{v\}$ [$O(n)$]
3. Output $v$ followed by topological order of $G'$. (compute recursively)

[Repeat $n$ times] Total = $O(n^2)$ [ $O(n+m)$ in book]

Proof (idea) for Lemma: By contradiction. Assume every vertex has an incoming edge and show $G$ has a cycle.

[Read Sec 3.6 from the book to the parts we did not finish. –Atri]