Knuth教授近期在自己的个人主页上强烈呼吁大家要更正对弱连通分量的定义，不要用大部分教材里三心二意的定义，而是要用上个世纪70年代一篇关于离散数学的论文里的定义。Knuth教授的呼吁在此：https://www-cs-faculty.stanford.edu/~knuth/news22.html#weakcomps，部分引用如下：

Let’s all agree as soon as possible to use the easily understood term undirected components, or (as suggested by Doug West) underlying 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.

本文研究学习上个世纪70年代一篇离散数学的话题，它有一个很好的关于图(Graph)的弱连通分量的定义。论文信息如下：

• Graham, Ronald L., Donald E. Knuth, and Theodore S. Motzkin. “Complements and transitive closures.” Discret. Math. 2.1 (1972): 17-29.
• https://mathweb.ucsd.edu/~ronspubs/72_08_complements.pdf

有向图(Directed Graph)由顶点(vertex)和边(edge)构成的，可以看成边(edge)的集合，所以是一个二元关系(binary relation)。路径的延伸本质是传导性(transition)的应用，所以我们先研究一些关系理论和传导性的基本概念。

A是全体元素的集合，R=\{(a,b)| a\in A, b\in A\}是A上的一个binary relation。R所在空间的全集是A和其自身的笛卡尔积: A \times A。很自然的可以引出补的概念：R^{-}=A\times A - R（这里的-是集合的差集运算）。

(a,b) \in R，我们可以写成a\ R\ b。TRANSITIVE CLOSURE的符号是R^{+}。一个Relation是transitive的，当且仅当 a\ R\ b \land b\ R\ c \implies a\ R\ c。

看一个实际的例子，<这个二元关系，假设A=\{n|n \in \mathcal{N}, 0\le n \le 3\}，<=\{(0,1), (1,2), (2,3)\}。(0,1) \in <，故可写作0<1。<^+ = \{(0,1),(1,2),(2,3),(0,2),(1,3),(0,3)\}。

两个Relation的组合操作定义为R \circ S = \{(a,c) | \exists b, a\ R\ b \land b\ S\ c\}。延续上面的案例：

• < \circ < = \{(0,2),(1,3)\}，
• < \circ < \circ < = \{(0,3)\}，
• < \circ < \circ < \circ = {}

R^{+} = R \cup R \circ R \cup R \circ R \circ R \cup ...。这提供了另一种理解传递闭包的方式：(a,b) \in R^{+}，则\exists n, a_0,a_1,\dots,a_n, a_0=a,a_n=b, \forall 0<i<n, a_i\ R\ a_{i+1}。

给定R \subseteq  S，关于传递闭包和补有几个显而易见的性质:

• S^{-} \subseteq R^{-}
• R^{+} \subseteq S^{+}
• R^{--}=R

继续看一些有趣的公式：

R^{-+-} \subseteq R \iff R^{-} \subseteq R^{-+} R^+-R \subseteq R \circ R^+ = R^+ \circ R

下面引入一个看上去不那么直接易得的Lemma:

Lemma 1: R^+\circ R^{+-+-} \subseteq R^{+-+-}

Proof: 用反证法。假设上面命题是错的，即某个元素对(a,c)在上面左侧集合，但不在右侧集合（也就是在右侧集合的补里），就是\exists b, a\ R^+\ b, b\ R^{+-+-}\ c, a\ R^{+-+}\ c。下面想办法找矛盾。

b\ R^{+-+-}\ c \implies (b,c) \in R^{+-+-} \implies (b,c) \in R^+ \implies b\ R^+\ c a\ R^+\ b, b\ R^+\ c \implies a\ R^+\ c \implies (a,c) \notin R^{+-} \implies (a,c) \in R^{+-+} - R^{+-} \text{with } R^{+-+} - R^{+-} \subseteq R^{+-} \circ R^{+-+}, \implies (a,c) \in R^{+-} \circ R^{+-+} \implies \exists d, a\ R^{+-}\ d \land d\ R^{+-+}\ c

此时，如果b\ R^+\ d，则a\ R^+\ d, 和上面的a\ R^{+-}\ d是冲突的。

