离散数学及其应用图论部分课后习题答案

上传人:mg****85 文档编号:34053442 上传时间:2018-02-20 格式:DOC 页数:11 大小:7.57MB
返回 下载 相关 举报
离散数学及其应用图论部分课后习题答案_第1页
第1页 / 共11页
离散数学及其应用图论部分课后习题答案_第2页
第2页 / 共11页
离散数学及其应用图论部分课后习题答案_第3页
第3页 / 共11页
离散数学及其应用图论部分课后习题答案_第4页
第4页 / 共11页
离散数学及其应用图论部分课后习题答案_第5页
第5页 / 共11页
点击查看更多>>
资源描述

《离散数学及其应用图论部分课后习题答案》由会员分享,可在线阅读,更多相关《离散数学及其应用图论部分课后习题答案(11页珍藏版)》请在金锄头文库上搜索。

1、作业答案:图论部分P165:习题九1、 给定下面 4 个图(前两个为无向图,后两个为有向图)的集合表示,画出它们的图形表示。(1) , ,1,GVE12345,v234()()()v(2) , ,,21123451,(,),(,),Evvv(3) 133,D3 245(4) 2441,VE125343,解答:(1)(2)10、是否存在具有下列顶点度数的 5 阶图?若有,则画出一个这样的图。(1)5,5,3,2,2;(2)3,3,3,3,2;(3)1,2,3,4,5;(4)4,4,4,4,4解答:(1) (3)不存在,因为有奇数个奇度顶点。14、设 G 是 阶无向简单图, 是它的补图,已知 ,求

2、(2)nG12(),()Gk, 。()解答: ; 。21k1()nk15、图 9.19 中各对图是否同构?若同构,则给出它们顶点之间的双射函数。解答:(c)不是同构,从点度既可以看出,一个点度序列为 4,3,3,3,3 而另外一个为4,4,3,3,1(d)同构,同构函数为 12()345xabfxcdxe16、画出所有 3 条边的 5 阶简单无向图和 3 条边的 3 阶简单无向图。解答:(1)三条边一共提供 6 度;所以点度序列可能是3,3,0,0,0,0;3,2,1,0,0,0;3,1,1,1,0,0;2,2,2,0,0,0;2,2,1,1,0,0;2,1,1,1,1,0;1,1,1,1,1

3、,1;由于是简单图,两种情形不可能图形如下:(2)三条边一共提供 6 度,所以点度序列可能为3,3,0;3,2,1;2,2,2由于是简单图,两种情形不可能21、在图 9.20 中,下述顶点序列是否构成通路?哪些是简单通路?哪些是初级通路?哪些是回路?哪些是简单回路?哪些是初级回路?(1) ;(2) ;(3) ;(4),abcde,abed,adceb,;dace(5) ;(6) ;(7) ;(8),abcde,adbec,cdab,abce解答:(1)构成通路,且为初级通路,因为点不重复(2)构成了回路,但是不为简单回路和初级回路,因为有重复的边 (,)(3)构成了初级通路,因为点不重复;(4

4、)不构成通路,因为边 不存在;(,)ac(5)构成通路,但是不为简单通路和初级通路,因为有重复的边 (,)dc(6)构成了回路,但是不为简单回路和初级回路,因为有重复的边 b(7)构成了初级通路;(8)简单通路,但是不为初级通路,有重复边。23、用 Dijkstra 标号法求图 9.22 中各图从顶点 到其余各点的最短路径和距离。1v解答步骤 1v23v45v67v81 *(,0)1(,6)*1(,)1(,)1(,)1(,)1(,)1(,)2 v*3,v38v3v3 *1(,)4(,6)1(,)(,)4(,)4 *,v231v5 (,)*5(,7)4(,)6 2v*7,0v7 *(,1)到 最

5、短路为 ,路长为 6;1v212v到 最短路为 ,路长为 3;33到 最短路为 ,路长为 5;1414到 最短路为 ,路长为 6;1v51345vv到 最短路为 ,路长为 12;626到 最短路为 ,路长为 7;1713457到 最短路为 ,路长为 10;v8 8vv(2)略。25、图 9.23 中各图有几个连通分支?给出它们所有的连通分支。解答:(a)有两个连通分支: 和 ;aecbdf(b)有三个连通分支: 、 和 ;(c)连通图,只有一个连通分支;(d)两个连通分支: 和 。fgech38、写出图 9.27 的关联矩阵。解答:10011000 40、写出图 9.29 中各图的邻接矩阵。解

