Announcements
Announcements
Homework 1 Due on Friday
Note
“Polynomial time” means time O(nk) for some k > 0.
[for graph algorithms it means O((|V|+|E|)k)]
Last Time
Pre- and Post- orderings
Keep track of execution of DFS
Preorder when find a new vertex
Postorder when finish with vertex
Directed graphs
Edges have direction
Dependency and topological ordering
Order vertices so that for each edge (v,w) v comes before w
Today
DAGs
Topological Sort
Strongly Connected Components
Cycles
Definition: A cycle in a directed graph is a sequence of vertices v1, v2, v3,…,vn so that there are edges
(v1,v2), (v2,v3),…,(vn-1,vn),(vn,v1)
Obstacle
Proposition: If G is a directed graph with a cycle, then G has no topological ordering.
Proof:
Have cycle v1, v2,…, vn.
AFSOC we have an ordering.
Find earliest vi in the ordering.
Note that vi comes before vi-1, in contradiction to the order property.
DAGs
Definition: A Directed Acyclic Graph (DAG) is a directed graph which contains no cycles.
Previous result said that only DAGs can be topologically ordered. Is the reverse true?
Surprisingly, yes.
Existence of Orderings
Theorem: Let G be a (finite) DAG. Then G has a topological ordering.
Proof:
Consider the last vertex in the ordering.
Must be a sink (vertex with no outgoing edges).
Idea: find a sink, put at end, order remaining.
Question: Does G have a sink?
Sinks
Lemma: Every finite DAG contains at least one sink.
Proof:
Start at vertex v = v1
Find edges (v1,v2), (v2,v3), (v3, v4)…
Eventually either:
Some vertex repeats (create cycle)
Get stuck (found a sink)
Proof of Theorem
Induction on |G|.
Find sink v.
Let G’ = G-v.
Inductively order G’ (still a DAG).
Add v to the end of the ordering.
Algorithm
Problem: Design an algorithm that given a DAG G computes a topological ordering on G.
Find sink v
Follow chain of vertices until stuck
Compute ordering on G-v
Place v at the end
Algorithm
Ordering(G)
If |G|=0, Return {}
Let v ∈ G
While there is an edge (v,w)
v ← w
Return (Ordering(G-v),v)
Example
A
B
C
D
E
Final Ordering:
D
C
B
E
A
Runtime
(|V| time to find each sink) ·(|V| sinks)
= O(|V|2) runtime.
This is suboptimal.
Problem: After adding a sink to the end, the algorithm forgets the path that it took. Instead of backing up to start, just back up one step.
Example II
A
B
C
D
E
Final Ordering:
D
C
B
E
A
This is just DFS ordering!
Algorithm II
TopologicalSort(G)
Run DFS(G) w/ pre/post numbers
Return the vertices in reverse postorder
Note: Can add vertices to list as postorder assigned.
Runtime: O(|V|+|E|).
Correctness
Proposition: If G is a DAG with an edge v → w then w.post < v.post.
Implies that ordering is correct.
Proof:
Break into cases based on which of v or w is discovered first.
Proof
If v discovered first
w discovered while exploring v
w descendant of v
pre-post intervals nested
w.post < v.post
If w discovered first
v cannot be a descendant (DAG)
pre-post intervals are disjoint
w.post < v.post
Topological Sort
Useful algorithm.
Many graph algorithms are relatively easy to find the answer for v if you’ve already found the answer for everything downstream of v.
Topologically sort G.
Solve for v in reverse topological order.
Connectivity in Digraphs
In undirected graphs, we had a very clean description of reachability: v was reachable from w if and only if they were in the same connected component.
This no longer works for digraphs.
v
w
What is the right notion of connected components for digraphs?
Problems
Reachability no longer symmetric
can reach w from v but not v from w.
Maybe allow reachability in either direction?
Maybe allow you to follow edges in either direction?
This basically treats digraph as undirected.
v
w
u
Strongly Connected Components
Definition: In a directed graph G, two vertices v and w are in the same Strongly Connected Component (SCC) if v is reachable from w and w is reachable from v.
Question: Can you actually partition the vertices into such components?
Equivalence Relation
Let v ~ w if v reachable from w and visa versa.
Claim: This is an equivalence relation. Namely:
v ~ v. (v reachable from itself)
If v ~ w then w ~ v. (relation is symmetric)
If u ~ v and v ~ w then u ~ w.
v
w
u
Components
Whenever you have an equivalence relation you can split a set into components (equivalence classes) so that v ~ w if and only if v and w are in the same component.
Take any v, the set of all w so that v ~ w is the component of v. Everything connects to everything else in this class and does not connect (both ways) to anything outside.
Question: SCCs
How many strongly connected components does the graph below have?
1
2
3
4
5
A
B
C
D
E
F
G
H