离散作业布置及讲评(5)

1、闽南师范大学 计算机学院 2014年11月 第五部分 组合数学 作业 作业讲评 v14-5设无向图有10条边，3度与4度顶点各2个， 其余顶点的度数均小于3，问G中至少有几个顶 点？在最少顶点情况下，写出G的度数列， (G), (G) v解：设G的阶数为n,已知有2个3度顶点和2个4度 顶点，其余n-4个顶点的度数均小于或等于2， 由握手定理得 v2m=20=7,即G中至少有7个顶点，当D有7个顶 点时，其度数列为2，2，2，3，3，4，4， v(G) =4， (G) =3 作业讲评 v14-15 下列各数列中哪些是可简单图化的？对于 简单图化的试给出两个非同构的简单图。 v(2) (1,1,

2、2,2,3,3,5,5) (3) (2,2,2,2,3,3) v解： v(2)可简单图化 v v(3)可简单图化 作业讲评 v14-21 无向图G如图所示，求(1)求G图的全部点 割集和边集，并指出其中的割点和桥（割边） v(2) 求G的点连通度k(G) 和边连通度(G) v解:(1) 点割集2个：a,c,d,其中d是割点，边割 集有7个：e5,e1 e3e2 e4e1 e2e2 e3e3 e4e1 e4，其中是e5桥。 v(2)因为既有割点又有桥，所以k= =1 作业讲评 v14-15 下列各数列中哪些是可简单图化的？对于 简单图化的试给出两个非同构的简单图。 v(1) (2,3,3,5,5

3、,6,6) v解：(1) (2,3,3,5,5,6,6) 不可简单图化。 v（反证法）假设存在无向简单图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矛盾 作业讲评 v14-41 设G是无向图简单图， (G)=2,证明G中 存在长度大于或等于(G)+1的圈

4、。 v证明：用扩大路径法证明。 v设 = v0v1vl为极大路径（可用扩大路径法得 到），则l=(G) v由极大路径的性质（ 的两个端点v0与v0不与 外顶点相邻）以及简单图的定义可知，v0要达 到其度数d(v0 )= (G),必须与上至少(G)个顶 点相邻，设其为vi1= v1, vi2, vi于是，圈 v0vi1, vi2 ,vi v0,长度大于或等于(G)+1，式 中=(G) ，参见例14.8 作业讲评 v14-25 画出5阶3条边的所有非同构的无向简单图 v解：3条边产生6度，分配给5个顶点，按简单图 度数的要求，有4种分配方案： v(1) 1,1,1,1,2 (2) 0,1,1,2,

5、2 v(3) 0,1,1,1,3 (4) 0,0,2,2,2 v在同构意义下，每种方案对应一个简单图，4个 非同构的图如下图实线边所示： 作业讲评 v14-29 设G是n阶n+1条边的无向图，证明G中存 在顶点v，使得d(v)=3 v解: 反证法 v假设不然， v V(G),均有d(v)=2,则由握手 定理可得 2n+2=2m=2n,其中m为边数 这显然是矛盾的。 作业讲评 v14-43 有向图D，如图所示 v(1) D中有多少种非同构的圈？ v有多少种非同构的简单回路？ v(2) 求a到d的短程线和距离d v(3) 求d到a的短程线和距离d v解:(1)有2种非同构的圈:ede, aeba,

6、长度分别为2 与3; 有3种非同构的简单回路:ede, aeba, aedeba, 长度分别为2，3，5 (2) a到d的短程线为aed, d=2 (3) d到a的短程线为deba, d=3 作业讲评 v14-43 (4) 判断D中是哪类连通图？ v (5) 对D的基图求解(1),(2),(3) v解:(4)D中存在经过每个顶点的 v通路，但不存在经过每个顶点的 v回路，所以D是单向连通图。 (5)I. D的基图中有4种非同构的圈: ede, aeba, aedba, aedcba，长度分别为2，3，4，5，有7种非同构 的简单回路，其中除4种非同构的圈之外，还有 3种非圈的简单回路:aede

7、ba, aebdcba, aedebdcba, 长度分别为5，6，8； II. a到d的短程线有3条，d =2 III.d到a的短程线有3条，d =2 作业讲评 v14-44 有向图如图所示， v(1)D中v1到v4长度为1,2,3,4的通路各为几条? v(2) D中v1到v1长度为1,2,3,4的通路各为几条? v(3)D中长度为4的 通路有多少条，其中长为4的 回路为多少条？ v(4)D中长度小于或等于4的通路为多少条？其中 多少条为回路？ v(5)写出D的矩阵。 作业讲评 v14-44 解：利用D的邻接矩阵的前4次幂 1222 2344 1222 2465 0121 1222 0121

8、2223 1001 0121 1001 0221 0100 1001 0100 0021 43 2 AA AA 作业讲评 v(1)v1到到v4长度为长度为1,2,3,4的通路数分别为的通路数分别为0,0,2,2. v即即a14=0, a14(2)=0, a14(3)=2, a14(4)=2 v其中只有长度为其中只有长度为4的两条是非初级的简单通路（的两条是非初级的简单通路（ 定义意义下），见下图所示定义意义下），见下图所示. v 作业讲评 v(2) v1到v1长度为1,2,3,4的回路数分别为1,1,3,5. 即即a11=1, a11(2)=1, a11(3)=3, a11(4)=5 v其中长

9、度为1的是初级的(环)；长度为2的是复杂 的；长度为3的中有1条是复杂的，2条是初级的 ；长度为4的有1条是复杂的，有4条是非初级的 简单回路. v(3)D中长度为4的通路为44条（即A4中元素之和 ），其中有11条是回路（即A4中对角线元素之 和）。 作业讲评 v14-44解： v(4) D中长度小于或等于4的通路为88条（即A， A2，A3，A4中元素之和），其中有22条是回路 （即A，A2，A3，A4中所有对角线元素之和） （5）因为D中存在经过所有顶点的回路，是强 连通图，所以可达矩阵为4阶全1方阵。 作业讲评 v15-1 判断图15-12中哪些是欧拉图？对不是欧拉 图的至少要加多少条

10、边才能成为欧拉图？ v解：(a) (c)为欧拉图，它们均连通且都无奇度顶 点。 v(b)(d)都不是欧拉图。(b)虽然无奇度顶点，但不 连通；(d)既不连通、又有奇度顶点。 v要使(b)(d)变为欧拉图均至少加两条边，使其连 通并且无奇度顶点。 v 作业讲评 v15-11 彼得松图既不是欧拉图也不是哈密顿图， 至少加几条边才能使它成为欧拉图，又至少加 几条新边才能使它变成哈密顿图？ v解：彼得松图是10阶3-正则图，要想消除所有 奇数顶点，至少加5条边，才能使其变成所有顶 点都是4度的顶点，成为欧拉图。如(a)(b)所示。 v彼得松图是半哈密顿图，因而只需加一条新边 就可以得到哈密顿图，如图(

11、c)所示。 作业讲评 v15-13 今有2k(k=2)个人去完成任务，已知每个 人均能与另外k个人中的任何人组成一组（每组 2个人）完成他们共同熟悉的任务,问这2k个人能 否分成 k组，每组完成一项他们共同熟悉的任务 v解：做2k个无向简单图G=,其中，V=v|v 为去完成任务的人，E=(u.v)|u,vV,u!=v且u与 v有共同熟悉的任务，根据题设u,vV,有 vd(u)+d(v)=2k v由定理15.7可知，G中存在哈密顿通路，设 C=vi1vi2vi2k为G的一条哈密顿通路，则在C上 相邻的顶点均有共同熟悉的任务，于是，沿通 路将相邻的两个人各组成小组，则每个小组的 两个人都能去完成他

12、们共同的任务。 作业讲评 v15-21 用DijKstra标号法求下述图中从顶点v1到 其各顶点的最短路径和距离。 15.3 最短路问题与货郎担问题 v15-21(a)Dijkstra求解过程 步步 骤骤 v1v2v3v4v5v6v7v8 1(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(

13、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)* 最短路径最短路径v1v2v1v3v1v3v4v1v3v4v5v1v2v6v1v3v4 v5v7 v1v3v4v5 v7v8 15.3 最短路问题与货郎担问题 v15-21(b)Dijkstra求解过程 步步 骤骤 v1v2v3v4v5v6 1(v1,0)*(v1,)(v1,)(v1,)(v1,)(v1,) 2(v1,0)*(v1,4)(v1,8)(v1, )(v1,)(v1,) 3(v1,0)*(v

14、2,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 v 最短路径可能不唯一，如：v1v2v4v5和v1v2v5都 是v1到v5的最短路径，距离均为10。 作业讲评 v16-1 画出所有5阶和7阶非同构的无向树。 v解：方法步骤 v(1) 计算总度数，n阶无向树的边数m=n-1，由握 手定理可知顶点度数总和 v(2) 构造可能的度数列，将2n-2划分成n份，第i 份为对应顶点vi的度数

15、d(vi)， 且在这个数中奇偶数个； v按每个度数列画树，按不同的度数画出的树都 是不同构的，对同一个度数列可能画画出非构 的树。 i 1 ( v)222 n i dmn 1( )1,1 i d vnin 作业讲评 v16-1 v解: (1) 5阶无向树，n=5, m=4,度数之和为8，划 分成5份有3种方案： v1) 1，1，1，1，4 v2) 1，1，1，2，3 v3) 1，1，2，2，2 作业讲评 v16-1 解： v (2) 7阶无向树，n=7, m=6,度数之和为12，划分 成7份有7种方案： v1) 1,1,1,1,1,1,6 有1棵非同构树 v2) 1,1,1,1,1,2,5 有

16、1棵非同构树 v3) 1,1,1,1,1,3,4 有1棵非同构树 v4) 1,1,1,1,2,2,4 有2棵非同构树 v5) 1,1,1,1,2,3,3 有2棵非同构树 v6) 1,1,1,2,2,2,3 有3棵非同构树 v7) 1,1,2,2,2,2,2 有1棵非同构树 作业讲评 v16-2 一棵无向树T有5片树叶，3个2度分支点， 其的分支点都是3度顶点，问T有向个顶点？ v解：设3度顶点为x个，则阶数n=5+3+x=8+x, 边 数m=7+x,由握手定理 2m=14+2x=5*1+3*2+3x=11+3x v解得x=3，故n=8+3=11 作业讲评 v16-13 在下面两个正整数数列中，

17、哪个（些）能 充当无向树的度数列？若能，请画出3棵非同构 的无向树 v（1）1,1,1,1,2,3,3,4 （2）1,1,1,1,2,2,3,3 v解： v（1）不能，若能，则阶数n=8,m=7,度数之和应 为14，而此数列之和为16 v（2）能。 作业讲评 v16-7 证明：n(n=2)阶无向树不是欧拉图。 v证明： v当n=2时，无向树T至少有2片树叶，树叶是奇 度顶点， v故T不可能为欧拉图。 作业讲评 v16-25 求图16.17中两个带权图的最小生成树。 v解： va:W(T)=27 vb:W(T)=14 作业讲评 v16-31 根树T如图16.18所示，回答以下问题： v(1) T是几叉树？ (2