Weak Components Revived
Speaking of unfortunate conventions in the math and CS literature, I've recently been surprised to learn that graph theory textbooks still have a very weak way to define the concept of “weak components” of a directed graph. They copy Harary's half-hearted notion, originally stated almost as an afterthought, by which a digraph's weak components are simply its ordinary components when the directions of oriented edges are ignored. Sometimes definitions are given just to fill up space instead of to fill a need!

A far better way to define weak components was introduced by Ron Graham, Theodor Motzkin, and yours truly in the paper “Complements and transitive closures,” Discrete Mathematics 2 (1972), 17--29; reprinted as Chapter 25 of Selected Papers on Discrete Mathematics. This definition wins big because it has a rich theory and many practical applications.

One nice way to think of it is by reference to strong components: The strong components of a digraph give the weakest partition of the vertices so that, when each part is collapsed into a single vertex, we get a partial order. The weak components give the weakest partition so that, when each part is collapsed into a single vertex, we get a total order.

Another nice way to think of it is by reference to ordinary connectivity: A digraph is weakly connected if and only if cannot be divided into two nonempty parts, L and R, such that (i) all vertices of R are reachable from all vertices of L; but (ii) no vertices of L are reachable from any vertex of R. Condition (ii) in an undirected graph is, of course, ordinary connectivity.

Bob Tarjan has devised beautiful algorithms to find both strong and weak components in linear time. I've recently written an exposition of those algorithms (and depth-first search in general), intended for eventual publication in Section 7.4.1.2 of The Art of Computer Programming. You can read it here: fasc12+.pdf (and there's a reward of 0x$1.00 if you are the first to discover an error). The theory of weak components is introduced on pages 11–14; relevant exercises are on page 21; answers to those exercises are on pages 31–33.

Let's all agree as soon as possible to use the easily understood term undirected components for what many people have unfortunately been calling weak components, and to celebrate the properties of directed graphs whose weak components are defined in a truly useful way.