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

1、冯伟森冯伟森Email：2022年年5月月8日星期日日星期日2022-5-82022-5-8计算机学院计算机学院2 2主要内容主要内容2022-5-82022-5-8计算机学院计算机学院3 3第十一章第十一章1.1. 深刻理解树（六个等价命题）及生成树、树深刻理解树（六个等价命题）及生成树、树枝、树补的定义，掌握生成树的主要性质，枝、树补的定义，掌握生成树的主要性质，并能灵活应用它们；并能灵活应用它们；2.2. 熟练地应用熟练地应用 KruskalKruskal 算法求最小生成树；算法求最小生成树；3.3. 掌握根树、掌握根树、m m叉树、完全叉树、完全m m叉树、正则叉树、正则m m叉树、叉

2、树、最优树的概念最优树的概念, ,熟练掌握熟练掌握 Huffman Huffman 算法，并算法，并使用它求最优二叉树；使用它求最优二叉树；第十二章第十二章1.1. 深刻理解平面图、面、对偶图的定义；深刻理解平面图、面、对偶图的定义；2.2. 熟记欧拉公式和二个平面图的必要条件熟记欧拉公式和二个平面图的必要条件, , 并能并能使用它们来判断图的非平面性；使用它们来判断图的非平面性；3.3. 了解库拉托夫斯基（了解库拉托夫斯基（ KuratowskiKuratowski）定理和细）定理和细分图的概念；分图的概念；2022-5-82022-5-8计算机学院计算机学院4 42022-5-82022-

3、5-8计算机学院计算机学院5 5第十三章第十三章1.1.深刻理解欧拉图和欧拉道路的定义，对于深刻理解欧拉图和欧拉道路的定义，对于给定的图能判断它是否为欧拉图或存在欧给定的图能判断它是否为欧拉图或存在欧拉道路；拉道路；2.2.掌握掌握 FleuryFleury 算法并会用算法并会用 FleuryFleury 算法求算法求出欧拉图中的欧拉回路；出欧拉图中的欧拉回路；3.3.理解中国邮递员问题算法并会用中国邮递理解中国邮递员问题算法并会用中国邮递员算法求出无向图中的欧拉回路；员算法求出无向图中的欧拉回路；4.4.深刻理解哈密顿道路及其哈密顿图、图的深刻理解哈密顿道路及其哈密顿图、图的闭包概念；闭包概

4、念；2022-5-82022-5-8计算机学院计算机学院6 65.5. 会用哈密顿图和含哈密顿道路的充分条件来会用哈密顿图和含哈密顿道路的充分条件来判断某些图是哈密顿图或是否含有哈密顿道判断某些图是哈密顿图或是否含有哈密顿道路；路；6.6. 会用破坏哈密顿图的某些必要条件的方法判会用破坏哈密顿图的某些必要条件的方法判断某些图不是哈密顿图断某些图不是哈密顿图7.7. 严格区分哈密顿图的充分条件和必要条件严格区分哈密顿图的充分条件和必要条件8.8. 理解判断哈密顿图的充分必要条件理解判断哈密顿图的充分必要条件9.9. 了解推销商问题的分枝定界求解方法了解推销商问题的分枝定界求解方法2022-5-8

