1. 图的定义（重点）

图 GG 由顶点集 VV 和边集 EE 组成，记作

G=(V,E).G=(V,E).
  • V(G)V(G)：图 GG 的有限非空顶点集；
  • E(G)E(G)：图 GG 中顶点之间关系（边）的集合；
  • 顶点数通常记为 nn；
  • 边数通常记为 mm。

重点：顶点集 VV 必须非空，但边集 EE 可以为空。 当 E=∅E=\varnothing 时，图中只有孤立顶点。

2. 有向图与无向图（重点）

有向图

边具有方向的图称为有向图。有向边也称为弧，用有序对

⟨v,w⟩\langle v,w\rangle

表示，其中 vv 是弧尾，ww 是弧头；⟨v,w⟩\langle v,w\rangle 与 ⟨w,v⟩\langle w,v\rangle 是两条不同的弧。

无向图

边没有方向的图称为无向图。无向边用无序对 (v,w)(v,w) 表示，因此

(v,w)=(w,v).(v,w)=(w,v).

重点：有向边有先后次序，无向边没有先后次序。

3. 简单图与多重图

同时满足以下条件的图称为简单图：

  1. 不存在重复边；
  2. 不存在顶点到自身的边，即不存在自环。

含有重复边或自环的图称为多重图。本书主要讨论简单图。

4. 顶点的度、入度和出度（重点）

无向图

与顶点 vv 相关联的边数称为顶点 vv 的度，记作 TD⁡(v)\operatorname{TD}(v)。自环在度数中计算两次。

无向图中所有顶点的度数之和，等于边数的 22 倍，即 2m2m。

有向图

  • 入度 ID⁡(v)\operatorname{ID}(v)：以顶点 vv 为终点的有向边数；
  • 出度 OD⁡(v)\operatorname{OD}(v)：以顶点 vv 为起点的有向边数；
  • 总度数：
TD⁡(v)=ID⁡(v)+OD⁡(v).\boxed{\operatorname{TD}(v)=\operatorname{ID}(v)+\operatorname{OD}(v)}.

有向图中，所有顶点的入度总和 = 出度总和 = 边数 mm。

重点：每条无向边为总度数贡献 22；每条有向边分别贡献 11 个入度和 11 个出度。

5. 路径、路径长度与回路

顶点 uu 到 vv 的一条路径，是由一系列顶点组成的序列，其中任意两个相邻顶点之间都有边。

  • 路径长度：路径所包含的边数；
  • 回路：第一个顶点与最后一个顶点相同的路径；
  • 对于含 nn 个顶点的无向图，若边数大于 n−1n-1，则图中一定有环。

6. 简单路径与简单回路

  • 简单路径：路径中的顶点不重复出现；
  • 简单回路：除第一个顶点与最后一个顶点相同外，其余顶点均不重复。

7. 距离

从顶点 uu 到顶点 vv 的最短路径长度称为二者之间的距离。若不存在路径，则距离为无穷大。

8. 子图

设 G=(V,E)G=(V,E)、G′=(V′,E′)G'=(V',E')。若 V′⊆VV'\subseteq V、E′⊆EE'\subseteq E，并且 E′E' 中每条边的两个端点都属于 V′V'，则称 G′G' 为 GG 的子图。

直观地说，从原图中删除部分顶点、部分边，或者同时删除二者，剩余的图就是原图的子图。

若子图包含原图的全部顶点，即 V′=VV'=V，则称 G′G' 为 GG 的生成子图。生成子图只允许删除边，不能删除顶点；它不要求连通，原图 GG 本身也是 GG 的生成子图。

若 G′G' 是 GG 的子图，并且 G′≠GG'\ne G，则称 G′G' 为 GG 的真子图，即至少删除了顶点或边。类似地，真生成子图需要保留原图的全部顶点，但不能与原图完全相同。

易错点： 不能任取 VV 和 EE 的子集就构成子图；所选边关联的顶点必须全部包含在 V′V' 中。

9. 连通、连通图与连通分量（重点）

在无向图中：

  • 若顶点 uu 到顶点 vv 存在路径，则称 uu 与 vv 连通；
  • 若图中任意两个顶点都连通，则称该图为连通图；
  • 非连通图的极大连通子图称为连通分量。

对于含 nn 个顶点的简单无向图，连通图至少有 n−1n-1 条边。因此，边数少于 n−1n-1 时，该图一定不连通。

非连通简单图最多有

(n−1)(n−2)2\frac{(n-1)(n-2)}2

条边，此时可由一个含 n−1n-1 个顶点的完全图和一个孤立顶点组成。

10. 强连通图与强连通分量（重点）

在有向图中，若从 vv 到 ww 以及从 ww 到 vv 都存在有向路径，则称 vv 与 ww 强连通。

  • 任意两个顶点都强连通的有向图称为强连通图；
  • 有向图的极大强连通子图称为强连通分量。

对于含 nn 个顶点的强连通有向图，至少需要 nn 条有向边，可以用一个经过所有顶点的有向回路实现。

重点：无向图讨论“连通”，有向图讨论“强连通”。

11. 生成树与生成森林（重点）

连通图的生成树，是包含图中全部顶点的极小连通子图。

也就是说，生成树是包含原图全部顶点，并且连通、无环的生成子图。

若图有 nn 个顶点，则任意生成树都恰有 n−1n-1 条边。

生成树具有以下性质：

  • 删除任意一条边，图都会变得不连通；
  • 添加任意一条原图中的非树边，图中都会形成回路。

在非连通图中，各连通分量的生成树共同构成该图的生成森林。

易错点： 极大连通子图强调“再加入顶点或边便不再是该连通分量”；极小连通子图强调“保持全部顶点连通的同时，边数不能再少”。

12. 边的权、网与带权路径长度

边上表示某种含义的数值称为该边的权值。带权值的图称为带权图，也称为网。

一条路径的带权路径长度，等于该路径上所有边的权值之和。

13. 完全图（重点）

无向完全图

任意两个不同顶点之间都有一条边的无向图称为完全图，记作 KnK_n。它的边数为

m=n(n−1)2.\boxed{m=\frac{n(n-1)}2}.

有向完全图

任意两个不同顶点之间都存在方向相反的两条有向边。其边数达到最大值

m=n(n−1).\boxed{m=n(n-1)}.

14. 稀疏图与稠密图（重点）

边数相对较少的图称为稀疏图，反之称为稠密图。二者是相对概念，没有绝对分界。

若用 nn 表示顶点数、mm 表示边数，本书采用的参考范围是

m<nlog⁡2n.m<n\log_2n.

时，可以将图视为稀疏图。

重点：稀疏与稠密描述的是边数相对于顶点数的多少，判断标准通常只是参考范围。

15. 有向树

一个顶点的入度为 00，其余顶点的入度均为 11 的有向图，称为有向树。

重点公式速记

概念 结论
无向图顶点度数之和 边数的 22 倍，即 2m2m
有向图入度、出度之和 入度总和 = 出度总和 = 边数 mm
连通无向图的最少边数 n−1n-1 条
强连通有向图的最少边数 nn 条
生成树的边数 n−1n-1 条
无向完全图的边数 n(n−1)2\dfrac{n(n-1)}2 条
有向完全图的边数 n(n−1)n(n-1) 条

怎么这么多内容要记，
又开始头疼了。
又快累死了，下午5点一直忙到晚上11点。
现在差单词还没有背，赶紧搞定吃饭去。
最近感觉My Iron Lung有点好听啊，
明天如果有空可以搜谱子练练，太帅了。

又是我最喜欢的贵贵😊 背着贝斯的中岛由贵