离散数学第十章基本图类及算法习题答案.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,设一个树中度为,k,的结点数是,n,k,(2,k),，求它的叶的数目。,解：设,n,个结点的树有,t,个叶，,由已知,n=t+,n,i,2(n-1)=t+in,i,消去式中的,n:2=t+(2-i)n,i,即：,t=(i-2)n,i,+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,不是叶，由道路唯一性，必有,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,图的一个子图，,它与,k,3,3,的细分图同构，所以,Peterson,图不是平面图。,设,G,是阶数不小于,11,的图，证明：,G,或,G,中至少有一个是非平面图。,证明：假设,G,和,G,都是平面图，可得,n(n-1)/2,6n-12,，,所以,n,2,-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),个奇数度结点的连通图。证明：,G,中必存在,k,条边不相重的简单道路,P,1,P,2,P,k,使得,E=E(P,1,),E(,P,2,)E(,P,k,).,证明：把,2k,个奇数度结点分成两两一组的,k,组，然后每组结点新加一条边，所得图为欧拉图，故存在欧拉回路。,再去掉欧拉回路中的,k,条新加入的边，得到,k,条互无重复边的道路,P,1,P,2,P,k,即为所求。,习题十三,2,v9,v6,v3,v1,求图中，中国邮递员问题的解。,解：图中有,4,个奇数度结点,v1,v6,v9,v3,求两两之间最短长度：,P,v1v6,=3 (v1v6),P,v1v9,=7 (v1v2v3v4v9),P,v1v3,=4 (v1v2v3),P,v6v9,=7 (v6v7v8v9),P,v3v6,=6 (v3v8v7v6),P,v3v9,=3 (v3v4v9),P,v1v6,和,P,v3v9,满足最小性要求，,复制,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,个人定期围圆桌而坐，商讨事务，他们希望每人每次两旁的人都和以前的不同，这样的安排最多有多少种？,解：将人看作图的结点，邻座关系作为图的边。每次安排方式对应一个,Hamilton,回路。因为每人每次两旁的人都和以前不同，所以每,2,种安排方式对应,2,个无公共边的,Hamilton,回路。,因每个人都可与其余人邻座，所以本问题转化为在,K,n,中找出所有无公共边的,Hamilton,回路的个数。,K,n,共有,n(n-1)/2,条边，每条,Hamilton,回路的长度为,n,，因此,K,n,中最多有,(n-1)/2,条无公共边的,Hamilton,回路。因此，最多有,(n-1)/2,种安排。,例如,n=7,时，共有,3,种就座方式，分别是：,1 2 3 4 5 6 7 1,1 3 5 7 2 4 6 1,1 4 7 3 6 2 5 1,用,2,种以上办法判别下图不是,Hamilton,图。,解：,用必要条件，选,7,个结点，去掉后剩,9,支。,注意观察，发现是平面二部图，因为所有回路都是偶长，那就可对结点进行二部划分：一部是,7,个，另一部是,9,个结点。但二部图要成为,Hamilton,图必须,2,部结点数相同。,2(f,4,(1),-f,4,(2),)+4(f,6,(1),-f,6,(2),)=0,f,4,(1),+f,4,(2),=12,f,6,(1),+f,6,(2),=1,无合理解。,习题十三,15,