Definitions

A path in a graph G=(V,E) is a sequence of nodes $u_1,
\ldots, u_k$, such that for all $i\in [1,k-1]$, $(u_i, u_{i+1}) \in
E$.

Graph G is strongly connected if, for every u and v in V, there is some path from u to v and some path from v to u.

A strongly connected component of a graph is a maximal subset of nodes (along with their associated edges) that is strongly connected. Nodes share a strongly connected component if they are interreachable.


next up previous
Next: More Formal Statement Up: STRONGLY CONNECTED COMPONENTS Previous: Airline Flight Planning