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

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,且其面数f12,证明G有一个面的边数小于5。6.8设图G的顶点度数至少为3，且面数f12，则G是4-面可着色的。6.12设G是简单图，有n个顶点(1)证明：若nn1ni(i=3,4,)。,7.21(1)试画一棵带权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分树上,其中m3。当t-1不是m-1的倍数时,则添加k个权为0的,使t-1+k是m-1的倍数.画一棵最优m分树方法是:这里t是权的个数设t个权w1,w2,wt,w1w2wt首先构造t棵树,每棵树是一个顶点(即根),分别带权w1,w2,wt。然后找出m个带最小权w1,w2,wm的顶点作为树叶,构造一棵m分树。,于是得到n-m+1棵树,它们的根分别带权w1+w2+wm,wm+1,wt,(此时w1+w2+wmwm+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,2,3,4,5,6,7,8的最优三分树。8-1=7,加一个为0的权.,W(T)=(1+2)*3+(3+4+5+6+7)*2+8=67,8-15：证明一棵树最多只有一个完美匹配。8-16：对于n=2,3,4,5，分别找出一个没有完美匹配的n-正则简单图的例子。8-17：证明二分图G具有完美匹配当且仅当对任意V的子集A，|（A）|A成立。,一、基本概念顶点度数，(G),定理5.1,5.2正则图，生成子图，导出子图，边导出子图，补图连通，连通图，连通分支(孤立点也是一个分支）出度，入度，竞赛图，强连通，单向连通，弱连通定理5.4(所有度数大于1有回路）,定理5.7（二分图，奇回路）,(半)Euler图,充要条件(半)Hamilton图,必要条件，充分条件(半)Euler有向图,充要条件(半)Hamilton有向图，有关结论平面图，面，内部面，外部面Euler公式,推论6.1，6.2库拉托斯基定理对偶图，定义，特点点着色，面着色，地图,树，树叶，分支点，树的等价定义生成树，最小生成树，余树，枝，弦，定理7.3,G连通当且仅当G有生成树定理7.1和7.3就可获知,一个简单连通图如果不是树,就一定存在3棵不同的生成树.m分树，正则m分树,最优树.点割，割点，点连通度(平凡或不连通)断集，割集，桥，边连通度(平凡或不连通),点连通度，边连通度，最小度数的关系定理8.1网络，容量，流量，可行流，最大流，割容量，最小割匹配，v关于M饱和，完美匹配，最大匹配，完全匹配交错路，增广路，定理8.8(最大匹配的充要条件。邻集，霍尔定理,二、基本算法和计算最小权通路,路及权点着色数和面着色数最小生成树,最优树（w(T).最大流，最小割，最大流的值，割容量三、证明及判别1.判别强连通，(半)Euler图,(半)Hamilton图，找出(回)路,(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的证明方法；利用霍尔定理证明在图论证明中，注意基本概念和结论的运用，通过加点，加边，