树与林

贡献者： 零穹

　　 [1] 林是不含圈的图，树是连通的林。也就是说，林的连通分支都是树。

　　 由例 1 可知，林和树都是简单图。

　　 证明： 1. $1\Rightarrow 2$：设 $\forall x,y\in T$。同于树是连通的，所以存在 $x$ 到 $y$ 的（长为 $l$）路 $R=xe_1x_1\cdots y$。设 $R'=xe'_1x_1'\cdots e'_n y$ 是连接 $x,y$ 的另一（长为 $n$）路。由于 $T$ 无圈，所以链 $xe_1\cdots y|e'_n\cdots e'_1x$ 中在 $|$ 两边一定有两个内点相同，否则该链就是一个圈。由于左边和右边分别是路，因此两个内点只能一个在一边。设这两个内点是 $x_{i},x'_{j}$，于是 $W(x_{i},x'_{j})$ 是 $x_{i}x'_{j}$ 链。

　　 由于 $W(x_{i},x'_{j})$ 端点相同，我们仍可以重复上面的论述。若 $i\neq j$，不是一般性 设 $i>j$，于是至多重复 $l-i+1$ 次后得到链 $x_{l-1}e_ly|e_n'\cdots x'_{i_{l-i+2}}$，继续重复操作，则将出现 $y=y',y'\in R'$。这和 $R'$ 是路矛盾。这一矛盾表明只能是 $x_i=x_i'$。若 $n\neq l$ 则重复 $k-l$ 次又会出现上面的情况，于是只能是 $n=l$。于是重复最多重复 $n-1$ 次，我们就会发现 $x_{n-1}=x'_{n-1}$。

　　 然后对路 $R_1=R-x_{n-1}$ 继续上述操作，可以得到 $x_{n-2}=x_{n-2}'$。如此重复，最终得到 $R=R'$。

　　 2.$2\Rightarrow 3$：由 2 可知 $T$ 是连通的。$\forall e\in E(T)$，设 其端点为 $x,y$，无圈表明 $x\neq y$。而 $x,y\in V(T-e)$，$xey$ 是连接 $x,y$ 的唯一路，所以 $T-e$ 中不能有连接 $x,y$ 的路了。否则这条路只能是 $xey$，但是 $e\not\in E(T-e)$。

　　 3.$3\Rightarrow 4$：a.设 $T$ 包含圈 $R=x_0e_1x_1\cdots x_0$，那么 $R-e_1=x_1e_2\cdots x_0$ 是连接 $x_1,x_0$ 的路，但这是不可能的，所以 $T$ 不包含圈。b.设 $\forall x,y\in V(T)$ 不相邻，记 $xy=e$。那么由于 $T$ 上有连接 $xy$ 的路 $xe_1x_1\cdots y$，所以此时 $T+xy$ 包含圈 $xe_1x_1\cdots yex$。

　　 4. $4\Rightarrow 1$：任意 $x,y\in V(T)$，记 $e=xy$。由于 $T$ 不含圈，$T+e$ 含圈，所以所含的圈必然包含 $e$，否则 $T$ 有圈。以 $x$ 作为端点，记该圈为 $xe_1x_1\cdots yex$。由于除了 $e$ 以外其它圈的元素都在 $T$ 内，因此路 $x e_1x_1\cdots y$ 属于 $T$，即 $x,y$ 连通。所以 $T$ 是树。

　　 证毕！

　　 注意定理的 3 相当于 $T$ 连通且连通分支 $\omega(T-e)=2,\forall e\in E(T)$。于是得下面的推论。

1. 支撑树与支撑林

　　 证明： 设 $T$ 是连通图 $G$ 的边最少的连通支撑子图。那么 $\omega(T-e)=2,\forall e\in E(T)$。事实上，如若不然，则 $T-e$ 仍是连通的，且点数不变，而边数却少了 1，这和 $T$ 是边最少的连通支撑子图矛盾。由推论 1 ，$T$ 是树。

　　 证毕！

[1] ^ 徐俊明.图论及应用. 中国科学技术大学出版社, 合肥.1998.