5、2022-5-8计算机学院计算机学院7 7例一例一 证明当每个结点的度数大于等于证明当每个结点的度数大于等于 3 3 时，时，不存在有不存在有 7 7 条边的连通简单平面图。条边的连通简单平面图。证明证明:(:(反证法反证法) ) 设图的边数设图的边数m=7m=7 由题意，由题意，d(Vd(Vi i) 3) 3，V Vi i为结点为结点则由握手定理，则由握手定理， 则则结点的个数不超过结点的个数不超过4 4个，而结点个数为个，而结点个数为4 4的完全的完全图的边数为图的边数为 6,6, 故应有环或平行边，不是简单连通平面图。故应有环或平行边，不是简单连通平面图。)(2 iiVdm3143)(7

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

7、用。最低费用的道路网络图并计算其费用。2022-5-82022-5-8计算机学院计算机学院9 92022-5-82022-5-8计算机学院计算机学院101013527V2V6V4V1V3V5费用费用=18=182022-5-82022-5-8计算机学院计算机学院1111例三例三 设图设图G G是具有是具有6 6个顶结点、个顶结点、1212条边的无向条边的无向简单图简单图, , 证明图证明图 G G 是哈密顿图。是哈密顿图。 证明：已知一个图是哈密顿图的充分条件是：证明：已知一个图是哈密顿图的充分条件是：图中任意不同两点的度数之和大于等于图中任意不同两点的度数之和大于等于n n。 （反证法）假设

8、图（反证法）假设图G G中存在两个结点中存在两个结点v v1 1, ,v v2 2, , 其度数之和不大于等于其度数之和不大于等于6, 6, 即即 d(vd(v1 1)+ d(v)+ d(v2 2) 5) 5。 2022-5-82022-5-8计算机学院计算机学院1212 而删去这两个点后而删去这两个点后, , 至多删去图至多删去图 G G 中的中的 5 5 条边。条边。 由于图由于图G G是具有是具有6 6个顶点个顶点, 12, 12条边的无条边的无向简单图向简单图, , 删去顶点删去顶点v v1 1, ,v v2 2后后, , 得到的子图为得到的子图为: : 具有具有4 4个结点个结点,

9、, 至少至少7 7条边的无向简单图条边的无向简单图, , 但但这样的无向简单图不存在这样的无向简单图不存在(4(4阶无向简单图最阶无向简单图最多有多有6 6条边条边), ), 由此证明图由此证明图G G中任意不同两点的中任意不同两点的度数之和大于等于度数之和大于等于6, 6, 图图G G是哈密顿图。是哈密顿图。2022-5-82022-5-8计算机学院计算机学院1313 设简单连通图设简单连通图 G=G=（V V，E E）的边集）的边集 E E 恰恰好可以分划为好可以分划为 G G 的两个生成树的边集。证明：的两个生成树的边集。证明：如果如果 G G 中恰有两个中恰有两个 4 4 度以下的结点

10、度以下的结点 u u 和和 v v，则则 uvuv E E。证：（反证法）设证：（反证法）设E=EE=E1 1 E E2 2 ，E E1 1 E E2 2= = T T（E E1 1），）， T T（E E2 2）是）是 G G 的两棵生成树。的两棵生成树。如如 uvuvE E，则则 uvuvE E1 1 或或 uvuvE E2 2。不妨设不妨设 uvuvE E1 1，由于，由于T T（E E1 1）是）是 G G 的生成树，的生成树，则则 u u 或或 v v 必有其中一个同其它结点相邻，即必有其中一个同其它结点相邻，即在在T T（E E1 1）中，）中，u u和和v v的度数之和大于等于的

11、度数之和大于等于 3.3.例四例四2022-5-82022-5-8计算机学院计算机学院1414而在而在 T T（E E2 2）中，）中， u u 和和 v v 分别同其它结点相邻，分别同其它结点相邻，且相关联的边且相关联的边 E E2 2. .故在故在 G G 中，中， d(u)+d(v) 5.d(u)+d(v) 5. T T（E E1 1），）， T T（E E2 2）是）是 G G 的两棵生成树的两棵生成树 m m（E E1 1）m m（E E2 2）=2(n-1)=2(n-1) 2 2m m(G)=2(G)=2(m m（E1E1）m m（E2E2）)=4(n-1)=4(n-1)，由握手定

12、理，由握手定理，5)2(4)()()()(2v nvdudwdwdmuwGw、4(n-1) 4(n-2)+54(n-1) 4(n-2)+5，矛盾，矛盾所以所以 uvuv E E 。2022-5-82022-5-8计算机学院计算机学院15151,1,解：设解：设 L L 是叶的数目，是叶的数目， m m 是树的边数是树的边数 由握手定理由握手定理 由树的定义由树的定义mLknikk22 12 Lnmikk)2( 2)2(222222 kinkLLnLknikkikkikk习题十一习题十一2022-5-82022-5-8计算机学院计算机学院1616 1616、证明证明: :在完全在完全二叉树二叉树

13、中，边的数目等于中，边的数目等于 2 2（t-1t-1），式中），式中t t是叶的数目。是叶的数目。 证明：设叶结点的个数为证明：设叶结点的个数为t t，分支数为，分支数为 i i，边边的数目为的数目为L L， 由由定理定理 11.5 11.5 (m-1)(m-1)i i=t-1=t-1 m=2 m=2 i i=t-1=t-1 由由完全二叉树的定义和握手定理完全二叉树的定义和握手定理， 2L=t+3i-1=t+3(t-1)-1=4t-42L=t+3i-1=t+3(t-1)-1=4t-4 L=2(t-1)L=2(t-1)2022-5-82022-5-8计算机学院计算机学院1717 2121、 证

14、明证明: :正则二叉树必有奇数个结点正则二叉树必有奇数个结点。 证明：证明： 由正则二叉树的定义，其叶结点的个由正则二叉树的定义，其叶结点的个数必为偶数，设叶数为数必为偶数，设叶数为 t t，分支数为，分支数为 i i 由定理由定理 11.5 (m-1)11.5 (m-1)i i=t-1=t-1 m=2 m=2 i i=t-1 =t-1 即分支点数是奇数即分支点数是奇数 故结点数故结点数 n=n=i+ti+t= = 奇数，且奇数，且n=2t-1n=2t-1， 即即 t=t=（n+1n+1）/2/22022-5-82022-5-8计算机学院计算机学院1818习题十二习题十二3 3、证：（反证法）

15、、证：（反证法）设设 G=G=（n n，m m）和）和 G=G=（n n，mm）都是平面图）都是平面图由由G G和和GG的定义的定义 m+mm+m=n(n-1)/2=n(n-1)/2由定理由定理 1 12 2. .5 5 m 3n-6, m3n-6m 3n-6, m3n-6 m+m=n(n-1)/2 6n-12 m+m=n(n-1)/2 6n-12整理上式有整理上式有 n n2 2-13n+24=(n-11)-13n+24=(n-11)2 2+9n-97 0+9n-97 0又又（ n-11)n-11)2 2 0 0，n11 n11 时时,9n-972,9n-972 （n-11)n-11)2 2

