离散课后习题答案5.doc
《离散课后习题答案5.doc》由会员分享,可在线阅读,更多相关《离散课后习题答案5.doc(12页珍藏版)》请在三一文库上搜索。
1、.第十四章部分课后习题参考答案5、设无向图 G 有 10 条边,3 度与 4 度顶点各 2 个,其余顶点的度数均小于 3,问 G 至G、精品.少有多少个顶点?在最少顶点的情况下,写出度数列、解:由握手定理图 G 的度数之和为: 2 10 = 20( ) (G) 。精品.3 度与 4 度顶点各 2 个,这 4 个顶点的度数之和为 14 度。其余顶点的度数共有 6 度。其余顶点的度数均小于 3,欲使 G 的顶点最少,其余顶点的度数应都取 2,精品.所以,G 至少有 7 个顶点, 出度数列为 3,3,4,4,2,2,2, () = 4 ,( ) = 2 .精品.G G7、设有向图 D 的度数列为 2
2、,3,2,3,出度列为 1,2,1,1,求 D 的入度列,并求(D), (D) ,精品.+ (D),+ ( ) , D( D),(D) .精品.解:D 的度数列为 2,3,2,3,出度列为 1,2,1,1,D 的入度列为 1,1,1,2.精品.( ) = 3, ( ) = 2 , +D D(D) = 2, + ( ) = 1, D( D) = 2,( D) = 1精品.8、设无向图中有 6 条边,3 度与 5 度顶点各 1 个,其余顶点都是 2 度点,问该图有多少个顶点?解:由握手定理图 G 的度数之和为: 2 6 = 12设 2 度点 x 个,则 3 1 + 5 1 + 2x = 12 ,
3、x = 2 ,该图有 4 个顶点.14、下面给出的两个正整数数列中哪个是可图化的?对可图化的数列,试给出 3 种非同构的无向图,其中至少有两个时简单图。(1) 2,2,3,3,4,4,5(2)2,2,2,2,3,3,4,4 解:(1) 2+2+3+3+4+4+5=23是奇数,不可图化;(2)22+2+2+3+3+4+4=16, 是偶数,可图化;18、设有 3 个 4 阶 4 条边的无向简单图 G1、G2、G3,证明它们至少有两个是同构的。精品.证明:4 阶 4 条边的无向简单图的顶点的最大度数为 3,度数之和为 8,因而度数列1精品.为 2,2,2,2;3,2,2,1;3,3,1,1。但 3,
4、3,1,1 对应的图不是简单图。所以从同构的观点看,4 阶 4 条边的无向简单图只有两个:所以,G1、G2、G3 至少有两个是同构的。20、已知 n 阶无向简单图 G 有 m 条边,试求 G 的补图 G 的边数 m 。 解: = n(n 1)m2m21、无向图 G 如下图(1)求 G 的全部点割集与边割集,指出其中的割点和桥;(2) 求 G 的点连通度 k (G) 与边连通度 (G) 。ae1e2debe5精品.解:点割集: a,b,(d)e3e4c精品.边割集e2,e3,e3,e4,e1,e2,e1,e4e1,e3,e2,e4,e5精品.k( ) = (GG) =1精品.k23、求 G 的点
5、连通度 (G) 、边连通度 ( G) 与最小度数 ( ) 。 G精品.精品.k解: (G) = 2 、 (G) = 3、 ( ) = 4G精品.28、设 n 阶无向简单图为 3-正则图,且边数 m 与 n 满足 2n-3=m 问这样的无向图有几种非同构的情况?精品.3解: n = 2m得 n=6,m=9.精品.2n 3 = m精品.2精品.31、设图 G 和它的部图 G 的边数分别为 m 和 m ,试确定 G 的阶数。精品. 解: m + m= n(n + 1)2 1 +得 n =1 + 8(m + m)2精品.45、有向图 D 如图(1)求 v2 到 v5 长度为 1,2,3,4 的通路数;
6、(2)求 v5 到 v5 长度为 1,2,3,4 的回路数;(3)求 D 中长度为 4 的通路数;(4)求 D 中长度小于或等于 4 的回路数;(5)写出 D 的可达矩阵。v1v4v5v2v3解:有向图 D 的邻接矩阵为:精品. 0000 10100 00002 02020 0 01011 1 , A 01A = 000021013020 10100 00002 02020 = 0 20010 0 A020 20200 = 20 4 0000精品. 00004 40400 4 = 00004 A 40400 0 04042A + A +3A + A 01 524 = 21 42 25215 5
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散 课后 习题 答案
链接地址:https://www.31doc.com/p-6294888.html