离散数学王元元习题解答 (10)

(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

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4