离散数学(第30讲习题课5)分析课件.ppt

《离散数学(第30讲习题课5)分析课件.ppt》由会员分享，可在线阅读，更多相关《离散数学(第30讲习题课5)分析课件.ppt（27页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

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

4、65.5.会会用用哈哈密密顿顿图图和和含含哈哈密密顿顿道道路路的的充充分分条条件件来来判判断断某某些些图图是是哈哈密密顿顿图图或或是是否否含含有有哈哈密密顿顿道道路；路；6.6.会会用用破破坏坏哈哈密密顿顿图图的的某某些些必必要要条条件件的的方方法法判判断某些图不是哈密顿图断某些图不是哈密顿图7.7.严格区分哈密顿图的充分条件和必要条件严格区分哈密顿图的充分条件和必要条件8.8.理解判断哈密顿图的充分必要条件理解判断哈密顿图的充分必要条件9.9.了解推销商问题的分枝定界求解方法了解推销商问题的分枝定界求解方法2023/1/82023/1/8计算机学院计算机学院7 7例一例一 证证明明当当每每个

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

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

7、13527V2V6V4V1V3V5费用费用=18=182023/1/82023/1/8计算机学院计算机学院1111例三例三 设设图图G G是是具具有有6 6个个顶顶结结点点、1212条条边边的的无无向向简单图简单图,证明图证明图 G G 是哈密顿图。是哈密顿图。证证明明：已已知知一一个个图图是是哈哈密密顿顿图图的的充充分分条条件件是是：图中任意不同两点的度数之和大于等于图中任意不同两点的度数之和大于等于n n。（反反证证法法）假假设设图图G G中中存存在在两两个个结结点点v v1 1,v v2 2,其度数之和不大于等于其度数之和不大于等于6,6,即即 d(vd(v1 1)+d(v)+d(v2

8、2)5)5。2023/1/82023/1/8计算机学院计算机学院1212而而删删去去这这两两个个点点后后,至至多多删删去去图图 G G 中中的的 5 5 条条边边。由由于于图图G G是是具具有有6 6个个顶顶点点,1212条条边边的的无无向向简简单单图图,删删去去顶顶点点v v1 1,v v2 2后后,得得到到的的子子图图为为:具具有有4 4个个结结点点,至至少少7 7条条边边的的无无向向简简单单图图,但但这这样样的的无无向向简简单单图图不不存存在在(4(4阶阶无无向向简简单单图图最最多多有有6 6条条边边),),由由此此证证明明图图G G中中任任意意不不同同两两点点的的度数之和大于等于度数之

9、和大于等于6,6,图图G G是哈密顿图。是哈密顿图。2023/1/82023/1/8计算机学院计算机学院13131,1,解：设解：设 L L 是叶的数目，是叶的数目，m m 是树的边数是树的边数 由握手定理由握手定理 由树的定义由树的定义习题十一习题十一2023/1/82023/1/8计算机学院计算机学院14141313、设设简简单单连连通通图图 G=G=（V V，E E）的的边边集集 E E 恰恰好好可可以以分分划划为为 G G 的的两两个个生生成成树树的的边边集集。证证明明：如如果果 G G 中中恰恰有有两两个个 4 4 度度以以下下的的结结点点 u u 和和 v v，则，则 uvuv E

10、 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的度数之和大于等于的度数之和大于等于 3.3.2023/1/82023/1/8计算机

11、学院计算机学院1515而而在在 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)，由握手定理，由握手定理，4(n-1)4(n-2)+54(n-1)4(n-2)+5，矛盾，矛盾所以所以 u

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

13、=2(t-1)L=2(t-1)2023/1/82023/1/8计算机学院计算机学院17172121、证明证明:正则二叉树必有奇数个结点。正则二叉树必有奇数个结点。证明：证明：由由正正则则二二叉叉树树的的定定义义，其其叶叶结结点点的的个个数必为偶数，设叶数为数必为偶数，设叶数为 t t，分支数为，分支数为 i i 由定理由定理 11.5 (m-1)i=t-111.5 (m-1)i=t-1 m=2 m=2 i=t-1 i=t-1 即分支点数是奇数即分支点数是奇数 故结点数故结点数 n=i+t=n=i+t=奇数，且奇数，且n=2t-1n=2t-1，即即 t=t=（n+1n+1）/2/22023/1/

14、82023/1/8计算机学院计算机学院1818习题十二习题十二3 3、证：（反证法）、证：（反证法）设设 G=G=（n n，m m）和）和 G=G=（n n，mm）都是平面图）都是平面图由由G G和和GG的定义的定义 m+m=n(n-1)/2m+m=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，n1

