内容发布更新时间 : 2024/12/23 23:40:52星期一 下面是文章的全部内容请认真阅读。

（chord）。对每一树枝t，T–t分为两个连通分支T1，T2，那么t及两端点分别在T1，T2中的弦组成G的一个割集，它被称为枝t-割集（t-cut set）；而每一条弦e与T中的通路构成一回路，它被称为弦e-回路（e-circuit）。

定理9.20 在连通无向图G中，任一回路与任一割集均有偶数条公共边。 定理9.21 设G为一连通无向图，T是G的生成树， S = {e1, e2, e3,…,ek}

为枝e1-割集，那么e1必在弦ei-回路中（i = 2，3,…，k），不在其它弦e-回路中。 定理9.22 设G为一连通无向图，T是G的生成树， C =（e1, e2,…,ek）

为弦e1-回路，那么e1必定在枝ei-割集中（i = 2，3,…，k），不在其它任何枝e1-割集中。

定理9.23 设G是连通边赋权图，且各边的权互不相等。若C是G中的一条回路，那么C上权最大的边e必定不在G的最小生成树上。

9.3.3 根树

递归地定义根树的概念。

定义9.12 树T称为根树（rooted tree），如果 （1）T为一孤立结点v0 。v0又被称为T的树根。

（2）T1，T2,…,Tk为以v1，v2,…，vk为树根的根树，T由T1，T2,…,Tk及与v1，v2,…，vk相邻的结点v0所组成。v0称为T的树根。 定义9.13 在定义9.12中，

（1）v1，v2,…，vk称为v0的儿子，v0称为它们的父亲。vi，vj同为一顶点v的儿子时，称它们为兄弟。 （2）顶点间的父子关系的传递闭包称为顶点间的祖孙关系。即当vi为vi+1 (i = 1, 2,…, l-1)的父亲时，v1是vl的祖先，vl为v1的子孙。 （3）根树T自身及以它的树根的子孙为根的根树（T的子图），均称为T的子树（subtree），后者又称为T的真子树。

定义9.14 除了树叶外，每个结点都有两个儿子的根树称为完全2元树（binary tree）。 完全2元树有以下性质。

定理9.24 完全2元树的顶点个数n必定是奇数。 定理9.25 完全二元树中叶的数目l? 定理9.26 完全二元树高h满足 ?log2(n?1)?1??h?n?1,其中n为树的顶点数。 2n?1 2这里n为二元树的顶点个数，[a]表示大于等于a的最小整数。

定义9.15 每个结点都至多有两个儿子的根树称为二元树（quasibinary tree）。类似地，每个结点都至多有n个儿子的根树称为n元树。 对各分支结点的诸儿子规定了次序（例如左兄右弟）的n 元树称为n元有序树；若对各分支结点的已排序的诸儿子规定了在图示中的位置（例如左、中、右），那么该n元有序树又称n元位置树。2元位置树各分支结点的左右儿子分别称为左儿子和右儿子。

二元位置树被大量用于数据的表示，例如表示算术表达式及各种字符串。这时，常常需要遍访每一个结点，以下是三种遍访二元树的算法。 （1）先根算法

（1.1） 访问二元树树根r。

11

（1.2） 如果r有左儿子，那么又以先根算法遍访r的左子树（以r的左儿子为根的子树）。

（1.3） 如果r有右儿子，那么又以先根算法遍访r的右子树（以r的右儿子为根的子树）。

（2）中根算法

（2.1） 如果二元树树根r有左儿子，那么以中根算法遍访r的左子树。 （2.2） 访问二元树树根r。

（2.3） 如果二元树树根r有右儿子，那么又以中根算法遍访r的右子树。 （3）后根算法

（3.1） 如果二元树树根r有左儿子，那么以后根算法遍访r的左子树。 （3.2） 如果二元树树根r有右儿子，那么又以后根算法遍访r的右子树。 （3.3） 访问二元树树根r。

习题解答

练习9.3

1．证明定理9.12、定理9.13。 证（1）定理9.12

由于树无回路，即回路长度为0。根据定理9.1，树是二分图。又根据练习9.1之9，树是可2-着色的。

又由于森林的诸连通分支均为树，故森林也是二分图，可2-着色。

