复旦大学计算机院赵一鸣离散数学图论习题.ppt

《复旦大学计算机院赵一鸣离散数学图论习题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、[5.14](1)若简单图G至多有2n个顶点,每个顶点度数至少为n,则G是连通图。(2)若简单图G至多有2n个顶点,每个顶点度数至少为n-1,则G是连通图?为什么?不一定[5.17]证明:对于任何简单图G,或者G是连通的或者K-G是连通的。[5.21]若G是一个多于四个顶点的任意简单图,则或者G或者K-G包含一条回路。[5.29](1)完全图Kn是欧拉图吗?是哈密顿图吗?(2)完全二分图是欧拉图吗?是哈密顿图吗?[6.7]设连通平面图G的顶点度数至少为3,且其面数f<12,证明G有一个面的边数小于

2、5。6.8设图G的顶点度数至少为3，且面数f<12，则G是4-面可着色的。6.12设G是简单图，有n个顶点(1)证明：若n<8，则G与中至少有一个是平面图；6.14:求(G)和*(G)[7.4](1)一棵树有两个顶点度数为2,一个顶点度数为3,三个顶点度数为4,问它有几个度数为1的顶点?(2)一棵树有ni个顶点度数为i,2ik,问它有几个度数为1的顶点?(3)设ni是树中度数为i的顶点数。证明:n1ni,(i=2,3,…,),或者n2>n1ni(i=3,4,…,)。[7.21](1

3、)试画一棵带权1,3,8,9,12,15,16的最优二分树。W(T)=(1+3)*5+8*4+9*3+(12+15+16)*2=20+32+27+86=165(2)试将最优二分树的霍夫曼算法推广到最优m分树上,其中m3。当t-1不是m-1的倍数时,则添加k个权为0的,使t-1+k是m-1的倍数.画一棵最优m分树方法是:这里t是权的个数设t个权w1,w2,,wt,w1w2wt首先构造t棵树,每棵树是一个顶点(即根),分别带权w1,w2,,wt。然后找出m个带最小权w1,w2,,wm的

4、顶点作为树叶,构造一棵m分树。于是得到n-m+1棵树,它们的根分别带权w1+w2++wm,wm+1,,wt,(此时w1+w2++wmwm+1不一定成立)。再在t-m+1棵树中找出m棵根带权最小的树,合并为一棵新的m分树,使得这m棵树根带的权为原m棵树根带的权之和,每一步选择m棵根带权最小的树合并为一棵m分树,重复这一过程直到只有一棵m分树为止。(3)画一棵带权1,2,3,4,5,6,7,8,9的最优三分树。W(T)=(1+2+3)*3+(7+8+4+5+6)*2+9=87(4)画一棵带权1

5、,2,3,4,5,6,7,8的最优三分树。8-1=7,加一个为0的权.W(T)=(1+2)*3+(3+4+5+6+7)*2+8=678-15：证明一棵树最多只有一个完美匹配。8-16：对于n=2,3,4,5，分别找出一个没有完美匹配的n-正则简单图的例子。8-17：证明二分图G具有完美匹配当且仅当对任意V的子集A，

6、Γ（A）

7、≥A成立。一、基本概念顶点度数，(G),定理5.1,5.2正则图，生成子图，导出子图，边导出子图，补图连通，连通图，连通分支(孤立点也是一个分支）出度，入度，竞赛图，强连通

8、，单向连通，弱连通定理5.4(所有度数大于1有回路）,定理5.7（二分图，奇回路）(半)Euler图,充要条件(半)Hamilton图,必要条件，充分条件(半)Euler有向图,充要条件(半)Hamilton有向图，有关结论平面图，面，内部面，外部面Euler公式,推论6.1，6.2库拉托斯基定理对偶图，定义，特点点着色，面着色，地图树，树叶，分支点，树的等价定义生成树，最小生成树，余树，枝，弦，定理7.3,G连通当且仅当G有生成树定理7.1和7.3就可获知,一个简单连通图如果不是树,就一定存在3

9、棵不同的生成树.m分树，正则m分树,最优树.点割，割点，点连通度(平凡或不连通)断集，割集，桥，边连通度(平凡或不连通)点连通度，边连通度，最小度数的关系定理8.1网络，容量，流量，可行流，最大流，割容量，最小割匹配，v关于M饱和，完美匹配，最大匹配，完全匹配交错路，增广路，定理8.8(最大匹配的充要条件。邻集，霍尔定理二、基本算法和计算最小权通路,路及权点着色数和面着色数最小生成树,最优树（w(T)).最大流，最小割，最大流的值，割容量三、证明及判别1.判别强连通，(半)Euler图,(半)Ha

10、milton图，找出(回)路(1)证明连通：任两点连通。反证，不连通：1）若干连通分支2）存在2个顶点，它们之间没有路(2)证明G为树：树的等价定义证明方法，利用树的等价定义；证明G有生成树，可证明G连通，再用定理7.3(3)利用Euler公式，推论6.1和6.2，及定理6.2的证明方法，结合定理5.1;做过的习题(4)连通度证明，定理8.1及做过习题证明方法(5)最大流标号法方法的正确性证明（算法停止时，为何就是最大流）(6)匹配的证明：定理8.8的证明方法；利用霍尔定理证明在图