15、1 n11 时时,9n-972,9n-972 （n-11)n-11)2 2+9n-972+9n-972与上式相矛盾，与上式相矛盾，故故 G G 与与 GG至少有一个是非平面图至少有一个是非平面图2023/1/82023/1/8计算机学院计算机学院19194 4、证证明明：具具有有6 6个个结结点点、1212条条边边的的简简单单连连通通平平面图，它的面的度数都是面图，它的面的度数都是3 3。证：证：由由 Euler Euler 公式，公式，n-m+f=2n-m+f=2 6-12+f=2 f=8 6-12+f=2 f=8 即面数为即面数为 8 8，对每个面，其度数对每个面，其度数 3 3 总面度总

16、面度 3 38=248=24 总面度总面度=2=2m=24m=24 每个面的度数为每个面的度数为 3 32023/1/82023/1/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矛盾矛盾 至少存在一个顶点的度数不超过至少存在一个顶点

17、的度数不超过4 42023/1/82023/1/8计算机学院计算机学院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

18、 v1 1构成一个构成一个HamiltonHamilton圈。圈。2 2）v v1 1v v4k+14k+1 E E，则，则 2023/1/82023/1/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图图2023/1/82023/1/8计算机学院计算机学院232313

19、13、今今有有n n个个人人,已已知知他他们们中中的的任任何何二二人人合合起起来认识其余的来认识其余的 n n-2 2个人。个人。证明证明:1 1）当当 n n 3 3 时时,这这 n n 个个人人能能排排成成一一列列、使使得得中中间间的的任任何何人人都都认认识识两两旁旁的的人人,而而站站在在两两端端的人认识左边的人认识左边(或右边或右边)的人。的人。2 2）当当 n n 4 4 时时,这这 n n 个个人人能能排排成成一一个个圆圆圈圈,使得每个人都认识两旁的人。使得每个人都认识两旁的人。证明：作证明：作 n n 阶简单无向图阶简单无向图 G=G=V V，E E,V=V=n n个个人人的的集集

20、合合,E=(u,v)E=(u,v)u,u,v v V V u v u u v u 与与 v v 认识认识.u,v V,u,v V,2023/1/82023/1/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,u,v v 不不相相邻邻,则则对对 w w V-u,v,V-u,v,w w 必必与与 u u 和和 v v 都都相相邻邻。否否则则,比比如如u u 和和w w 不不相相邻邻,则则v,v,w w 都都不不邻邻接接u,u,于于是是u u 和和w w 合合起起来来至至多多

21、与与其其余余的的n n 3 3 个个人人认认识识,与与已已知知条条件件不符不符.因而因而 d(u)+d(v)2(n-2)d(u)+d(v)2(n-2)。1)1)当当 n n 3 3 时时,2(n-2)2(n-2)n-1,n-1,因因此此无无论第论第 (1)(1)或或 (2)(2)种情形种情形,都有都有 d(u)+d(v)n d(u)+d(v)n 1 1,2023/1/82023/1/8计算机学院计算机学院2525 由由定定理理 13.4 13.4 知知 G G 中中有有哈哈密密顿顿道道路路、道道路路上上的的人人按按在在道道路路中中的的顺顺序序排排成成一一列列,即即满满足要求。足要求。2 2）当

22、当 n n 4 4 时时,2(n-2)2(n-2)n,n,因因此此无无论论第第 (1)(1)或或 (2)(2)种情形种情形,都有都有 d(u)+d(v)n,d(u)+d(v)n,由由定定理理13.5 13.5 知知G G 中中有有哈哈密密顿顿圈圈,所所有有的的人按圈中的顺序排成一个圆圈人按圈中的顺序排成一个圆圈,即满足要求。即满足要求。2023/1/82023/1/8计算机学院计算机学院26265 5、设设G G是是(n,m)(n,m)简单图。若简单图。若 ,证明证明G G必是哈密顿图。必是哈密顿图。证：（反证法）假设证：（反证法）假设G G不是哈密尔顿图，则不是哈密尔顿图，则2023/1/82023/1/8计算机学院计算机学院2727 因为因为G G除结点除结点s,ts,t外的其余外的其余n-2n-2结点之间最多可结点之间最多可以构成完全图，所以以构成完全图，所以 2m(n-2)(n-3)+n+nn2m(n-2)(n-3)+n+nn2 2-3n+6=(n-1)(n-2)+4-3n+6=(n-1)(n-2)+4从而从而与已知与已知 矛盾，故结论成立。矛盾，故结论成立。