您好,欢迎访问三七文档
当前位置:首页 > 电子/通信 > 综合/其它 > 离散作业布置及讲评(5)
闽南师范大学计算机学院2014年11月第五部分组合数学作业作业讲评14-5设无向图有10条边,3度与4度顶点各2个,其余顶点的度数均小于3,问G中至少有几个顶点?在最少顶点情况下,写出G的度数列,(G),(G)解:设G的阶数为n,已知有2个3度顶点和2个4度顶点,其余n-4个顶点的度数均小于或等于2,由握手定理得2m=20=2*3+2*4+(n-4)*2=2n+6解得n=7,即G中至少有7个顶点,当D有7个顶点时,其度数列为2,2,2,3,3,4,4,(G)=4,(G)=3作业讲评14-15下列各数列中哪些是可简单图化的?对于简单图化的试给出两个非同构的简单图。(2)(1,1,2,2,3,3,5,5)(3)(2,2,2,2,3,3)解:(2)可简单图化(3)可简单图化作业讲评14-21无向图G如图所示,求(1)求G图的全部点割集和边集,并指出其中的割点和桥(割边)(2)求G的点连通度k(G)和边连通度(G)解:(1)点割集2个:{a,c},{d},其中d是割点,边割集有7个:{e5},{e1e3}{e2e4}{e1e2}{e2e3}{e3e4}{e1e4},其中是e5桥。(2)因为既有割点又有桥,所以k==1作业讲评14-15下列各数列中哪些是可简单图化的?对于简单图化的试给出两个非同构的简单图。(1)(2,3,3,5,5,6,6)解:(1)(2,3,3,5,5,6,6)不可简单图化。(反证法)假设存在无向简单图G以它为度数列设d(v1)=2,d(v2)=d(v3)=3,d(v4)=d(v5)=5,d(v6)=d(v7)=6,由于只有7个顶点,v6,v7必与v1,…v5均相邻,v6与v7也相邻,因为d(v1)=2,故v1不能再与v2,…v5相邻,于是,要满足v4,v5的度数,它们必须与v2,v3均相邻,从而d(v2)=4,d(v3)=4,这与d(v2)=d(v3)=3矛盾作业讲评14-41设G是无向图简单图,(G)=2,证明G中存在长度大于或等于(G)+1的圈。证明:用扩大路径法证明。设=v0v1…vl为极大路径(可用扩大路径法得到),则l=(G)由极大路径的性质(的两个端点v0与v0不与外顶点相邻)以及简单图的定义可知,v0要达到其度数d(v0)=(G),必须与上至少(G)个顶点相邻,设其为vi1=v1,vi2,…,vi于是,圈v0vi1,…,vi2…,viv0,长度大于或等于(G)+1,式中=(G),参见例14.8作业讲评14-25画出5阶3条边的所有非同构的无向简单图解:3条边产生6度,分配给5个顶点,按简单图度数的要求,有4种分配方案:(1)1,1,1,1,2(2)0,1,1,2,2(3)0,1,1,1,3(4)0,0,2,2,2在同构意义下,每种方案对应一个简单图,4个非同构的图如下图实线边所示:作业讲评14-29设G是n阶n+1条边的无向图,证明G中存在顶点v,使得d(v)=3解:反证法假设不然,∀vV(G),均有d(v)=2,则由握手定理可得2n+2=2m=2n,其中m为边数这显然是矛盾的。作业讲评14-43有向图D,如图所示(1)D中有多少种非同构的圈?有多少种非同构的简单回路?(2)求a到d的短程线和距离da,d(3)求d到a的短程线和距离dd,a解:(1)有2种非同构的圈:ede,aeba,长度分别为2与3;有3种非同构的简单回路:ede,aeba,aedeba,长度分别为2,3,5(2)a到d的短程线为aed,da,d=2(3)d到a的短程线为deba,dd,a=3作业讲评14-43(4)判断D中是哪类连通图?(5)对D的基图求解(1),(2),(3)解:(4)D中存在经过每个顶点的通路,但不存在经过每个顶点的回路,所以D是单向连通图。(5)I.D的基图中有4种非同构的圈:ede,aeba,aedba,aedcba,长度分别为2,3,4,5,有7种非同构的简单回路,其中除4种非同构的圈之外,还有3种非圈的简单回路:aedeba,aebdcba,aedebdcba,长度分别为5,6,8;II.a到d的短程线有3条,da,d=2III.d到a的短程线有3条,dd,a=2作业讲评14-44有向图如图所示,(1)D中v1到v4长度为1,2,3,4的通路各为几条?(2)D中v1到v1长度为1,2,3,4的通路各为几条?(3)D中长度为4的通路有多少条,其中长为4的回路为多少条?(4)D中长度小于或等于4的通路为多少条?其中多少条为回路?(5)写出D的矩阵。作业讲评14-44解:利用D的邻接矩阵的前4次幂1222234412222465012112220121222310010121100102210100100101000021432AAAA作业讲评(1)v1到v4长度为1,2,3,4的通路数分别为0,0,2,2.即a14=0,a14(2)=0,a14(3)=2,a14(4)=2其中只有长度为4的两条是非初级的简单通路(定义意义下),见下图所示.作业讲评(2)v1到v1长度为1,2,3,4的回路数分别为1,1,3,5.即a11=1,a11(2)=1,a11(3)=3,a11(4)=5其中长度为1的是初级的(环);长度为2的是复杂的;长度为3的中有1条是复杂的,2条是初级的;长度为4的有1条是复杂的,有4条是非初级的简单回路.(3)D中长度为4的通路为44条(即A4中元素之和),其中有11条是回路(即A4中对角线元素之和)。作业讲评14-44解:(4)D中长度小于或等于4的通路为88条(即A,A2,A3,A4中元素之和),其中有22条是回路(即A,A2,A3,A4中所有对角线元素之和)(5)因为D中存在经过所有顶点的回路,是强连通图,所以可达矩阵为4阶全1方阵。作业讲评15-1判断图15-12中哪些是欧拉图?对不是欧拉图的至少要加多少条边才能成为欧拉图?解:(a)(c)为欧拉图,它们均连通且都无奇度顶点。(b)(d)都不是欧拉图。(b)虽然无奇度顶点,但不连通;(d)既不连通、又有奇度顶点。要使(b)(d)变为欧拉图均至少加两条边,使其连通并且无奇度顶点。作业讲评15-11彼得松图既不是欧拉图也不是哈密顿图,至少加几条边才能使它成为欧拉图,又至少加几条新边才能使它变成哈密顿图?解:彼得松图是10阶3-正则图,要想消除所有奇数顶点,至少加5条边,才能使其变成所有顶点都是4度的顶点,成为欧拉图。如(a)(b)所示。彼得松图是半哈密顿图,因而只需加一条新边就可以得到哈密顿图,如图(c)所示。作业讲评15-13今有2k(k=2)个人去完成任务,已知每个人均能与另外k个人中的任何人组成一组(每组2个人)完成他们共同熟悉的任务,问这2k个人能否分成k组,每组完成一项他们共同熟悉的任务解:做2k个无向简单图G=V,E,其中,V={v|v为去完成任务的人},E={(u.v)|u,vV,u!=v且u与v有共同熟悉的任务},根据题设∀u,vV,有d(u)+d(v)=2k由定理15.7可知,G中存在哈密顿通路,设C=vi1vi2…vi2k为G的一条哈密顿通路,则在C上相邻的顶点均有共同熟悉的任务,于是,沿通路将相邻的两个人各组成小组,则每个小组的两个人都能去完成他们共同的任务。作业讲评15-21用DijKstra标号法求下述图中从顶点v1到其各顶点的最短路径和距离。§15.3最短路问题与货郎担问题15-21(a)Dijkstra求解过程步骤v1v2v3v4v5v6v7v81(v1,0)**(v1,∞)(v1,∞)(v1,∞)(v1,∞)(v1,∞)(v1,∞)(v1,∞)2(v1,0)*(v1,6)(v1,3)*(v1,∞)(v1,∞)(v1,∞)(v1,∞)(v1,∞)3(v1,0)*(v1,6)(v1,5)*(v3,8)(v1,∞)(v3,11)(v1,∞)4(v1,0)*(v1,6)*(v4,6)(v1,∞)(v3,11)(v4,11)5(v1,0)*(v4,6)*(v2,12)(v3,11)(v4,11)6(v1,0)*(v2,12)(v5,7)*(v4,11)7(v1,0)*(v2,12)(v2,10)*8(v2,12)*最短路径v1v2v1v3v1v3v4v1v3v4v5v1v2v6v1v3v4v5v7v1v3v4v5v7v8®§15.3最短路问题与货郎担问题15-21(b)Dijkstra求解过程步骤v1v2v3v4v5v61(v1,0)**(v1,∞)(v1,∞)(v1,∞)(v1,∞)(v1,∞)2(v1,0)*(v1,4)(v1,8)(v1,∞)(v1,∞)(v1,∞)3(v1,0)*(v2,6)*(v1,7)*(v2,10)(v1,∞)4(v1,0)*(v2,7)*(v2,10)(v3,14)5(v1,0)*(v2,10)(v4,8)6(v1,0)*(v2,10)*最短路径v1v2v1v2v3v1v2v4v1v2v5v1v2v4v6®最短路径可能不唯一,如:v1v2v4v5和v1v2v5都是v1到v5的最短路径,距离均为10。作业讲评16-1画出所有5阶和7阶非同构的无向树。解:方法步骤(1)计算总度数,n阶无向树的边数m=n-1,由握手定理可知顶点度数总和(2)构造可能的度数列,将2n-2划分成n份,第i份为对应顶点vi的度数d(vi),且在这个数中奇偶数个;按每个度数列画树,按不同的度数画出的树都是不同构的,对同一个度数列可能画画出非构的树。i1(v)222nidmn1()1,1idvnin作业讲评16-1解:(1)5阶无向树,n=5,m=4,度数之和为8,划分成5份有3种方案:1)1,1,1,1,42)1,1,1,2,33)1,1,2,2,2作业讲评16-1解:(2)7阶无向树,n=7,m=6,度数之和为12,划分成7份有7种方案:1)1,1,1,1,1,1,6有1棵非同构树2)1,1,1,1,1,2,5有1棵非同构树3)1,1,1,1,1,3,4有1棵非同构树4)1,1,1,1,2,2,4有2棵非同构树5)1,1,1,1,2,3,3有2棵非同构树6)1,1,1,2,2,2,3有3棵非同构树7)1,1,2,2,2,2,2有1棵非同构树作业讲评16-2一棵无向树T有5片树叶,3个2度分支点,其的分支点都是3度顶点,问T有向个顶点?解:设3度顶点为x个,则阶数n=5+3+x=8+x,边数m=7+x,由握手定理2m=14+2x=5*1+3*2+3x=11+3x解得x=3,故n=8+3=11作业讲评16-13在下面两个正整数数列中,哪个(些)能充当无向树的度数列?若能,请画出3棵非同构的无向树(1)1,1,1,1,2,3,3,4(2)1,1,1,1,2,2,3,3解:(1)不能,若能,则阶数n=8,m=7,度数之和应为14,而此数列之和为16(2)能。作业讲评16-7证明:n(n=2)阶无向树不是欧拉图。证明:当n=2时,无向树T至少有2片树叶,树叶是奇度顶点,故T不可能为欧拉图。作业讲评16-25求图16.17中两个带权图的最小生成树。解:a:W(T)=27b:W(T)=14作业讲评16-31根树T如图16.18所示,回答以下问题:(1)T是几叉树?(2)T的树高为几(3)T有几个内点(4)T有几个分支点?解:(1)T是4叉树(2)T的树高为4(3)T有5个内点(4)T有6个分支点作业讲评16-37画一棵权为3,4,5,6,7,8,9的最优2叉树,并计算出它的权。421776514112598437权W(T)=2*(8+9)+3*(5+6+7)+
本文标题:离散作业布置及讲评(5)
链接地址:https://www.777doc.com/doc-3357655 .html