图论习题与答案.doc资源-CSDN文库

需积分: 5 165 浏览量 2023-12-11 14:21:24 上传评论收藏 458KB DOC 举报

资源推荐

资源详情

资源评论

图论习题与答案

1.(1)图 G 的度数列为 2、2、3、3、4，则 G 的边数是多少？

(2)3、3、2、3 和 5、2、3、1、4 能成为图的度数列吗？为什么？

(3)图 G 有 12 条边，度数为 3 的结点有 6 个，其余结点的度数均小于 3，问图 G 中至多

有几个结点？为什么？

解 (1)设 G 有 m 条边，由握手定理得 2m＝

�

�Vv

vd )(

＝2＋2＋3＋3＋4＝14，所以 G 的

边数 7 条。

(2)由于这两个序列中有奇数个是奇数，由握手定理的推论知，它们都不能成为图的度

数列。

(3) 由握手定理得

�

�Vv

vd )(

＝2m＝24，度数为 3 的结点有 6 个占去 18 度，还有 6 度由其

它结点占有，其余结点的度数可为 0、1、2，当均为 2 时所用结点数最少，所以应由 3 个结

点占有这 6 度，即图 G 中至多有 9 个结点。

2、.画出 4 阶无向完全图 K

4

的所有非同构的生成子图，并指出自补图来。

解下图中的 11 个图是 K

4

的全部的非同构的生成子图，其中(7)为自补图。

3、给定无向图 G＝<V，E>如图 10-49 所示，试求：

(1)从 a 到 d 的所有基本路。

(2)从 a 到 d 的所有简单路。

(3)长度分别是最小和最大的基本回路。

(4)长度分别是最小和最大的简单回路。

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余4页未读，立即下载

内容反馈

想要打Acm的小周同学呀

粉丝: 1070
资源: 105

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip