离散作业布置及讲评

离散作业布置及讲评()演示文稿目前一页\总数二十七页\编于十六点（优选）离散作业布置及讲评()目前二页\总数二十七页\编于十六点作业讲评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的短程线和距离d<a,d>(3)求d到a的短程线和距离d<d,a>解:(1)有2种非同构的圈:ede,aeba,长度分别为2与3;有3种非同构的简单回路:ede,aeba,aedeba,长度分别为2，3，5(2)

a到d的短程线为aed,d<a,d>=2(3)d到a的短程线为deba,d<d,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条，d<a,d>=2

III.d到a的短程线有3条，d<d,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次幂目前十二页\总数二十七页\编于十六点作业讲评(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)，且在这个数中奇偶数个；按每个度数列画树，按不同的度数画出的树都是不同构的，对同一个度数列可能画画出非构的树。目前二十二页\总数二十七页\编于十六点作业讲评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