离散数学第十章基本图类及算法习题答案.ppt
《离散数学第十章基本图类及算法习题答案.ppt》由会员分享,可在线阅读,更多相关《离散数学第十章基本图类及算法习题答案.ppt(13页珍藏版)》请在三一文库上搜索。
1、设一个树中度为k的结点数是nk(2k),求它的叶的数目。 解:设n个结点的树有t个叶, 由已知 n=t+ni 2(n-1)=t+ ini 消去式中的n: 2= t+ (2-i)ni 即: t= (i-2)ni + 2,i=2,i=2,i=2,i=3,习题十一 1,设e是连通图的一条边,证明: e是割边当且仅当e含于G的每个生成树中. 证明: ()如果割边e不在G的某个生成树中,则G- e仍有生成树,即仍连通,与割边的定义相矛盾. ()如果e是每个生成树的公共边,则去掉e后G- e不再连通,即e为G 的割边.,习题十一 10,树T中最长道路的起点和终点必都是T的叶. 证明: 设u到v的道路是树中
2、最长道路,如果u或v不是叶,由道路唯一性,必有u或v的邻接结点不在该道路上,因此这条道路可延长至w,与最长条件矛盾。,习题十一 2,用Kruskal算法求图的一个最小生成树。 解:边按序排列:ab,gc,eg,ed,af,fd,fe,dc,fb,bd,ag,bc 按算法构造生成树边集为:ab,gc,eg,ed,af,fd, W(T)=8.,a,g,f,e,d,c,b,1,3,2,1,3,2,1,1,4,4,6,5,习题十一 12,用Kruskal定理证明Peterson图不是平面图。 证明:下面是Peterson图的一个子图, 它与k3,3的细分图同构,所以Peterson图不是平面图。,设G
3、是阶数不小于11的图,证明:G或G中至少有一个是非平面图。 证明:假设G和G都是平面图,可得n(n-1)/2 6n-12, 所以 n2-13n+24 0 可得n10,与已知矛盾。所以原题得证。,习题十二 3,证明:少于30条边的简单平面图至少有一个顶点的度不大于4。 证明:假设 5,可得 5n 2m 由平面性,2m 6n-12 再将n 12 代入5n 2m ,得m 30,与已知矛盾。所以原题得证。, n 12,习题十二 5,若一平面图与其对偶图同构,则称这个平面图为自对偶图。推导自对偶图必须满足的结点数n与边数m的关系,并找出一个自对偶图。 解:如果G是自对偶图,在欧拉公式中必有n=f, 于是
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 第十 基本 算法 习题 答案
链接地址:https://www.31doc.com/p-2142458.html