树

树的定义及其性质
定义：不含任何回路的连通图成为树。度为1的点称为树叶，大于1的点称为分支点。

定义：设e是图G的一条边。如果\(G-e\)的连通分支多于G，称e是G的一条割边。

定理1. e是G的割边，当且仅当e不属于G的任何回路。

定理2. 设T是阶不小于2的无向简单图，则以下说法等价：
1. T连通，且无回路
2. T连通，且每条边都是割边
3. T连通，且有n-1条边
4. T有n-1条边，且无回路
5. T的任意两结点之间有唯一道路
6. T无回路，但任意加上一条边后，恰有一个回路。
证明：\(1\Leftrightarrow 2, 2\Rightarrow 3, 3\Rightarrow 4, 4\Rightarrow 5, 5\Rightarrow 6, 6\Rightarrow 1\)

推论3. 设G是结点数为n的、连通分支数为k的森林，则G的边数为\(n-k\)。

回路与割集
定义：设T是连通图G的生成树，\(e_1,\cdots, e_{m-n+1}\)是T的弦，记\(C_r\)是T加弦\(e_r\)产生的回路。称\(C_r\)为对应弦\(e_r\)的基本回路，\(\{C_1,\cdots,C_r\}\)。

定理3. 设T是连通图G的一颗生成树，\(C_k\)是对应于弦\(e_k\)的基本回路，对于任意r及序列\(1\le i_1< \cdots < i_r\le m-n+1\)，有\(e_{i_1},\cdots,e_{i_r}\)是\(C_{i_1}\oplus \cdots\oplus C_{i_r}\)的所有弦。
证明：只需注意到\(e_i\)只在\(S_i\)中出现。

下面说明G中任意回路都可由基本回路生成。
引理4. 如果图\(G_1,G_2\)的结点都是偶结点，则\(G_1\oplus G_2\)的结点也都是偶结点。
定理5. 连通图G的任何回路C均可表示为生成树T的若干基本回路的环和。
证明：设C中含T的r条弦，取\(C'\)为这r条弦对应的基本回路之环和。断言\(C=C'\)，否则\(C\oplus C'\)非空，而由定理3知\(C\oplus C'\)的边都在T中，由引理4知这些结点都是偶结点，必包含回路，矛盾。

推论6. 设连通图G的回个数为c，则\(m-n+1\le c \le 2^{m-n+1}-1\).

生成树与基本割集系统
定义：设\(S\)是图G的边集E的子集，且满足：
1. \(G'=(V,E-S)\)不连通；
2. 对任意\(S'\subsetneq S\)， \(G''=(V,E-S'')\)仍连通。

定理7. 设T是连通图G的生成树，则T的每一树枝对应G的一个割集。
证明：取e为T的一个树枝。从T中删去e得到二连通分支\(T_1,T_2\)，分别对应结点集为\(V_1,V_2\)，G中所有两端点分别在\(V_1,V_2\)的边组成集合为\(S_e\)，则\(S_e\)是仅包含T中一条边e的割集。

由定理7可以引出基本割集系统的概念。基本割集系统与基本回路系统有类似的性质。
定义：设T是连通图G的生成树，\(n-1\)个树枝对应的割集\(S_1,\cdots, S_{n-1}\)称为对应T的基本割集，称\(\{S_1,\cdots, S_{n-1}\}\)为对应T的基本割集系统。

定理8. 连通图G的每个割集必包含G中每棵生成树的至少一个树枝。
定理9. 设\(\{S_1,\cdots, S_{n-1}\}\)是G相对于生成树T的基本割集系统，则\(S_{i_1}\oplus \cdots\oplus S_{i_k}\)的所有树枝是\(e_{i_1}, \cdots, e_{i_k}\)。
证明与定理3类似。

为了说明任意割集可由基本割集生成，我们还需引入断集的概念。
定义：设G是无向图，\(V_1\)是V的非空真子集，所有两端点分别在\(V_1,\bar V_1\)中的边组成的集合记作\(E(V_1\times\bar V_1)\)，成为G的一个断集。
割集一定是断集，但断集未必是割集。

引理10. 设\(S_1,S_2\)是无向图G的两个不同断集，则\(S_1\oplus S_2\)也是G的断集。
证明：令\(V_0=(V_1\cap V_2)\cup (\bar V_1\cap \bar V_2)\)， 则\(S_1\oplus S_2=E(V_0\times\bar V_0)\)。

定理11. 连通图G的任意割集可以表示为生成树T的对应若干基本割集的环和。
证明：任取G的割集S，设S包含T的k条边，取\(S'\)为这k条边对应的基本割集之环和。如果\(S\ne S'\)，则\(S\oplus S'\)是断集，但不包含T的任何边，与定理8矛盾。

定理12. 任何一个回路与任何一个断集都有偶数条公共边。
推论13. 设T是连通图G的生成树，e是T的树枝，\(e'\)是T的弦。则\[e\in C_{e'}\Leftrightarrow e'\in S_e.\]

    所属分类：离散数学     发表于2022-08-21