6、答:(a) ; (b)1200110041、设有向图 ,其中 ,其邻接矩阵为,DVE1234,v01A试求出 中各顶点的入度和出度。D解答:出度: 1234:;:;vv入度: 0243、有向图 D 如图 9.29(a)所示(1)D 中 道 长度为 1, 2,3,4 的通路各有几条?1v4(2)D 中 道 长度为 1, 2,3,4 的通路各有几条?(3)D 中长度为 4 的通路有多少条?其中长为 4 的回路有多少条?(4)D 中长度小于或者等于 4 的通路有多少条?其中多少条为回路?(5)写出 D 的可达矩阵。解答: ,则 , ,120M210M3210M,456213(1)D 中 道 长度为

7、1, 2,3,4 的通路各有 0,0,2,2 条;1v4(2)D 中 道 长度为 1, 2,3,4 的通路各有 1,1,3,5 条;(3)D 中长度为 4 的通路有 44 条;其中长为 4 的回路有 11 条.(4)D 中长度小于或者等于 4 的通路有 88 条;其中 22 条为回路。(5)写出 D 的可达矩阵为 。1P181:习题十1、 图 10.14 中的哪些图是树?解答:(a)是树;(b)不是树,因为不连通。3、无向树 T 有 8 片树叶,2 个 3 度分支点,其余分支点都是 4 度顶点,问 T 有几个 4 度分支点?请画出 3 棵非同构的这种无向树。解答:设有 个 4 度分支点,则 T

8、 共有 个顶点。那么有 条边。由x8210x9x握手定理有 (9)42x所以有 2 个 4 度分支点。4、无向树 T 有 个 i 度分支点,其余顶点都为树叶,问 T 有几片树叶?(2,3.)ink解答:设有 片树叶,共有 个顶点,那么有 条边,x2ixn21kixn而共有 度,由握手定理可知2kiin22()kki ii所以有 。2()kiix15、已知 n 阶 m 条边的无向图 G 是 棵树组成的森林。证明: 。(2)kmnk证明:方法一:对变量 进行归纳k当 是,因为是一棵树,显然成立;1k假设 n 阶 m 条边的无向图 G 是 棵树组成的森林,有 ;1k(1)nk那么对于 n 阶 m 条

9、边的无向图 G 是 棵树组成的森林,在任意两棵树中分别找一点进行连一条边,那么得到的图则为 n 阶 m+1 条边的无向图 G 是 棵树组成的森林,那么 ,所以 。1()kk方法二:设 棵树中,分别有 个顶点和 条边, ,则有iim1,2.ik, , ,即可得证。1kii1kin1iin19、求图 10.17 中两个带权图的最小生成树。解答:P204:习题十一1、判断图 11.22 中哪些是欧拉图?哪些是半欧拉图?对欧拉图给出一条欧拉回路。对半欧拉图给出一条欧拉通路。对不是的,说明不是欧拉图或半欧拉图的理由。解答:(a)为欧拉图,全为偶度顶点;(b)为半欧拉图,1,2 两个顶点点度为 3,其它为

10、偶数。2、判断图 11.23 中哪些是欧拉图?哪些是半欧拉图?对欧拉图给出一条欧拉回路。对半欧拉图给出一条欧拉通路。对不是的,说明不是欧拉图或半欧拉图的理由。解答:(a)为半欧拉图,a,c 两点的出度和入度都相等; b 点的入度比出度大 1;c 点的入度比出度小 1.(b)为欧拉图,每个顶点的入度和出度都相等。3、判断命题的真假。(1)完全图 是欧拉图。nK(2) 阶有向完全图是欧拉图。()(3)当 r,s 为正偶数时,完全二部分图 是欧拉图。,rsK解答:(1)为假,因为当 n 为偶数时,每个点的点度都为奇数。(2)真;有向完全图的出度和入度必然相等。(3)真,完全二部分图 中,一部分点的点

11、度全为 r,另外一部分点的点度全为 s。,rs10.说明图 11.25 中各图不是哈密顿图,也不半哈密顿图的理由。解答:(a)删掉画圈的 3 个顶点,还剩下 5 个连通分支;(b)删掉画圈的 4 个顶点,还剩下 6 个连通分支。由定理 11.2 和 11.3 可知不是哈密顿图,也不半哈密顿图。11、设 G 是无向连通图,证明:若 G 中有桥或者割点,则 G 不是哈密顿图。证明: 若 G 中有者割点 ,取 ,则 ,由书中定理 11.2 可知,G 不vV()2|pV是哈密顿图。 若 G 中有者割边 ,12(,)e如果 和 的点度都为 1,则该图只有一条边,显然不为哈密顿图;1v2 如果 和 的点度至少有一个大于 1,不妨设 的点度大于 1,取 ,则1v1Vv,由书中定理 11.2 可知,G 不是哈密顿图。()|pV

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 生活休闲 > 科普知识

电脑版 |金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号