Directed Graph

Terminology

• $G^T$: Transpose of directed graph; $G$ with all the directions of edges reversed
• Source vertex: outgoing edges only
• Sync vertex: incoming edges only
• Strongly connected directed graph: all edges can reach all other edges
  • Source Component: only outgoing edges to any vertex of component
  • Sync Component: only incoming edges to any vertex of component
• If directed graph has no cycles, it is a DAG

alg. Kosaraju’s Algorithm for Finding Strongly Connected Components.

• Idea: after performing a DFS on graph $G$, the
  1. let $v$ be the component with the maximum post-time
  2. Reverse edges of $G$ to get $G^T$.
  3. let $V_C$ be a sync component of $G^T$
  4. **$v$ must be an element of some sync component $V_C$
• See also: course

1. DFS on $G$
2. DFS on $G^T$ but…
   1. when you run out of reachable components…
   2. cut off the DFS tree; that’s a strongly connected component; then
   3. go in the next maximum unvisited post-time vertex

thm. (no cycles implies no zero-degree vertex) Let $G$ be a directed graph. If every vertex of $G$ has one or more outgoing edges, the graph is cyclic. Proof. graph theory - Having No Directed Cycles Guarantees a Vertex of Zero Outdegree - Mathematics Stack Exchange