离散数学(第30讲习题课5)

冯伟森Email：fws365@02二月2023离散数学计算机学院2023/2/2计算机学院2主要内容习题课五2023/2/2计算机学院3第十一章深刻理解树（六个等价命题）及生成树、树枝、树补的定义，掌握生成树的主要性质，并能灵活应用它们；熟练地应用Kruskal算法求最小生成树；掌握根树、m叉树、完全m叉树、正则m叉树、最优树的概念,熟练掌握Huffman算法，并使用它求最优二叉树；第十二章深刻理解平面图、面、对偶图的定义；熟记欧拉公式和二个平面图的必要条件,并能使用它们来判断图的非平面性；了解库拉托夫斯基（Kuratowski）定理和细分图的概念；2023/2/2计算机学院42023/2/2计算机学院5第十三章深刻理解欧拉图和欧拉道路的定义，对于给定的图能判断它是否为欧拉图或存在欧拉道路；掌握Fleury算法并会用Fleury算法求出欧拉图中的欧拉回路；理解中国邮递员问题算法并会用中国邮递员算法求出无向图中的欧拉回路；深刻理解哈密顿道路及其哈密顿图、图的闭包概念；2023/2/2计算机学院6会用哈密顿图和含哈密顿道路的充分条件来判断某些图是哈密顿图或是否含有哈密顿道路；会用破坏哈密顿图的某些必要条件的方法判断某些图不是哈密顿图严格区分哈密顿图的充分条件和必要条件理解判断哈密顿图的充分必要条件了解推销商问题的分枝定界求解方法2023/2/2计算机学院7例一

证明当每个结点的度数大于等于3时，不存在有7条边的连通简单平面图。证明:(反证法)设图的边数m=7

由题意，d(Vi)≥3，Vi为结点则由握手定理，则∴结点的个数不超过4个，而结点个数为4的完全图的边数为6,

故应有环或平行边，不是简单连通平面图。2023/2/2计算机学院8例二

有6个村庄Vi，i=l，2，…，6欲修建道路使村村可通。现已有修建方案如下带权无向图所示，其中边表示道路，边上的数字表示修建该道路所需费用，问应选择修建哪些道路可使得任二个村庄之间是可通的且总修建费用最低?要求写出求解过程，画出符合要求的最低费用的道路网络图并计算其费用。2023/2/2计算机学院92023/2/2计算机学院1013527V2V6V4V1V3V5费用=182023/2/2计算机学院11例三

设图G是具有6个顶结点、12条边的无向简单图,证明图G是哈密顿图。证明：已知一个图是哈密顿图的充分条件是：图中任意不同两点的度数之和大于等于n。（反证法）假设图G中存在两个结点v1,v2,其度数之和不大于等于6,即

d(v1)+d(v2)≤5。

2023/2/2计算机学院12而删去这两个点后,至多删去图G中的5条边。由于图G是具有6个顶点,12条边的无向简单图,删去顶点v1,v2后,得到的子图为:具有4个结点,至少7条边的无向简单图,但这样的无向简单图不存在(4阶无向简单图最多有6条边),由此证明图G中任意不同两点的度数之和大于等于6,图G是哈密顿图。2023/2/2计算机学院131,解：设L是叶的数目，m是树的边数由握手定理

由树的定义习题十一2023/2/2计算机学院1413、设简单连通图G=（V，E）的边集E恰好可以分划为G的两个生成树的边集。证明：如果G中恰有两个4度以下的结点u和v，则uvE。证：（反证法）设E=E1∪E2

，E1∩E2=φT（E1），T（E2）是G的两棵生成树。如uv∈E，则uv∈E1

或uv∈E2。不妨设uv∈E1，由于T（E1）是G的生成树，则u或v必有其中一个同其它结点相邻，即在T（E1）中，u和v的度数之和大于等于3.2023/2/2计算机学院15而在T（E2）中，u和v分别同其它结点相邻，且相关联的边∈E2.故在G中，

d(u)+d(v)≥5.∵T（E1），T（E2）是G的两棵生成树

∴m（E1）＋m（E2）=2(n-1)

