《离散数学第十章基本图类及算法习题答案.ppt》由会员分享,可在线阅读,更多相关《离散数学第十章基本图类及算法习题答案.ppt(13页珍藏版)》请在三一办公上搜索。
1、设一个树中度为k的结点数是nk(2k),求它的叶的数目。解:设n个结点的树有t个叶,由已知n=t+ni2(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的道路是树中最长道路,如果u或v不是叶,由道路唯一性,
2、必有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是阶数不小于11的图,证明:G或G中至少有一个是非平
3、面图。证明:假设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,于是m=2(n-1).,习题十二 9,设G=(V,E)是一个具有2k(k0
4、)个奇数度结点的连通图。证明:G中必存在k条边不相重的简单道路P1,P2,Pk,使得E=E(P1)E(P2)E(Pk).证明:把2k个奇数度结点分成两两一组的k组,然后每组结点新加一条边,所得图为欧拉图,故存在欧拉回路。再去掉欧拉回路中的k条新加入的边,得到k条互无重复边的道路P1,P2,Pk,即为所求。,习题十三 2,v9,v6,v3,v1,求图中,中国邮递员问题的解。解:图中有4个奇数度结点v1,v6,v9,v3,求两两之间最短长度:Pv1v6=3(v1v6),Pv1v9=7(v1v2v3v4v9),Pv1v3=4(v1v2v3),Pv6v9=7(v6v7v8v9),Pv3v6=6(v3v
5、8v7v6),Pv3v9=3(v3v4v9),Pv1v6和Pv3v9满足最小性要求,复制v1v6和v3v4v9的边,图中欧拉回路即为所求解。,v2,v4,v5,v7,v8,v10,2,2,1,1,1,1,3,3,v11,3,4,4,1,5,5,6,2,习题十三 5,证明:连通图G是平面欧拉图当且仅当其对偶图是平面二部图。证明:“”:当G是平面欧拉图时,G的点度是偶数,对应G*的面度应是偶数,说明G*的回路都是偶长回路,从而G*是二部图。“”:当G*是平面二部图时,它的面度都是偶数,因而G的各点度均为偶数,故G是平面欧拉图。,n个人定期围圆桌而坐,商讨事务,他们希望每人每次两旁的人都和以前的不同
6、,这样的安排最多有多少种?解:将人看作图的结点,邻座关系作为图的边。每次安排方式对应一个Hamilton回路。因为每人每次两旁的人都和以前不同,所以每2种安排方式对应2个无公共边的Hamilton回路。因每个人都可与其余人邻座,所以本问题转化为在Kn中找出所有无公共边的Hamilton回路的个数。Kn共有n(n-1)/2条边,每条Hamilton回路的长度为n,因此Kn中最多有(n-1)/2条无公共边的Hamilton回路。因此,最多有(n-1)/2种安排。例如n=7时,共有3种就座方式,分别是:1 2 3 4 5 6 7 11 3 5 7 2 4 6 11 4 7 3 6 2 5 1,用2种以上办法判别下图不是Hamilton图。解:用必要条件,选7个结点,去掉后剩9支。注意观察,发现是平面二部图,因为所有回路都是偶长,那就可对结点进行二部划分:一部是7个,另一部是9个结点。但二部图要成为Hamilton图必须2部结点数相同。2(f4(1)-f4(2)+4(f6(1)-f6(2)=0f4(1)+f4(2)=12f6(1)+f6(2)=1无合理解。,习题十三 15,