Strong Connectivity

todo A graph is strongly connected if there is a path from any node to all other nodes in the graph.

The strongly connected components of a graph divide the graph into strongly connected parts that are as large as possible. The strongly connected components form an acyclic component graph that represents the deep structure of the original graph.

Slide: 12/19 of Lecture 07: Directed Graphs

From MATH239

Definitions

Connecteness

A graph is connected if there exists a $u,v$-path for every pair of vertices $u,v$.

Component, Graph cut,

Theorems and Lemmas

todo