16、+9n-972+9n-972与上式相矛盾，与上式相矛盾，故故 G G 与与 GG至少有一个是非平面图至少有一个是非平面图2022-5-82022-5-8计算机学院计算机学院19194 4、证明：具有证明：具有6 6个结点、个结点、1212条边的简单连通平条边的简单连通平面图，它的面的度数都是面图，它的面的度数都是3 3。证：证： 由由 Euler Euler 公式，公式， n-n-m+fm+f=2=2 6-12+f=2 f=8 6-12+f=2 f=8 即面数为即面数为 8 8， 对每个面，其度数对每个面，其度数 3 3 总面度总面度 3 38=248=24 总面度总面度=2=2m=24m=2

17、4 每个面的度数为每个面的度数为 3 32022-5-82022-5-8计算机学院计算机学院20205 5、证明：少于证明：少于3030条边的简单平面至少有一个顶条边的简单平面至少有一个顶点的度不大于点的度不大于4 4。证：（反证法）证：（反证法） 设所有顶点的度数设所有顶点的度数 5 5 由定理由定理12.5 m3n-612.5 m3n-6 5n/2 m3n-6 n125n/2 m3n-6 n12 则则 m5n/25m5n/2512/2=30 12/2=30 与与 m m3030矛盾矛盾 至少存在一个顶点的度数不超过至少存在一个顶点的度数不超过4 42022-5-82022-5-8计算机学院

18、计算机学院2121习题十三习题十三1010、证明证明:4k+l:4k+l阶的所有阶的所有2k2k正则简单图正则简单图都是哈密都是哈密顿图。顿图。证：证： G G是是2k2k正则图，正则图， 对任意的对任意的u u、vGvG，d(u)+d(v)=4kd(u)+d(v)=4k 由定理由定理13.4,13.4,在在G G中存在一条中存在一条HamiltonHamilton道道路，设为：路，设为： v v1 1v v2 2, ,v,v4k+14k+1 1 1）v v1 1v v4k+14k+1EE， 则则v v1 1v v2 2, ,v,v4k+14k+1v v1 1构成一个构成一个HamiltonH

19、amilton圈。圈。 2 2）v v1 1v v4k+14k+1 E E，则，则 邻邻接接与与1221,vvvvkiii 2022-5-82022-5-8计算机学院计算机学院2222 G G的阶数为的阶数为4k+14k+1 （否则（否则d(vd(v4k+14k+1)=4k-1-2k=2k-1)=4k-1-2k=2k-1 与与d(vd(v4k+14k+1)=2k)=2k矛盾矛盾) ) 可构造可构造 即为即为G G的一个的一个HamiltonHamilton圈，故圈，故G G是一个是一个HamiltonHamilton图图中中的的一一个个点点邻邻接接，必必与与11114221, kiiikvvv

20、vEvvkit 14 设设141411,vvvvvvttikki 2022-5-82022-5-8计算机学院计算机学院23231313、 今有今有n n个人个人, , 已知他们中的任何二人合起已知他们中的任何二人合起来认识其余的来认识其余的 n n- -2 2个人。个人。 证明证明: : 1 1）当）当 n 3 n 3 时时, , 这这 n n 个人能排成一列、使个人能排成一列、使得中间的任何人都认识两旁的人得中间的任何人都认识两旁的人, , 而而站在站在两两端端的人认识左边的人认识左边 ( (或右边或右边) ) 的人。的人。2 2）当）当 n 4 n 4 时时, , 这这 n n 个人能排成

21、一个圆圈个人能排成一个圆圈, , 使得每个人都认识两旁的人。使得每个人都认识两旁的人。证明：作证明：作 n n 阶简单无向图阶简单无向图 G= G= V V，E E , , V= nV= n个人的集合个人的集合, E=(, E=(u,vu,v) ) u, v V u, v V u v u u v u 与与 v v 认识认识. . u, v V,u, v V,2022-5-82022-5-8计算机学院计算机学院2424 (1)(1)若若 u, v u, v 相邻相邻, , 则则 d(u)+d(v) (nd(u)+d(v) (n- -2)+2=n2)+2=n。 (2)(2)若若 u, v u, v

22、 不相邻不相邻, , 则对则对 w V-w V-u,vu,v, w , w 必与必与 u u 和和 v v 都相邻。都相邻。 否则否则, , 比如比如u u 和和w w 不不相邻相邻, , 则则v, w v, w 都不邻接都不邻接u,u,于是于是u u 和和w w 合起来合起来至多与其余的至多与其余的n n 3 3 个人认识个人认识, , 与已知条件与已知条件不符不符. . 因而因而 d(u)+ d(v) 2(n-2)d(u)+ d(v) 2(n-2)。 1) 1) 当当 n 3 n 3 时时, 2(n-2) n-1, , 2(n-2) n-1, 因此无因此无论第论第 (1) (1) 或或 (2) (2) 种情形种情形, , 都有都有 d(u) + d(v) n d(u) + d(v) n 1 1, , 202