浙江理工大学本科生课程离散数学-图

图离散数学答案浙江理工大学本科生课程计算机科学与技术系6.19无向图如图6.51所示

(1)G中最少的圈长为几？最短的圈长为几？

(2)G中最长的简单回路长度为几？最短的简单回路长度为几？

(3)求出图的△、δ、k、λ解:(1)最长为4,v1v2v3v6v1

最短为1v1v1

(2)最长为10e1e2e3e4e5e6e7e8e9e10

最短为1e1

(3)G的最小度δ=3（v4,v5)

G的最大度△=4（v1,v2,v9,v6)

G的点连通度k=1

（割点v3)

G的边连通度λ=2(边割集{e2,e10},{e5,e9}等)6.19e2e5e6e4e3e1e9e8e7e11v2e10v3v4v6v5v16.206.20有向图D如图6.52所示

(1)D中有多少条非同构的初级回路圈？有多少条非同构的简单回路？

(2)求a到d的短程线路和距离

(3)求d到a的短程线路和距离

(4)D是哪类连通图？解:(1)初级回路（圈）c1,c2,c1≌c2,当且仅当c1与c2长度相等。有3条初级回路非同构，长度分别为1,2,3.

非同构的简单回路非同构，除以上3条，还有1条

若在定义意义下，不同起始点的回路看成不同，初级回路6条，简单回路6+4=10条abced6.20(2)D中a到d的短程线是唯一的，即为aed,d<a,d>=2

(3)D中d到a的短程线是唯一的，即为deba,d<d,a>=3

(4)D中存在经过每个顶点至少一次的通路，如aedbc

所以是单向连通图，但没有经过每个顶点至少一次的回路，所以D不是强连通图。

6.316.31今有甲、乙、丙三人去完成任务a,b,c,已知甲能胜任a,b,c;乙能胜任a,b;丙能胜任b,c,做三部图G=(v1,v2,E),

其中v1={甲、乙、丙},v2={a,b,c},E={(u,v)|u∈v1,v∈v2}，并且u能胜任v},请画出G的图形，并且根据图形给尽量多的分配任务方案，使得每个人去完成自己能胜任的任务。解：方案1：甲完成a,乙完成b,丙完成c

方案2：甲完成b,乙完成a,丙完成c

方案3：甲完成c,乙完成a,丙完成b

6.406.40若工厂生产由6种不同颜色的纱织成的双色布，已知在品种中，每种颜色至少分别和其他5种颜色中的3种相搭配，证明可以排出3中双色布，他们至少有6种不同的颜色。解：将有关事物之间的关系转化成无向图，证明所得图为哈密顿图。

无向简单图G=(V,E),其中：

V={v|v为6种颜色的纱之一}，则|V|=6

E={（u,v)|u,v∈V,且u≠v,且u与v能搭配}

由已知条件可知，u,v∈V，都有

d(u)+d(v)≥3+3=6由定理可知，存在哈密顿回路，设c=Vi1….Vi6Vi1为其中一条，由G的构造可知，C上任何两个顶点当且仅当它们代表的颜色的纱能织成双色布。

比如Vi1和Vi2合，Vi3和Vi4合，Vi5和Vi6分别织成符合要求的三种双色布，并用上6种不同的颜色。6.456.45已知7阶连通平面图G中有6个面，试求G的边数m解：由于G为连通平面图，有欧拉公式n–m+r=2

所以m=n+r-2=7+6-2=116