[图论]哈尔滨工业大学（哈工大 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：不能成功染色但是是哈密顿图，可以在哈密顿圈上补点

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

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

（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）示例

4. 带权图

略。老师只抛出了问题，没有说求解办法。