Lesson 1

Recall that an undirected graph is called connected if there is a path between any two of its nodes. For example, the following graph is connected.

Would you call the following directed graph connected?

Though this graph looks connected in a sense that there are roads allowing one to get from any node to any other node, these roads are now one-way and one needs to respect the direction while driving the roads. In particular, there is no path from \(6\) to \(4\) in this graph, for a simple reason: there are no edges coming to \(4\). Also, from \(8\) one cannot reach \(5\) since the only nodes reachable from \(8\) are \(2\) and \(7\).

This discussion motivates the following definition. In a directed graph, nodes \(u,v\) are connected if there is a path from \(u\) to \(v\) and a path from \(v\) to \(u\). In the example graph above, the nodes \(3\) and \(6\) are connected, whereas the nodes \(5\) and \(8\) are not.

As in the case of undirected graphs, the nodes of any directed graph can be partitioned into subsets called strongly connected components (SCCs) satisfying the following properties:

• every node belongs to exactly one SCC;


• nodes from the same SCC are connected;


• nodes from different SCCs are not connected.