离散作业布置及讲评(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…,viv0,长度大于或等于(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解:反证法假设不然，∀vV(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,vV,u!=v且u与v有共同熟悉的任务}，根据题设∀u,vV,有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)222nidmn1()1,1idvnin作业讲评16-1解:(1)5阶无向树，n=5,m=4,度数之和为8，划分成5份有3种方案：1)1，1，1，1，42)1，1，1，2，33)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)=27b: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)+