离散数学 (II) 习题 1-Toy模板网

这篇具有很好参考价值的文章主要介绍了离散数学 (II) 习题 1。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

1、如果一个无向图的每个顶点的度数均为 k，则称其为 k− 正则图。考虑 n 阶 3− 正则简单图，并且边数 m 与顶点数 n 满足：2n − 3 = m；请问，这样的无向图有几种非同构的情况。画出每种情况对应的图。

解答：
由握手定理可得：
3n=2m①
已知：
2n-3=m②
①②联立解得：m=9；n=6
度数集为（3,3，3,3，3,3）
一共有3情况
（1）

（2）

（3）

2、下面哪些数列是可图化的，哪些是可简单图化的？请给出你的理由。

对于可简单图化的，请给出对应的简单图。
(1) (4, 3, 2, 1)
(2) (5, 4, 3, 2, 1)
(3) (6, 6, 5, 5, 3, 3, 2)
(4) (5, 5, 3, 3, 2, 2, 1, 1)
(5) (3, 3, 2, 2, 2, 2)

解答：
（1）
d1+d2+d3+d4=4+3+2+1=10为偶数
所以可图化。
因为△(G) =4; n-1=3
所以△(G)>n-1
所以不可简单图化。
（2）
d1+d2+d3+d4+d5=15为奇数
所以不可图化。
（3）
d1+d2+d3+d4+d5+d6+d7=6+6+5+5+3+3+2=30为偶数
所以可图化。
(6,6,5,5,3,3,2)去掉一个度数为6的顶点
得(5,4,4,2,2,1)
去掉一个度数为5的顶点
得(3,3,1,1,0)
去掉一个度数为3的顶点
得(2,0,0,0)
显而易见一定有平行边或者环
所以不可简单图化。
（4）
d1+d2+d3+d4+d5+d6+d7+d8=5+5+3+3+2+2+1+1=22为偶数
所以可图化。
(5,5,3,3,2,2,1,1)去掉一个度数为5的顶点
得(4,2,2,1,1,1,1)
去掉一个度数为4的顶点
得(1,1,1,1,0,0)
所以可简单图化。

（5）
d1+d2+d3+d4+d5+d6=3+3+2+2+2+2=14为偶数
所以可图化。
(3,3,2,2,2,2)去掉一个度数为3的顶点
得(2,2,2,1,1)
去掉一个度数为2的顶点
得(1,1,1,1)
所以可简单图化。文章来源地址https://www.toymoban.com/news/detail-474403.html

到了这里，关于离散数学 (II) 习题 1的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！