（2）定理9.13

由于树无回路，因而无论怎样切割、贯通操作也不可能以K3,3、K5为子图。根据定理9.10，树是平面图，面数为1（无回路）。

又由于森林的诸连通分支均为树，因此森林也是平面图，面数为1 。

2．证明定理9.16之（3）?（4），（4）?（5）。 证（1）（3）?（4）已知T无回路，添加任一边时产生唯一的回路，欲证T连通且删去任一边时便不再连通。

假设T不连通，则至少存在两个顶点vi，vj不可达。在T中添加关联vi、vj的边e，根据(3)，产生唯一回路C，且e在C中（否则与T无回路矛盾）。从C中删去e，vi、vj仍然可达，与假设矛盾。所以，T连通。

假设e是关联vi、vj的边，删除e后T仍然连通，即vi、vj之间有一条不经过e的通路。则在T中，该通路与e构成一回路，与前提矛盾。所以，删去任一边时T不再连通。

（2）（4）?（5）已知T连通，但删去任一边时便不再连通，欲证T的任意两个不同顶点之间有且仅有一条通路。

因为T连通，所以任意两个不同顶点之间至少有一条通路。现假设存在两个顶点vi、vj，vi到vj有不止一条通路，则两条通路构成一闭路径，从闭路径上删去任一边e，T – e 仍连通，与前提矛盾。所以，任意两个不同顶点之间有且仅有一条通路。 3．（1）试画出所有具有五个顶点的、不同构的树。 （2）描述恰有两片叶的树的特征，并证明你的描述是正确的。 解（1） 12

（2）恰有两片叶的树是一条链，除两端的两个悬挂点外，其余皆为2度分支点。证明如下 ：

设树共有n个顶点，其中恰有2片叶，其余n–2个节点的度数均≥2，而它们的平均度数为

2m?22(n?1)?2??2n?2n?2所以，除叶之外，其余节点的度数均为2。为证明它是一条链，用数学归纳法。

显然，当n=2时，树为具有两片叶的链。

假设n=k (k≥2) 时，恰有两片叶的树为一条链。现在考虑n=k+1时的情况。设v为两片叶之一，T’=T–v，则T’仍为一棵恰有两片叶的树（否则添加v后叶的数目将超过2）。根据假设，T’为一链，而在T中，与v相关联的节点只能是T’中的叶，因为其余节点的度数已经达到2，再与v关联将超过2，也就是说，T也是一条链。

归纳完成，命题得证。

4．一棵树有两个2度顶点，1个3度顶点，3个4度顶点，问：它有几个1度的顶点。 解 假设共有k个1度顶点，则

k + 2?2 + 1?3 + 3?4 = 2m = 2(n–1) = 2(k+2+1+3–1) 解得k=9，即共有9个1度顶点

5．一棵树有n2个2度顶点，有n3个3度顶点，……, 有nk个k度顶点，问：它有几个1度的顶点。

解 假设共有n1个1度顶点，则

?ni?1ki?i?2(?ni?1)i?1kkn1??ni(i?2)?2i?2

6. （1）证明：n 个顶点的树，其顶点度数之和为2n – 2。 ?（2）设d1, d2, … , dn 为n个正整数，n≥2,并且

?di?1ni?2n?2。

证明：有树T使T的n个顶点的度数分别是d1, d2, … , dn 。

证 （1）由于

?di?1ni?2m，而m=n – 1（T为树）

故

?di?1ni?2n?2

（2）用数学归纳法。

当n=2时，因为d1 + d2 = 2，d1, d2为正整数，所以d1 =d2 =1，显然两节点组成的树满足要求。

假设当n=k (k≥2) 时，命题成立，现在考虑n=k+1的情况。

13

∵ d1, d2, … , dk+1 为k+1个正整数，并且

?di?1k?1i?2k

k?1i?1 ∴d1, d2, … , dk+1中必存在某个di =1（1≤i≤k+1），否则

?dk?1i?1i?2k?2，

d1, d2, … , dk+1中必存在某个dj≥2（1≤j≤k+1），否则

?di?k?1?2k，

