*(Guest post by Andrew Muraco)*

**Directed Graphs**

- Model asymmetric relationships
*Precedence relationships*: needs to be done before means 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.”

- : directed graph
- Topological ordering: , if for every edge then .

**Proposition:** If has a topological ordering then 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 ? They are all outgoing, so it is the top of the topological ordering; no incoming edge. (*Remember: *need not be a connected graph!)

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

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

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

*Algorithm idea:* If is a DAG, then is a DAG (Cannot add a cycle by deleting edges)

*Algorithm:* : given as adj list

- Find a vertex that has only outgoing edges. []
- Delete from to get []
- Output followed by topological order of . (compute recursively)

[Repeat times] Total = [ in book]

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

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

## Leave a Reply