§2.2.1树
1847年，克希霍夫在研究电网络方程时首次提出了树的概念.
树(tree)：a connected(连通的) and acyclic(无圈的) graph.
平凡树（trivial tree）：的树，即（平凡图）；非平凡树（nontrivial tree）：otherwise.
叶（leaf）：树的悬挂点（度为1的顶点）；分支点（branch vertex）：度2的顶点.
非同构的树
1
2
3
4
5
6
7
11个
注：（1）若是树的顶点，则是树的割点是树的分支点，不是树的割点是树的叶；树的每一条边均为割边.
（2）若是树，则，为森林，的各个连通分支都是树（见§2.2.1），称之为的子树（subtree）.
（3）树是二分图.（树无圈，当然也不含有奇圈，见§2.1.2 Th1）.当然，森林也是二分图
树的应用背景：
（1）概率树（probability tree）
概率树在概率论上利用全概率公式，Beyes公式计算概率时作用甚大.
（2）组织结构
（3）家谱（family tree）：家谱反映的家族内部的血缘关系和树的特征（连通，无圈）一致.
（4）化学物质的结构：同分异构体
1857年，数学家凯莱（Arthur Cayley）利用树的概念来研究烃的同分异构体.
顶点表示碳原子，边表示原子之间的化学键.
丁烷的两种同分异构体
（5）决策树（decision tree）：
（6）在计算机上，Windows操作系统采用树形结构管理文件与目录系统.
Lemma1任一非平凡树均至少有两个悬挂点.（任一非平凡树均至少有两个叶）
证明：设是一个树，，取的一条最长路，
，且连通，的长度为，于是.
下证是悬挂点，即.
（反证法）假设，则，使得.
若，则令，显然是的一条路，且比的长度多1，与是最长路矛盾；
若，则是的一个圈，与是树矛盾.
同理可证，也是悬挂点.
另证：设非平凡树的悬挂点的个数为，则非悬挂点的个数为.
由§2.1.1 Th1有，.▌
注：非平凡树的最长路的起点和终点必为悬挂点.
Lemma2(1)若图无孤立点，且，则至少有一个悬挂点．
(2)若图连通，且，则至少有一个悬挂点．
证明：(1)（反证法）假设无悬挂点，则由无孤立点知，.
于是，，矛盾.
(2)若连通，则无孤立点，故由（1）知，至少有一个悬挂点.▌
注：（逆否命题）若图无孤立点，且无悬挂点，则；若图连通，且无悬挂点，则．
Th1（1）是树；（2）无圈，且；（3）连通，且；（4）的任两顶点之间恰有唯一一条路相连；（5）连通，且去掉任一条边后即不连通；（6）无圈，且在任两顶点之间添加一条边即得一个圈.
证明：（1）（2）：设是树，则无圈；下证.
（对作数归法）当时，结论显然成立；
设当时结论成立，则当时，令，则由Th1知，至少有两个悬挂点.不妨取其一为，则易见仍是树，且.
由归纳假设，有.
于是，.综上，成立.
设无圈，且,则仅需证连通.（反证法）假设不连通，则.不妨设的各连通分支为，则易见是树，且由（1）（2）知，,.于是，，与矛盾.
（1）（3）：设是树，则连通；再由（1）（2）知，.
设连通，且，则仅需证无圈.
（对作数归法）当时，，显然无圈；
设当时无圈性成立，则当时，令，，则由Lemma2（2）知，至少有一个悬挂点.不妨设它为，则易见仍连通，且，.
由归纳假设知，无圈.显然，亦无圈.综上，无圈得证.
（1）（4）：设是树，则连通，的任两顶点之间必至少有一条路相连.
下证唯一性.（反证法）假设，之间有两条不同的路相连,
若与无公共边，则恰为的一个圈，与是树矛盾；否则，.显然，连通，故中一条路.于是，是的一个圈，与是树矛盾.
设的任两顶点之间恰有唯一一条路相连，则连通.下证无圈.（反证法）假设中有一个圈，则与是连结顶点的两条不同的路，与唯一性矛盾.
（1）（5）：设是树，则连通.下证去掉的任一条边后即不连通.
（反证法）假设，使得仍连通，则之间有一条路相连.于是，是的一个圈，与是树矛盾.
设连通，且去掉任一条边后即不连通，则仅需证无圈.
（反证法）假设中有一个圈，则易见，仍连通，矛盾.
（1）（6）：设是树，则无圈.下证在的任两顶点之间添加一条边即得一个圈.
，由是树知，连通，之间有一条路相连.在中添加边，则即为的一个圈.
设无圈，且在任两顶点之间添加一条边即得一个圈，则仅需证连通.
，在中添加边，则中有一个圈，不妨设为.易见，.于是，即为连结的一条路，故连通.▌
注：（1）树的边数是.
（2）Th1（5）表明：就连通性而言，树的边数最少.树是极小连通图（minimal connected graph），即在顶点数相同的所有连通图中，树含有的边数最少；
（6）表明：就无圈性而言，树的边数最多.树是极大无圈图（maximal acyclic graph），即在顶点数相同的所有无圈图中，树含有的边数最多.
Th2 A connected graph is a tree if and only if every edge of is a cut edge.
证明：Assume is a graph,, is acyclic,by 02-01(2)割边的定义的注（3）, is a cut edge.
(By contradiction)Suppose is not a tree,then contains at least a cycle .By §2.1.2割边的定义的注（3）,the edges of are not cut edge of ,which contradicts the hypothesis.▌
Note:§2.1.2割边的定义的注（3）： is a cut edge of a graph dosen’t belong to any cycle of .
Th3 设树中度为的顶点的个数为，，，则叶的个数为.
证明：由§2.1.1 Th1有，
▌
注：叶的个数竟然与度为2的顶点的个数无关！（为什么？）
例1一个树中度为2，3，4的顶点的个数分别为2，1，3，其余顶点为叶，求叶的个数.
解：设叶的个数为，则.
由§2.1.1 Th1有，.
另解：由Th3有，.▌
注：将例1改为：“度为3，4的顶点的个数分别为1，3”亦可解.
例2一个树有20个顶点，其中有8个叶，其余顶点的度均，求2，3度顶点的个数.
解：易见，除叶外，树的其余顶点的度均为2，3.设2度顶点的个数为，则由§2.1.1 Th1有，
,3度顶点的个数为.▌
例3求证：恰含有2个悬挂点的树必为一条路.
证明：只需证树中除两个悬挂点外的顶点的度均为2.（反证法）假设树中存在度2的顶点，则有，矛盾.▌
例4求证：若是树，且，则中至少有个悬挂点.
证明：（反证法）假设中悬挂点的个数为，则
.▌
例5求证：若树中度为的顶点的个数，，，则，，但与大小不定.
但与大小不定.
另证：由Th3有，，
.▌
例6烷烃是一种有机物，由碳原子和氢原子构成，其中碳，氢原子的化合价分别为4，1，且不存在任何化学键构成圈.试证：烷烃的分子式为.
证：设烷烃的分子式为，将碳，氢原子视为顶点，原子之间的化学键视为边，则烷烃的分子结构是一个含有个4度顶点，个1度顶点的树.
由Th3有，.
烷烃的分子式为.▌
1847年，克希霍夫在研究电网络方程时首次提出了树的概念.
树(tree)：a connected(连通的) and acyclic(无圈的) graph.
平凡树（trivial tree）：的树，即（平凡图）；非平凡树（nontrivial tree）：otherwise.
叶（leaf）：树的悬挂点（度为1的顶点）；分支点（branch vertex）：度2的顶点.
非同构的树
1
2
3
4
5
6
7
11个
注：（1）若是树的顶点，则是树的割点是树的分支点，不是树的割点是树的叶；树的每一条边均为割边.
（2）若是树，则，为森林，的各个连通分支都是树（见§2.2.1），称之为的子树（subtree）.
（3）树是二分图.（树无圈，当然也不含有奇圈，见§2.1.2 Th1）.当然，森林也是二分图
树的应用背景：
（1）概率树（probability tree）
概率树在概率论上利用全概率公式，Beyes公式计算概率时作用甚大.
（2）组织结构
（3）家谱（family tree）：家谱反映的家族内部的血缘关系和树的特征（连通，无圈）一致.
（4）化学物质的结构：同分异构体
1857年，数学家凯莱（Arthur Cayley）利用树的概念来研究烃的同分异构体.
顶点表示碳原子，边表示原子之间的化学键.
丁烷的两种同分异构体
（5）决策树（decision tree）：
（6）在计算机上，Windows操作系统采用树形结构管理文件与目录系统.
Lemma1任一非平凡树均至少有两个悬挂点.（任一非平凡树均至少有两个叶）
证明：设是一个树，，取的一条最长路，
，且连通，的长度为，于是.
下证是悬挂点，即.
（反证法）假设，则，使得.
若，则令，显然是的一条路，且比的长度多1，与是最长路矛盾；
若，则是的一个圈，与是树矛盾.
同理可证，也是悬挂点.
另证：设非平凡树的悬挂点的个数为，则非悬挂点的个数为.
由§2.1.1 Th1有，.▌
注：非平凡树的最长路的起点和终点必为悬挂点.
Lemma2(1)若图无孤立点，且，则至少有一个悬挂点．
(2)若图连通，且，则至少有一个悬挂点．
证明：(1)（反证法）假设无悬挂点，则由无孤立点知，.
于是，，矛盾.
(2)若连通，则无孤立点，故由（1）知，至少有一个悬挂点.▌
注：（逆否命题）若图无孤立点，且无悬挂点，则；若图连通，且无悬挂点，则．
Th1（1）是树；（2）无圈，且；（3）连通，且；（4）的任两顶点之间恰有唯一一条路相连；（5）连通，且去掉任一条边后即不连通；（6）无圈，且在任两顶点之间添加一条边即得一个圈.
证明：（1）（2）：设是树，则无圈；下证.
（对作数归法）当时，结论显然成立；
设当时结论成立，则当时，令，则由Th1知，至少有两个悬挂点.不妨取其一为，则易见仍是树，且.
由归纳假设，有.
于是，.综上，成立.
设无圈，且,则仅需证连通.（反证法）假设不连通，则.不妨设的各连通分支为，则易见是树，且由（1）（2）知，,.于是，，与矛盾.
（1）（3）：设是树，则连通；再由（1）（2）知，.
设连通，且，则仅需证无圈.
（对作数归法）当时，，显然无圈；
设当时无圈性成立，则当时，令，，则由Lemma2（2）知，至少有一个悬挂点.不妨设它为，则易见仍连通，且，.
由归纳假设知，无圈.显然，亦无圈.综上，无圈得证.
（1）（4）：设是树，则连通，的任两顶点之间必至少有一条路相连.
下证唯一性.（反证法）假设，之间有两条不同的路相连,
若与无公共边，则恰为的一个圈，与是树矛盾；否则，.显然，连通，故中一条路.于是，是的一个圈，与是树矛盾.
设的任两顶点之间恰有唯一一条路相连，则连通.下证无圈.（反证法）假设中有一个圈，则与是连结顶点的两条不同的路，与唯一性矛盾.
（1）（5）：设是树，则连通.下证去掉的任一条边后即不连通.
（反证法）假设，使得仍连通，则之间有一条路相连.于是，是的一个圈，与是树矛盾.
设连通，且去掉任一条边后即不连通，则仅需证无圈.
（反证法）假设中有一个圈，则易见，仍连通，矛盾.
（1）（6）：设是树，则无圈.下证在的任两顶点之间添加一条边即得一个圈.
，由是树知，连通，之间有一条路相连.在中添加边，则即为的一个圈.
设无圈，且在任两顶点之间添加一条边即得一个圈，则仅需证连通.
，在中添加边，则中有一个圈，不妨设为.易见，.于是，即为连结的一条路，故连通.▌
注：（1）树的边数是.
（2）Th1（5）表明：就连通性而言，树的边数最少.树是极小连通图（minimal connected graph），即在顶点数相同的所有连通图中，树含有的边数最少；
（6）表明：就无圈性而言，树的边数最多.树是极大无圈图（maximal acyclic graph），即在顶点数相同的所有无圈图中，树含有的边数最多.
Th2 A connected graph is a tree if and only if every edge of is a cut edge.
证明：Assume is a graph,, is acyclic,by 02-01(2)割边的定义的注（3）, is a cut edge.
(By contradiction)Suppose is not a tree,then contains at least a cycle .By §2.1.2割边的定义的注（3）,the edges of are not cut edge of ,which contradicts the hypothesis.▌
Note:§2.1.2割边的定义的注（3）： is a cut edge of a graph dosen’t belong to any cycle of .
Th3 设树中度为的顶点的个数为，，，则叶的个数为.
证明：由§2.1.1 Th1有，
▌
注：叶的个数竟然与度为2的顶点的个数无关！（为什么？）
例1一个树中度为2，3，4的顶点的个数分别为2，1，3，其余顶点为叶，求叶的个数.
解：设叶的个数为，则.
由§2.1.1 Th1有，.
另解：由Th3有，.▌
注：将例1改为：“度为3，4的顶点的个数分别为1，3”亦可解.
例2一个树有20个顶点，其中有8个叶，其余顶点的度均，求2，3度顶点的个数.
解：易见，除叶外，树的其余顶点的度均为2，3.设2度顶点的个数为，则由§2.1.1 Th1有，
,3度顶点的个数为.▌
例3求证：恰含有2个悬挂点的树必为一条路.
证明：只需证树中除两个悬挂点外的顶点的度均为2.（反证法）假设树中存在度2的顶点，则有，矛盾.▌
例4求证：若是树，且，则中至少有个悬挂点.
证明：（反证法）假设中悬挂点的个数为，则
.▌
例5求证：若树中度为的顶点的个数，，，则，，但与大小不定.
但与大小不定.
另证：由Th3有，，
.▌
例6烷烃是一种有机物，由碳原子和氢原子构成，其中碳，氢原子的化合价分别为4，1，且不存在任何化学键构成圈.试证：烷烃的分子式为.
证：设烷烃的分子式为，将碳，氢原子视为顶点，原子之间的化学键视为边，则烷烃的分子结构是一个含有个4度顶点，个1度顶点的树.
由Th3有，.
烷烃的分子式为.▌
