📦图论与算法—期末笔记

1 概念题

1. 图的点数 n，边数 m

2. 度：一个顶点所连接的边的数量。最大度 ，最小度 。

3. 离心率：ecc(v) 指的是 v 到所有顶点的距离的最大值

4. 中心点：离心率最小的顶点；半径：中心点的离心率

5. 边缘点：离心率最大的顶点；直径：边缘点的离心率

6. 点连通度：使图不连通或退化为单个顶点所需删除的最少顶点数，
• k-连通图指的是 k 点连通

7. 边连通度：使图不连通所需删除的最少边数，
• 结论：简单连通图

8. 二分图：没有奇圈

9. 边独立数：最大匹配的边数（即无公共顶点的边集合的最大大小）

10. 边覆盖数：覆盖所有顶点的最小边集合的大小

11. 边支配数：最小的边集合，使得图中每条边要么属于该集合，要么与它邻接

12. 点独立数：最大独立集的顶点数（即没有边连接的顶点集合的最大大小）

13. 点覆盖数：覆盖所有边的最小顶点集合的大小

14. 点支配数：最小的顶点集合，使得图中每个顶点要么属于该集合，要么与它邻接

15. 边色数：给图的边着色所需的最小颜色数，使得相邻边颜色不同

16. 点色数：给图的顶点着色所需的最小颜色数，使得相邻顶点颜色不同
• Vizing 定理：

17. 平面图：嵌入平面中，使得任何两条边不相交
• 判定的充要条件：平面图 $$ 不包含与 或 同胚的子图
• 平面图的欧拉公式： 其中顶点数为 n，边数为 m，面数为 f，连通分支数为 k
• 简单连通平面图：
• 无 的简单连通平面图：

18. 对偶图：可平面图的对偶图
• 顶点集：所有的面
• 每条边（可能有重边）：
• 如果原图中的某条边在两个面的边界中，那么在对偶图中这两个面对应的顶点有一条边
• 如果原图中的某条边在一个面的边界中，那么对应一个自环

2 3 书中原题

1. 证明边数不小于点数的图都有圈（逐步删去度为 1 的顶点）。

2. 证明最小度不小于 2 的图都有圈（从某个顶点出发的路可以一直延伸。由于顶点数量有限，所以一定会经过访问过的顶点，从而成环）。

3. 证明最小度不小于 k 的图都有至少 k+1 个点的圈（构造法）。

4. 证明 2-正则图点连通度等于边连通度（边连通度为 2. 点连通度构造得 <=2, 然后由于 2-正则图，因此任意两个顶点有两条不交路。>=2）。

5. 证明往点连通度为 p 的图加个点，这个点任意和其他 p 个点连边得到的新图点连通度和原图相同（trivial）。

4 必考算法

1. 匈牙利算法 (P60)：
• 思路：对左侧（X 集合）未匹配的点进行 DFS 找增广路，每次 do while 循环只找一条。

2. HK 算法
• 思路：每次 do while 循环从左侧（X 集合）未匹配的点开始，进行 BFS。当找到第一条增广路时，记录其长度 d，并将终点加入 Y’ 集合中。当 BFS 的距离大于 d 时终止。然后从 Y’ 中的顶点按照 d 递减的顺序找到互不相交的增广路，同时进行增广。

知识点

1. 迹：边不重复出现的路线

2. 路：点不重复出现的迹

3. 割点的充要条件：对于连通图 和顶点 ，v 是 G 的割点当且仅当存在 V 的两个不相交的非空子集 Vi 和 Vj，对于任意顶点 和 ，每条 u-w 路都经过 v.

Algorithms

Tarjan 算法求割点（P19）

• 根节点：有两个以上的子树，则是割点

• 其他节点：对边 ，v 为 u 在 DFS Tree 中的子节点，low[v] >= dfn[u]，u 是割点。（割开了以 v 为根的子树和 u 的 parent）

寻找欧拉迹

Fleury 算法

Hierholzer 算法

二级结论

1. 阶 ≥ 2 的简单图，至少有两个点的度相同。

2. 若 G 连通，则 G 补图可能连通可能不连通。若 G 不连通，则 G 补图一定连通。

3. 若顶点 v 是 G 的割点，v 不是 G 补图的割点。

4. 连通图的距离函数满足三角不等式。

5. 连通图的两个顶点 u v，

6. 连通图 G：

7. 二分图 G 连通当且仅当顶点集的划分唯一。

8. 圈图的补图一定有哈密尔顿回路（n ≥ 5）。证明：n = 5 使用特判，n ≥ 6 使用 Dirac 定理或 Ore 定理。
• Dirac 定理：若 G 的每个顶点度数至少为 ，则 G 是哈密尔顿图
• Ore 定理：若 G 中任意两个不相邻的顶点度数之和至少为 n，则 G 是哈密尔顿图。