发布时间 : 星期六 文章离散数学答案 屈婉玲版 第二版 高等教育出版社课后答案更新完毕开始阅读8e3402dcbb1aa8114431b90d6c85ec3a86c28be3
(1)求G的全部点割集与边割集,指出其中的割点和桥; (2) 求G的点连通度k(G)与边连通度?(G)。
ae2be3解:点割集: {a,b},(d)
e1de5ee4c
边割集{e2,e3},{e3,e4},{e1,e2},{e1,e4}{e1,e3},{e2,e4},{e5}
k(G)=?(G)=1
23、求G的点连通度k(G)、边连通度?(G)与最小度数?(G)。
解:k(G)?2、?(G)?3 、?(G)?4
28、设n阶无向简单图为3-正则图,且边数m与n满足2n-3=m问这样的无向图有几种非同构的情况?
?3n?2m解:? 得n=6,m=9.
2n?3?m? 31、设图G和它的部图G的边数分别为m和m,试确定G的阶数。
解:m?m??1?1?8(m?m)n(n?1) 得n? 2245、有向图D如图
(1)求v2到v5长度为1,2,3,4的通路数;
(2)求v5到v5长度为1,2,3,4的回路数; (3)求D中长度为4的通路数; (4)求D中长度小于或等于4的回路数;
(5)写出D的可达矩阵。
v1v4v5v2v3
解:有向图D的邻接矩阵为:
?0??1A??0??1?0??0??4A4??0??4?0?0001??01??0100??000001?,A2??01??0100??00?201010???010??20??002??02010?A3??20??002??02?00200???200??020?200?
?020?004??0004??01??0400??520004? A?A2?A3?A4??21??0400??42?254040???215??522?215?
?522?254??(1)v2到v5长度为1,2,3,4的通路数为0,2,0,0; (2)v5到v5长度为1,2,3,4的回路数为0,0,4,0; (3)D中长度为4的通路数为32; (4)D中长度小于或等于4的回路数10;
?1??1(4)出D的可达矩阵P??1??1?1?1111??1111?1111?
?1111?1111??第十六章部分课后习题参考答案
1、画出所有5阶和7阶非同构的无向树.
2、一棵无向树T有5片树叶,3个2度分支点,其余的分支点都是3度顶点,问T有几个顶点? 解:设3度分支点x个,则
5?1?3?2?3x?2?(5?3?x?1),解得x?3
T有11个顶点
3、无向树T有8个树叶,2个3度分支点,其余的分支点都是4度顶点,问T有几个4度分支点?根据T的度数列,请至少画出4棵非同构的无向树。
解:设4度分支点x个,则
8?1?2?3?4x?2?(8?2?x?1),解得x?2
度数列
4、棵无向树T有ni (i=2,3,…,k)个i度分支点,其余顶点都是树叶,问T应该有几片树叶? 解:设树叶x片,则
ni?i?x?1?2?(ni?x?1),解得x?(i?2)ni?2 评论:2,3,4题都是用了两个结论,一是握手定理,二是m?n?1 5、n(n≥3)阶无向树T的最大度解:2,n-1
6、若n(n≥3)阶无向树T的最大度解:n-1
7、证明:n(n≥2) 阶无向树不是欧拉图.
=2,问T中最长的路径长度为几? 至少为几?最多为几?
证明:无向树没有回路,因而不是欧拉图。 8、证明:n(n≥2) 阶无向树不是哈密顿图. 证明:无向树没有回路,因而不是哈密顿图。 9、证明:任何无向树T都是二部图.
证明:无向树没有回路,因而不存在技术长度的圈,是二部图。 10、什么样的无向树T既是欧拉图,又是哈密顿图? 解:一阶无向树
14、设e为无向连通图G中的一条边, e在G的任何生成树中,问e应有什么性质?
解:e是桥
15、设e为无向连通图G中的一条边, e不在G的任何生成树中, 问e应有什么性质?
解:e是环
23、已知n阶m条的无向图 G是k(k≥2)棵树组成的森林,证明:m = n-k.;
证明:数学归纳法。k=1时, m = n-1,结论成立;
设k=t-1(t-1?1)时,结论成立,当k=t时, 无向图 G是t棵树组成的森林,任取两棵树,每棵树任取一个顶点,这两个顶点连线。则所得新图有t-1棵树,所以m = n-(k-1).
所以原图中m = n-k 得证。
24、在图所示2图中,实边所示的生成子图T是该图的生成树.
(1)指出T的弦,及每条弦对应的基本回路和对应T的基本回路系统.
(2) 指出T的所有树枝, 及每条树枝对应的基本割集和对应T的基本割集系统.
图 解:(a)T的弦:c,d,g,h
(a) (b)
T的基本回路系统: S={{a,c,b},{a,b,f,d},{e,a,b,h},{e,a,b,f,g}} T的所有树枝: e,a,b,f
T的基本割集系统: S={{e,g,h},{a,c,d,g,h},{b,c,d,g,h},{f,d,g}} (b)有关问题仿照给出