当前课程知识点：离散数学 >  第6章 特殊图 >  6.2 哈密顿图 >  定理2证明

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

定理2证明资料文件与下载

定理2证明

定理2  如果G是有 n个结点的简单无向图，对于每一对不邻接结点u和v，满足d(u)+d(v) ³ n-1，那么G中存在哈密顿通路，图G是半哈密顿图。

证明  首先用反证法证明图G是连通的。

假设图G不连通，它至少有两个连通分支G1=（V1，E1）和G2 =（V2，E2）。取任意结点v1Î V1，v2Î V2，因为G是简单无向图，所以d（v1）£|V1|-1，d（v2）£|V2|-1，因而d（v1）+ d（v2）£ |V1|+|V2|-2 = n-2，与已知条件矛盾，所以图G是连通的。

然后证明G中存在哈密顿通路。

设L：v1 v2¼ vk 是G的最长的基本通路，显然k £ n。因为L是G的最长的基本通路，所以v1 和 vk的邻接点都在L上。

（1）     若k=n，则L为G中经过所有结点的通路，即为哈密顿通路。

（2）     若k<n，说明G中存在不在L上的结点。此时可以证明存在仅经过P上的所有结点的基本回路，证明如下：

第一种情况：若在L上v1和vk相邻，则v1 v2¼ vk v1是经过L上所有结点的基本回路。

   第二种情况：若在L上v1和vk不相邻，设v1与L上的结点 vj1=v2, vj2, ¼ vjm相邻（m³2，否则d(v1)+d(vk)£1+k-2<n-1），这时vk必与vj2 ¼ vjm 的邻接结点vj2-1 ¼ vjm-1之一相邻（否则d(v1)+d(vk)£j+k-2-(j-1)<n-1）。设vk与vjr-1（2£r£m）相邻，在L中添加边（v1, vjr），（vk，vjr-1），如图1(a)所示。删除边（vjr，vjr-1）得基本回路C= v1 v2¼ vjr-1vk vk-1¼ vjrv1，经过L上的所有结点，如图1(b)所示。

 

image.png   

图1                                   

 （3）     证明存在比L更长的通路。

       因为k<n-1，G中必有不在L上的结点vk+1。由于G是连通的，vk+1与L上的一个结点vt邻接，在L上删除边（vt-1，vt），添加边（vt，vk+1），于是可得到一条长度为k+1的基本通路vt-1¼ v1 vjr¼ vk vjr-1¼ vt vk+1，如图2所示。

       重复（1）~（3），由于G中的结点数目有限，一定能在有限步骤内得到一条哈密顿通路。

 

                                                  image.png

 

图2


下一节:最短路径问题

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

离散数学课程列表：

第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

期末考试

-期末考试

定理2证明笔记与讨论

也许你还感兴趣的课程:


  1. 植物生理学(2021秋)

  2. 儒家美育观与文学理论素养(2021秋)

  3. 日本近现代文学选读(2021暑假班)

  4. The Best Start in Life: Early Childhood Development for Sustainable Development(2021秋)

  5. 企业经营模拟(2021秋)

  6. 国际关系：理论与实践(2021秋)

  7. 社会工作概论(2021秋)

  8. 网络文学经典密码(2021秋)

  9. 金融与投资分析(2021秋)

  10. 口译：理论与实践(2021秋)

  11. 离散数学(自主模式)

  12. 无机与分析化学(自主模式)

  13. 知识产权法案例教学(2021春)

  14. 大学美育(自主模式)

  15. 数据结构（Data Structures）(自主模式)

  16. 创业管理四季歌：艺术思维与技术行动(2021春)

  17. 山野菜认知与开发利用(2021春)

  18. 小白学人工智能(自主模式)

  19. 马克思主义基本原理概论(自主模式)

  20. 智能车制作：电子技术(自主模式)
© 柠檬大学-慕课导航 课程版权归原始院校所有，
本网站仅通过互联网进行慕课课程索引，不提供在线课程学习和视频，请同学们点击报名到课程提供网站进行学习。