• : Transpose of directed graph; 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 , the
    1. let be the component with the maximum post-time
    2. Reverse edges of to get .
    3. let be a sync component of
    4. ** must be an element of some sync component
  • See also: course
  1. DFS on
  2. DFS on 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 be a directed graph. If every vertex of 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