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]

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: