1设有一(n，m)树，由于其不包含任何回路，故从树中删去一边后就变成两个互不连通的子图。而其每个子图是连通的，故其每个子图均为树。设它们分别是(n1，m1)树及(n2，m2)树，由于 n1 ＜ n， n2 ＜ n 。故有归纳假设可得， m1＝n1 －1 ， m1＝n1 －1 又因为
n ＝n1 ＋ n1 ， m2＝n2 －1 故得到m＝n－1
定理1.2.2 非平凡树至少有两片叶子
［证］设树T＝〈V , E〉，│V│＝v ，因为Ｔ是连通图，对于任何vi 属于Ｔ有deg(vi) < 1 且∑deg(vi) 不大于2v 得出矛盾。若T中只有一个结点度数为1，其它结点度数大于等于2，则 ∑deg(vi) ≤ 2v－1
得出矛盾。故T中至少有两个结点度数为1。
定理1.2.3 (n，m)无向图构成树↔每对结点的通路只有一条
［证］ 必要性：若有图Ｇ是树，故每对节点间均有通路。若结点vi 与vj 间有两条通路，则此两条通路必构成一条回路，而这与树的定义矛盾。
充分性：图G的每对结点间存在通路，故G是连通的。又由于通路的唯一性，故知图中不包含回路，由此可知G是树。 1.3 特殊的无向树（生成树） 1.3.1 生成树的有关定义及其性质
定义1.3.1 设有无向图G的生成子图构成树，则称其为生成树。
由一个连通图找它的生成树的过程是：
方法一：破圈法。设G是一个连通图，如果G是树，则G本身就是G的生成树。如果G
不是树，则G至少有一个回路c，在ｃ中任取一条边ｅ，则Ｇ－ｅ仍是连通图。即Ｇ１＝Ｇ－ｅ是Ｇ的连通生成子图。如果Ｇ1仍不是树，可以继续这个过程，直到一条边从最后一个回路中去掉。所得图Ｔ就是Ｇ的一个连通生成子图，而且没有回路，故Ｔ就是Ｇ的生成树。
方法二：避圈法。设Ｇ是一个连通图。在Ｖ（Ｇ）中逐次添加Ｅ（Ｇ）中的边，要求每次添加边后所得子图都不含回路。把上述过程进行到无法再进行为止。所得到的子图Ｔ是Ｇ的一个极大无回路生成子图，Ｔ就是Ｇ的生成树。 定理1.3.1 连通图至少有一颗生成树。
2
［证］设连通图G没有回路则G本身就是一棵生成树。若G至少有一个回路，我们删去G的回路上的一条边，得到图G1就是生成树。若G１仍有回路，再删去G１回路上的一条边。重复上述步骤，直至得到一个连通图H，它没有回路。但与Ｇ有同样的结点集，因此H是 G生成树。 由此定理得证。 1.3.2 最小生成树
定义1.3.2 在图G的所有生成树中，树权最小的那棵生成树称作最小生成树。其中
树权记作T（w）。 用避圈法找最小生成树。 将图中的环去掉。
将图中个边的权按从小到大的顺序排列w1 ， w2 … wn （ l1 ，l2 … lm ）。 先取l1，看l2 … lm与l1是否构成回路，构成回路的删去，不构成的留下。 继续以上方法，最后得到的生成树为最小生成树。 如图1.3.2中实线组成的图形为最小生成树。
2 有向树的有关概念
2.1有向树的有关定义
定义2.1.1 在有向图中不考虑边的方向而构成树，则称此有向图为有向树。
例如图2.1（a）所绘出的有向图即为有向树，但图2.1（b）所绘出的有向图则不是有向树，因为当忽略其方向时该图存在回路。
3
定义2.1.2 若一颗有向树恰有一个结点的引入次数为0，其余所有节点的引入次数为1，则称该有向树为树形图。
例如图2.1.2中(a)，(b)所示是树形图。
在树形图中引入次数为零的结点称为树形图的根。如图2.1.2 (a)中V1。引入次数为１，引出次数为０的结点称为树形图的叶。如图2.1.2 (a)中v2 ，v4 ，v6 。 引入次数为１， 引出 次数非零的结点称为树形图的内点。如图2.1.2 (a)中v3 ， v5 2.2 特殊有向树
定义2.2.1 有且仅有一个结点的引入次数为0，其它结点的引入次数为1，还有一些结
点的引出次数为0的有向树称为外向树（根树）。 例如图2.1.2中(a)，(b)所示是外向树。
定义2.2.2 有且仅有一个结点的引出次数为0，其它结点的引出次数为1，还有一些结点的引出次数为0的有向树称为内向树 。 例如图2.2.2 所示
4
3 根树（外向树）
定义3.1 在树形图中有且仅有一个引入次数为零的结点称为根。 定义3.2 根到结点vi的层数称为该结点vi的层数。 定义3.3 外向树的最大层数称为树高。 例如图3.0 所给出的图是根树。
在图3.0中，v0是根。v5 ， v6 ， v7 ， v8 ， v9是树叶。 v1 ， v2 ， v3 ， v4是内点。v0 ， v1 ， v2 ， v3 ， v4统称为分枝点。结点v0 的层数为0。结点v1 ， v2 的层数为1，结点v3 ， v4 ，v5 的层数为2。结点v6 ， v7 ， v8 ， v9的层数为3。这样的树形图的高为3 。
4 二元树
外向树除叶外每个节点的引出次数均大于0。结点的引出次数均不超过某一正整数ｍ，则称此外向树为ｍ元树。由此可以定义ｍ元树如下： 定义4.1 n个结点的外向树如满足：
引出次数deg(vi)≤m (i=1,2…n)
则称此外向树为m元树。 如满足（除叶外）：
5
引出次数deg(vi)=m (i=1,2…n)
则称此外向树为m元完全树。
定理4.1 设有m元完全树，其树叶树为t，分枝点数为i，则（m-1）×i＝t－1 ［证］若把m元树看做是每局有m位选手参加比赛的单淘汰撒计划表。树叶数t表示参加比赛的选手数。分枝点数i表示比赛的局数。因为每局比赛将淘汰（m-1）位选手，故比赛结果共淘汰（m-1）×i位选手，最后剩下一位冠军。因此（m-1）×i＝t－1 。 定义4.2 设有有权树D=〈V，E，w〉。 w1 ， w2 … wn为叶的权。T（w）＝∑wi×l( vi) 中最小的2元树称为最优2元树。 画出最优2元树的步骤如下：
① 将叶的权从小到大排列w1 ， w2 … wn 。
② 将权为 w1 ， w2 的两片叶子画出，引出新的结点的权数为w1 ＋ w2 。 ③ 权为w1 ＋ w2与w3 … wn 的比较画出结点。继续上述过程得到的2元树为最优2元树。
图4.0 （a）（b）（c）（d）分别绘出了四元树、四元完全树、二元树、二元完全树的例子。
6
在二元树中每个节点最多可以有两个儿子，一般称位于左边的为做儿子，右边的为右儿子。二元树是一种比较重要的外向树，好多实际问题均可用二元树表示。 下面举几个这方面的例子。
例 可用二元树表示算术表达式，如下列表达式 （v1 － v2 ） ／ v3 ＋ v4 （ v5 － v6 ／ v7 ） 这个表达式可用图4.1所示有序二元树表示。
例 很多计算机中的程序流程图可用有序二元树表示。如图4.2（a）所示的流程图及可用图4.2(b)的有序二元树表示。
7
5 树的应用
例1 有十个学生参加一次考试，试题10道。已知没有两个学生作对的题目是相同的。证明：在这10道题中可以找到一道试题，将这道试题取消后，每两个学生所做对的题目仍然不会相同。
证明：反证法。用10个结点vi (i=1,2…10)来表示10位学生。如果结论不成立，则对每一道试题h(1≤h≤10)，如果去掉h，比有两个学生vi 和 vj ，他们作对的题目是完全相同的，即原来vi 比 vj 或vj 比vi 恰好多做一题h，就在vi 和 vj 之间连一条边，并标上号h（如果有好几对，我们可以任取一对）。这样就得到一个具有10个结点，10条边的简单图，用G表示。有定理可知，G不是树。因为结点数与边数相同。G含有回路，设为 C=vi1vi2 …vikvi1
则沿着C走时，每通过一条边就相当于解出的题目增加或减少了一道题，并且增减的题目是互不相同的。现在对回路C来说。从 vi1 出发沿 C走一圈回到 vi1 ，就相当于vi1 做对的题目会增加一些，在减少一些题目，最后结果仍是 vi1 原来做对的题目，这是一个矛盾。
例2 用树形图可以表示家庭之间的关系。
设某祖宗A有两个儿子B、C， B与C分别有三个儿子D、E、F及G、H、I，而D与G分别又有一个儿子J及K。这样的家庭关系可以用如下树形图5.2 表示。
例3 设有28盏灯 ,拟共用一个电源插座.问需用多少块具有四插座的插线板.
8
解：将四叉树的每个分枝点看作是具有四插座的接线板，树也看作是电灯，则有（4－1）×i＝28－1，i＝9， 所以需要九块具有四插座的接线板。
例4 假设有一台计算机，它有一条加法指令，可计算三个树的和。如果要计算九个数的和，至少要执行几次家发指令。
解：若把这就个数看作是完全三叉树的九片叶子，则有（3－1）×i＝9－1，i＝4 。所以需要之心四次加法指令。
例5 如图5(a)中给出了一个连通图，求此图的生成树。 解：求图5(a)的生成树过程可用图5(b)到图5(e)表示。
例6 绘出公式（P∨（¬P∧Q））∧(（¬P∨Q)∧¬R）的根树表示 。
9
例7 在一棵有2个结点，次数为2 。4个结点次数为3 。其余结点都是叶的无向树中，共有几片叶子。
解：设X为其余结点。其中n＝2＋4＋X，m＝n－1＝X＋5 。由握手定理与结点和边的关系 2×2＋4×3＋X×1＝2×(X＋5)。 解得 X＝6。
例8 构造带权3、4、7、8、10、12的最优二元树。 解：这样的最优二元树的权为
w(T)＝3×4＋4×4＋7×3＋8×2＋10×2＋12×2＝109 构造过程如图5.8所示。
10
参考文献：
1. 卜月华著， 《图论及其应用》 ，南京：东南大学出版社，2000 。 2. 左孝凌等著， 《离散数学》， 上海：上海科学技术文献出版社， 2001 。 3. 徐洁磬著， 《离散数学导论》， 北京：高等教育出版社，2007 。
11