如果b\ R^{+-}\ d，则b\ R^{+-+}\ d，结合d\ R^{+-+}\ c ，有 b\ R^{+-+}\ c，这又和假设里的 b\ R^{+-+-}\ c是矛盾的。

综上，只能是假设不正确，从而原命题得证。

QDE.

下面紧接着看的是一个定理Theorem.

Theorem 1: \forall R是一个二元关系，R^{+-+-+}=R^{+-+-}。从而至多只有10个关系可以用补和传递闭包衍生获得：

• R,R^+,R^{+-},R^{+-+},R^{+-+-}
• R^{-},R^{-+},R^{-+-},R^{-+-+},R^{-+-+-}

Proof: 这个定理实际上是说R^{+-+-}是有传递性质的(transitive)。它如果已经具有传递性了，传递闭包就是它自身：R \text{ is transitive} \iff R^+=R 。结合前面的传递闭包的展开定义R^{+}=R\cup R \circ R \cup R \circ R \circ R \cup \dots，可以得知 R^+ = R \iff R \circ R \subseteq R。那么我们尝试来证明 R^{+-+-} \circ R^{+-+-} \subseteq R^{+-+-} 。回顾Lemma 1，以及我们还知道的:

• R^+ \circ R^{+-+-} \subseteq R^{+-+-}
• R^{+-+-} \subseteq R^{+}

如果我们可以证明 R^{+-+-} \circ R^{+-+-} \subseteq R^+ \circ R^{+-+-} 就搞定了这个问题。这个结合已有信息是显然的。它抽象出来的命题是：A_1,A_2,B_1,B_2是Relations，且A_1\subseteq A_2, B_1\subseteq B_2，则A_1 \circ B_1 \subseteq A_2 \circ B_2。它的证明如下:

\forall (a_1,b_1) \in A_1 \circ B_1, \exists c_1, a_1\ A_1\ c_1 \land c_1 \ B_1\ b_1 a_1 \ A_1\ c_1 \land A_1\subseteq A_2 \implies a_1\ A_2\ c_1 c_1 \ B_1\ b_1 \land B_1\subseteq B_2 \implies c_1\ B_2\ b_1 a_1\ A_2\ c_1 \land c_1\ B_2\ b_1 \implies a_1 (A_2 \circ B_2) b_1

QED.

二元关系(binary relation) R可以认为是有向图(directed graph)，如果R不连通，那么一定可以找到两个非空集合B, A-B，从而R \subseteq B\times B \cup (A-B) \times (A-B) 。研究下此类情况（非连通）下这个Relation的补和传递闭包:

R \subseteq B\times B \cup (A-B) \times (A-B) \implies (B\times B \cup (A-B) \times (A-B))^{-} \subseteq R^- \implies B\times (A-B) \cup (A-B) \times B \subseteq R^-

任何一个元素\forall a \in A，不论它在哪边，永远可以通过另一侧中转回到另一侧。所以R^{-+}=A\times A，因此R^{-+-}=\empty。稍加思考可以知道R^{+-+}=A\times A。

对任何一个二元关系，都可以定义出一个等价关系。

a \leftrightarrow b (R), \text{ if } a=b \lor (a\ R^+\ b \land b\ R^+\ a)

这个关系能被称作等价关系，显然它是具备三种性质：reflexive, symmetric and transitive。等价关系可以把A划分成若干等价类(equivalence classes)。如果我们把relation \ R看成是一个有向图(directed graph)，如果(a,b) \in R\ (a \ R\ b)，那就是有一个有向边从a指向b，那么上面的这个等价关系就把这个有向图分成了一个一个的强连通分量。

弱连通分量的定义可以模仿上面，先定义一个等价关系，这个等价关系粗糙一些。所以我们称之为弱连通分量，如下：

a \Leftrightarrow b (R), \text{ if } a \leftrightarrow b(R) \lor a \leftrightarrow b(R^{+-})

Knuth教授在手稿里关于弱连通分量的解释，似乎更容易懂一些：