2m(G)=2(m（E1）＋m（E2）)=4(n-1)，由握手定理，4(n-1)≥4(n-2)+5，矛盾所以uv

E。2023/2/2计算机学院1616、证明:在完全二叉树中，边的数目等于2（t-1），式中t是叶的数目。证明：设叶结点的个数为t，分支数为i，边的数目为L，由定理11.5(m-1)i=t-1∵m=2∴i=t-1由完全二叉树的定义和握手定理，

2L=t+3i-1=t+3(t-1)-1=4t-4∴L=2(t-1)2023/2/2计算机学院1721、

证明:正则二叉树必有奇数个结点。证明：由正则二叉树的定义，其叶结点的个数必为偶数，设叶数为t，分支数为i

由定理11.5(m-1)i=t-1∵m=2∴i=t-1即分支点数是奇数故结点数n=i+t=奇数，且n=2t-1，即t=（n+1）/22023/2/2计算机学院18习题十二3、证：（反证法）设G=（n，m）和G′=（n，m′）都是平面图由G和G′的定义m+m′=n(n-1)/2由定理12.5

m≤3n-6,m′≤3n-6∴m+m′=n(n-1)/2≤6n-12整理上式有n2-13n+24=(n-11)2+9n-97≤0又∵（n-11)2≥0，n≥11时,9n-97≥2∴（n-11)2+9n-97≥2与上式相矛盾，故G与G′至少有一个是非平面图2023/2/2计算机学院194、证明：具有6个结点、12条边的简单连通平面图，它的面的度数都是3。证：由Euler公式，n-m+f=2∴6-12+f=2f=8

即面数为8，∵对每个面，其度数≥3∴总面度≥3×8=24∵总面度=2×m=24∴每个面的度数为32023/2/2计算机学院205、证明：少于30条边的简单平面至少有一个顶点的度不大于4。证：（反证法）设所有顶点的度数≥5由定理12.5m≤3n-6∵

5n/2≤m≤3n-6∴n≥12

则m≥5n/2≥5×12/2=30

与m＜30矛盾∴至少存在一个顶点的度数不超过42023/2/2计算机学院21习题十三10、证明:4k+l阶的所有2k正则简单图都是哈密顿图。证：∵G是2k正则图，∴对任意的u、v∈G，d(u)+d(v)=4k

由定理13.4,在G中存在一条Hamilton道路，设为：

v1v2,…,v4k+11）v1v4k+1∈E，则v1v2,…,v4k+1v1构成一个Hamilton圈。

2）v1v4k+1E，则

2023/2/2计算机学院22∵G的阶数为4k+1∴

（否则d(v4k+1)=4k-1-2k=2k-1

与d(v4k+1)=2k矛盾)

可构造即为G的一个Hamilton圈，故G是一个Hamilton图2023/2/2计算机学院2313、今有n个人,已知他们中的任何二人合起来认识其余的n-2个人。证明:1）当n≥3时,这n个人能排成一列、使得中间的任何人都认识两旁的人,而站在两端的人认识左边(或右边)的人。2）当n≥4时,这n个人能排成一个圆圈,使得每个人都认识两旁的人。证明：作n阶简单无向图G=＜V，E＞,

V=n个人的集合,E={(u,v)︱u,v∈V∧u≠v∧u与v认识}.u,v∈V,2023/2/2计算机学院24(1)若u,v相邻,则

d(u)+d(v)≥(n-2)+2=n。(2)若u,v不相邻,则对w∈V-{u,v},w必与u和v都相邻。否则,比如u和w不相邻,则v,w都不邻接u,于是u和w合起来至多与其余的n−3个人认识,与已知条件不符.

因而d(u)+d(v)≥2(n-2)。

1)当n≥3时,2(n-2)≥n-1,因此无论第(1)或(2)种情形,都有

d(u)+d(v)≥n−1,2023/2/2计算机学院25

由定理13.4知G中有哈密顿道路、道路上的人按在道路中的顺序排成一列,即满足要求。

2）当n≥4时,2(n-2)≥n,因此无论第(1)或(2)种情形,都有

d(u)+d(v)≥n,

由定理13.5知G中有哈密顿圈,所有的人按圈