当前课程知识点:离散数学 >  第6章 特殊图 >  作业9 >  作业9解答

返回《离散数学》慕课在线视频课程列表

作业9解答资料文件与下载

作业9解答

11、在哥尼斯堡七桥问题中,至少再架几座桥,游人可以从陆地的某一点出发经过每座桥一次且仅一次,最后回到出发地点?

解答:

.:只需多加两座桥即可.如图所示:

d(A)=3,d(B)=5,d(C)=3,d(D)=3,d(A)=3,d(B)=5,d(C)=3,d(D)=3,4奇度数节点的个数为4,(ADG)若只添加一条边(如AD之间添加一条边,形成新图G'),2此时奇度数节点的个数为2,根据欧拉定理,GG'中存在一条欧拉通路,(BC)但是出发点和结束点是两个不同的奇度节点(B和C),(BC).因此需要再额外多加一条边(BC).

截屏2020-02-13下午6.27.59.png

2Gn(n3)vi,vjd(vi)+d(vj)n.2、设G是n(n\geq3)阶无向简单哈密顿图,则对于任意不相邻的结点v_i,v_j,均有d(v_i)+d(v_j)\geq n.这个结论成立吗?为什么?

.解答:结论不成立. 我们举例说明:

5d(A)+d(C)=4<5.下图是一个5阶无向简单哈密顿图,但是d(A)+d(C)=4<5.Gn(n3)d(vi)+d(vj)nG.事实上,反过来是成立的,即“G是n(n\geq3)阶无向简单图,若对任意两个不相邻的节点都满足d(v_i)+d(v_j)\geq n,则G为哈密顿图.”


下一节:中国邮路问题

返回《离散数学》慕课在线视频列表

离散数学课程列表:

第1章 命题逻辑

-1.1 命题与联结词

--命题

--联结词

--1.1 练习

-1.2 命题公式及其分类

--命题公式及其分类

--1.2 练习

-1.3 命题演算的关系式

--等值演算

--其它联结词

--1.3 练习

-作业1

--作业1

--讨论1

--作业1解答

-1.4 范式

--主析取范式

--主合取范式

--1.4 练习

-1.5 命题演算的推理

--推理定理

--推理证明方法

--1.5 练习

-作业2

--作业2

--作业2解答

第2章 谓词逻辑

-2.1 谓词逻辑的基本概念

--谓词逻辑的基本概念

--2.1练习

-2.2 谓词演算公式

--谓词演算公式

--2.2练习

-2.3 谓词公式的解释和分类

--谓词公式的解释和分类

--2.3练习

-作业3

--作业3

--作业3解答

-2.4 谓词演算的关系式

--谓词演算的关系式

--2.4练习

-2.5 前束范式

--前束范式

--2.5练习

-2.6 谓词演算的推理

--谓词逻辑的推理规则

--谓词逻辑推理证明举例

--2.6练习

-作业4

--作业4

--讨论2

--作业4解答

单元测验1

-测验1

--单元测验1

第3章 集合

-3.1 集合的基本概念和表示法

--集合的概念和表示方法

--3.1练习

-3.2 集合的关系

--集合的关系

--3.2练习

-3.3 集合的运算

--集合的运算

--3.3练习

-3.4 后继数和自然数

--后继数与自然数

-作业5

--作业5

--作业5解答

第4章 关系和函数

-4.1 关系的概念与笛卡尔积

--关系的概念与笛卡儿积

--4.1练习

-4.2 关系的表示法

--关系的表示法

--4.2练习

-4.3 关系的运算

--关系的运算

--4.3练习

-4.4 关系的性质

--关系的性质

--4.4练习

-作业6

--作业6

--作业6解答

-4.5 关系闭包

--关系闭包

--4.5练习

--讨论3

-4.6 等价关系

--等价关系

--4.6练习

-4.7 偏序关系

--偏序关系

--4.7练习

-4.8 函数

--函数的定义

--函数的复合和反函数

--集合的基数

--4.8练习

-作业7

--作业7

--作业7解答

单元测验2

-测验2

--单元测验2

第三部分 图论

-图论的起源和发展

--图论的起源和发展

第5章 图论

-5.1 图的基本概念

--图的基本概念

--图的分类

--子图和补图

--图的同构

--5.1练习

-5.2 通路、回路、连通的概念

--通路和回路

--连通的概念

--5.2练习

-5.3 图的表示

--图的表示

--5.3练习

-作业8

--作业8

--作业8解答

第6章 特殊图

-6.1 欧拉图

--欧拉图

--6.1练习

-6.2 哈密顿图

--哈密顿图

--6.2练习

--定理2证明

-6.3 最短路径问题

--最短路径问题

--6.3练习

-作业9

--作业9

--作业9解答

-6.4 中国邮路问题

--中国邮路问题

--6.4练习

-6.5 匹配和二分图

--匹配和二分图

--定理2的证明

--6.5练习

-6.6 平面图

--平面图的定义和欧拉公式

--对偶图和图的着色

--6.6练习

--讨论4

--学习资源

-作业10

--作业10

--作业10解答

第7章 树

-7.1 树的定义和生成树

--树的定义和生成树

--7.1练习

-7.2 根树

--根树

--7.2练习

-7.3 根树的应用

--根树的应用

--7.3练习

-作业11

--作业11

--讨论5

--作业11解答

单元测验3

-测验3

--单元测验3

期末考试

-期末考试

作业9解答笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。