• 弱连通是一种比强连通弱一些的等价关系
• 强连通当然毫无疑问就应该认为弱连通了
• 如果两个元素，在R里，互相不可到达，就是弱等价
  • (\neg (a\ R^+\ b)) \land (\neg (b\ R^+\ a))
  • 上述实际上就是 a\ R^{+-} b \land b\ R^{+-} a ，就是 a \leftrightarrow b(R^{+-})

我们来证明弱连通分量也是一个等价关系。

Proof：

reflexive: \forall a \leftrightarrow a(R) \implies a \Leftrightarrow a (R) ；

symmetric:

• 可能性1： a \leftrightarrow b(R) \implies b \leftrightarrow a(R) \implies b \Leftrightarrow a (R)
• 可能性2： a \leftrightarrow b(R^{+-}) \implies b \leftrightarrow a(R^{+-}) \implies b \Leftrightarrow a (R)

transitive：即证明 a \Leftrightarrow b (R) \land b \Leftrightarrow c (R) \implies a \Leftrightarrow c (R)。

• 可能性1： a \leftrightarrow b(R) \land b \leftrightarrow c(R) \implies a \leftrightarrow c(R) \implies a \Leftrightarrow c (R) ；
• 可能性2： a \leftrightarrow b(R^{+-}) \land b \leftrightarrow c(R^{+-}) \implies a \leftrightarrow c(R^{+-}) \implies a \Leftrightarrow c (R)
• 可能性3： a \leftrightarrow b(R) \land b \leftrightarrow c(R^{+-})
• 可能性4： a \leftrightarrow b(R^{+-}) \land b \leftrightarrow c(R)

上述可能性3和4可以用反证法，证明技巧是一样的。针对可能性3，反证法，假设a \Leftrightarrow c (R)不成立，也就是 (a,c) \notin R^{+-} \implies (a,c) \in R^+ \implies a\ R^+\ c \implies a \leftrightarrow c(R) 。这就是和假设矛盾了。故而得证。

QED.

再看一个命题： a\ R^{+-}\ b \land b\ R^{+-}\ c \land a\ R^+\ c \implies b\ R^{+-}\ a \land c\ R^{+-}\ b，这个命题还是可以用反证法得出：假设 b\ R^{+-}\ a 不成立，即 (b,a) \notin R^{+-} \implies (b,a) \in R^+ , 那么a,b,c就属于同一个等价类（强连通分量），这就和 a\ R^{+-}\ b矛盾了。故而命题得证。

下面这段论文里的原话十分重要，这也是为啥Knuth教授对大部分教材上的弱连通分量定义极度不满意的原因：

The importance of the equivalence relations \leftrightarrow and \Leftrightarrow is due to the
fact that R^+ defines a partial order on the strong components, and a
total order on the weak components.

全序性质让我们可以写出：

a < b(R), \text{ if } a \nLeftrightarrow b (R) \land a\ R^+\ b

即我们可以把弱连通分量进行线性排序。如果一个弱连通分量，可以抵达另一个弱连通分量，那么它就排在前头。

每一个弱连通分量都由若干强连通分量组成，只有一个强连通分量的弱连通分量称之为simple；只有一个元素的连通分量称之为trivial。

用论文里的一个示例图(Fig 1)来理解一下（强｜弱）连通分量：如下图的relation R，合计有15个元素（顶点），20条边：A=\{a,b,c,d,e,f,g,h,i,j,k,l,m,n,o\}:

上图中，强连通分量共有9个，分别用虚线的椭圆框圈起来了。弱连通分量有4个，用水平的粗黑线隔开：

• 强连通分量：
  • S_1=\{a,b,c\},
  • S_2=\{h,i,j\},
  • trivial的分量： S_3=\{d\}, S_4=\{e\}, S_5=\{o\}, S_6=\{n\}, S_7=\{g\},
  • S_8=\{k,l\},
  • S_9=\{m,f\},
• 弱连通分量：
  • S_1 \cup S_2 \cup S_3
  • S_8 \cup S_4
  • S_9
  • S_5 \cup S_6 \cup S_7

强连通分量很好理解，每个内部是连通的，任意两个元素都存在通路。并且上述9个强连通分量之间互相是不可达的。上面图中的弱连通分量从上到下，线性排序。