[图论]哈尔滨工业大学（哈工大 HIT）学习笔记23-31-Toy模板网

这篇具有很好参考价值的文章主要介绍了[图论]哈尔滨工业大学（哈工大 HIT）学习笔记23-31。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

视频来源：4.1.1 背景_哔哩哔哩_bilibili

1. 哈密顿图

1.1. 背景

1.2. 哈氏图

2. 邻接矩阵/邻接表

3. 关联矩阵

3.1. 定义

4. 带权图

1. 哈密顿图

1.1. 背景

（1）以地球为建模，从一个大城市开始遍历其他大城市并且返回，每个顶点只能被通过一次

1.2. 哈氏图

（1）定义：如果G中有生成圈，则称G为哈氏图

（2）和欧拉图的区别：欧拉图是一个顶点可以通过多次，只要把边画完就好。但哈密顿图一个顶点只能经过一次

（3）染色：

①同一条边的两个顶点染上不同的颜色

②每个顶点都需染色

③一共只能染两种颜色

④特例1：不能成功染色但是是哈密顿图，可以在哈密顿圈上补点

[图论]哈尔滨工业大学（哈工大 HIT）学习笔记23-31,图论,学习,笔记,图论,深度学习,人工智能

⑤特例2：不是哈密顿图但是可以成功染色（因此一定要判断是不是圈）：

[图论]哈尔滨工业大学（哈工大 HIT）学习笔记23-31,图论,学习,笔记,图论,深度学习,人工智能

⑥⭐若能染，但是染完两个颜色个数不一样多，一定不是哈密顿图

（4）必要条件：，，设为求支，若是哈密顿则有：

（5）充分条件：

①定理1：顶点大于3时，任何一个顶点的度都大于p/2

证明：若一个图G不是哈密顿图，则存在有u,v不邻接的。则一直加边，加到是哈密顿图为止。这时去掉一条边，G变成哈密顿路，形似1.2.(3)⑤。

②定理2：若不相邻两顶点度数之和大于等于p，则G是哈密顿图

③定理3：若不相邻两顶点度数之和大于等于p-1，则G中有哈密顿路

2. 邻接矩阵/邻接表

（略）数据结构学过了

3. 关联矩阵

3.1. 定义

（1）纵轴为顶点，横轴为边，关联则标1。

（2）重视顶点和边之间的关系

（3）示例

[图论]哈尔滨工业大学（哈工大 HIT）学习笔记23-31,图论,学习,笔记,图论,深度学习,人工智能

4. 带权图

略。老师只抛出了问题，没有说求解办法。文章来源地址https://www.toymoban.com/news/detail-837083.html

到了这里，关于[图论]哈尔滨工业大学（哈工大 HIT）学习笔记23-31的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

[图论]哈尔滨工业大学（哈工大 HIT）学习笔记23-31

1. 哈密顿图

1.1. 背景

1.2. 哈氏图

2. 邻接矩阵/邻接表

3. 关联矩阵

3.1. 定义

4. 带权图

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

支付宝扫一扫领取红包，优惠每天领

二维码1

二维码2