不失一般性，设i＜j，对于 k个正整数d1, d2, … ,di-1, di+1, … , dj–1, … , dk+1，它们的和为2k–2，根据归纳假设，存在一棵有k个节点的树T，其各节点的度数与这k个整数一一对应。现在T上添加顶点vi，并增加vi与vj的关联边，得到T’，T’仍为树，且vj的度数从dj–1变成了dj，vi的度数为1 (di)，其余各节点度数不变，即T’各节点的度数分别与d1, d2, … , dk+1一一对应。 归纳完成，命题得证。 7．给出图9.35的最小生成树，并写出关于这一生成树的枝割集系和弦回路系。 89106475311 图9.35 解 最小生成树如下图所示 89106475311 共有4条枝，5条弦，因为各边权重各不相同，所以以下用相应的权来记边 枝3-割集是{3，8，9，10} 枝4-割集是{4，7，9，10，11} 枝5-割集是{5，10，11} 枝6-割集是{6，7，8，9，10，11} 弦7-回路是{7，4，6} 弦8-回路是{8，3，6} 弦9-回路是{9，3，4，6} 弦10-回路是{10，3，4，5，6} 弦11-回路是{11，4，5，6}

8．证明定理9.22。

证 设S为任一枝ei -割集（i=2, 3, …, k），例如S为枝e2 -割集，则C与S有偶数条公共边，其中之一是e2，由于C中e1为弦，其余均为枝，而S中除e2外均为弦，所以C与S还应有的公共边只能是e1，故e1在枝e2 -割集中。由于证明过程对一切ei（i=2, 3, …, k）均

14

成立，因此定理的前半部分得证。

设S为枝e -割集，而e≠e2, e3, …, ek，若e1在S中，那么C与S只能有e1一条公共边，因为S中只有e为枝，而C中只有e1为弦，故e1?S， 定理的后半部分得证。

由此，定理得证。

9. 判断下列断言的真假：

（1）连通无向图G的任何边，都是G的某一棵生成树的枝。 （2）连通无向图G的任何边，都是G的某一棵生成树的弦。 解 （1）假。因为环不是任何生成树的枝。

（2）假。G的割边不是任一生成树的弦。

10．设G为连通无向图，证明：

（1）G的任一生成树T的关于G的补G – T 中不含有G的割集。

（2）G的任一割集S的关于G的补G –S（从G中删除所有S中的边）中不含有G的生成树。

证（1）用反证法。假设存在某个T，使得G – T 中含有G的割集，那么根据割集的定义，T不连通，与T为树矛盾，所以，原命题得证。

（2）用反证法。假设存在某个S，使得G – S 中含有G的生成树，则根据树的定义，G – S仍连通，与S为割集矛盾。所以，原命题得证。

11．设C是连通无向图G的一条回路，a , b是C中任意两条边。证明：存在G的割集S，使得S与C仅以a , b为公共边。

证 设T为以a为枝，以b为弦的G的生成树（这总是可以办到的，因为a、b同在一条回路C上），则C为T的弦b-回路。用S表示枝a-割集，因为a?C，根据定理9.22，b必在S中。所以，a、b同为C和S的公共边。除此而外，C、S不可能再有其它的公共边，因为S中只有枝a，C中只有弦b。定理得证。

12．T是连通无向图G的生成树的充分必要条件是：T是G的连通生成子图，且T有n – 1条边，这里n是G的顶点数。

证 必要性。

设T是G的生成树，那么T是G的生成子图，且T为树，即T是连通图，m = n – 1 。 充分性。

设T连通且m = n – 1，那么根据树的定义，可知T为树。又因为T是G的生成子图，故 T是G的生成树。

13．设T1，T2为连通无向图G的两棵不同的生成树，边a在T1中，但它不在T2中。证明：T2中存在边b , 使b不在T1中，并且（T1 – a）? {b}以及（T2 – b）? {a}都是图G的生成树。

证 由于a在T1中，而不在T2中，故存在T1的枝a-割集S，T2的弦a-回路C。根据定理9.20，S和C除了a之外至少还有一条公共边，记为b，则b为T2的枝，T1的弦，即b属于T2，不属于T1。

又因为对T1来说，a属于弦b-回路，对T2来说，b属于弦a-回路，因此

15