目录#

1. 图是什么
2. 顶点与边的关系
3. 顶点的度数与握手定理
4. 图的同构
5. 几类特殊图
6. 子图与补图
7. 通路回路路径与圈
8. 无向图的连通性
9. 割点割边与连通度
10. 有向图的连通性
11. 图的矩阵表示
12. 图的基本运算
13. 综合例题
14. 复习重点

1. 图论研究的对象#

现实中有许多问题可以抽象成“点”和“线”。

图论通常不关心边的长度，也不关心图形画出来的形状。只要顶点之间的连接关系没有变化，就可以认为图的结构没有变化。

例如，下面两幅图虽然形状不同，但表示的连接关系相同。

1
a ----- b           a
2
|       |          / \
3
|       |         d   b
4
d ----- c          \ /
5
                    c

2. 无向图#

无向图记作 $G=\langle V,E\rangle$。

其中：

• $V$ 是顶点集；
• $E$ 是边集；
• 每条边没有方向。

例如：

• $V=\{a,b,c,d\}$
• $E=\{(a,b),(b,c),(c,a),(c,d)\}$

可以画成：

1
a ----- b
2
 \     /
3
  \   /
4
    c ----- d

由于边没有方向，所以 $(a,b)=(b,a)$。

例如，城市之间的双向道路可以用无向边表示。

3. 有向图#

有向图通常记作 $D=\langle V,E\rangle$。

每条边具有方向，用有序对表示。

例如，$\langle a,b\rangle$ 表示从顶点 $a$ 指向顶点 $b$。

此时，$\langle a,b\rangle \ne \langle b,a\rangle$。

1
a → b

例如，用户 $a$ 关注了用户 $b$，并不代表用户 $b$ 一定关注用户 $a$。

将有向图中每条有向边的箭头去掉，得到的无向图称为该有向图的基图。

4. 阶、零图、平凡图与空图#

需要区分：

• 零图可以有多个顶点，只是没有边；
• 平凡图是特殊的零图；
• 空图连顶点都没有。

1. 端点与关联#

在无向图中，设 $e=(u,v)$，则 $u,v$ 称为边 $e$ 的端点，边 $e$ 与顶点 $u,v$ 关联。

1
u ----- v
2
    e

边 $e$ 与 $u$ 和 $v$ 都关联。

2. 环#

当一条边的两个端点相同时，即 $e=(v,v)$，这条边称为环。

1
  ↗---↘
2
  | v |
3
  ↖---↙

环有一个重要的计数规则：

在无向图中，一个环使顶点的度数增加 $2$。

原因是：环虽然只有一条边，但它的两个端点都是同一个顶点。

3. 平行边与多重图#

如果两条或多条边连接同一对顶点，这些边称为平行边。

1
u ===== v

假设 $u,v$ 之间有两条边，则这两条边互为平行边，其重数为 $2$。

在有向图中，只有始点和终点都相同的边才是平行边。

例如，$\langle u,v\rangle$ 与 $\langle u,v\rangle$ 是平行边。

但是，$\langle u,v\rangle$ 与 $\langle v,u\rangle$ 的方向不同，不是平行边。

4. 简单图与多重图#

后续学习完全图、补图和树时，通常会重点讨论简单图。

5. 相邻#

1
a ----- b

1
a ----- b ----- c
2
   e₁       e₂

6. 邻域与关联集#

对于无向图中的顶点 $v$：

1
a ----- b ----- c
2
        |
3
        d

1. 无向图中顶点的度数#

顶点 $v$ 的度数记作 $d(v)$。

它表示顶点 $v$ 作为边的端点出现的总次数。

例如：

1
a ----- b ----- c
2
        |
3
        d

有：

• $d(a)=1$
• $d(b)=3$
• $d(c)=1$
• $d(d)=1$

1
  ↗---↘
2
  | a | ----- b
3
  ↖---↙

2. 特殊顶点#

图 $G$ 的最大度和最小度分别记作：

• $\Delta(G)=\max\{d(v)\mid v\in V\}$
• $\delta(G)=\min\{d(v)\mid v\in V\}$

3. 有向图中的入度与出度#

在有向图中，每条边有方向，因此需要区分：

• 出度：从顶点出发的边数；
• 入度：进入顶点的边数。

记作：

• $d^+(v)$：顶点 $v$ 的出度；
• $d^-(v)$：顶点 $v$ 的入度。

总度数为 $d(v)=d^+(v)+d^-(v)$。

例如：

1
a → b → c
2
↑   ↓
3
└── d

假设边为：

• $\langle a,b\rangle$
• $\langle b,c\rangle$
• $\langle b,d\rangle$
• $\langle d,a\rangle$

则：

• $d^+(b)=2$
• $d^-(b)=1$
• $d(b)=3$

4. 握手定理#

对于任意无向图，有：

$\sum_{v\in V}d(v)=2|E|$

也就是说：

所有顶点度数之和等于边数的 $2$ 倍。

原因很直观：每条边都有两个端点，因此每条边总共贡献 $2$ 次度数。

例如：

1
a ----- b
2
 \     /
3
  \   /
4
    c ----- d

边数为 $|E|=4$。

各顶点度数为：

• $d(a)=2$
• $d(b)=2$
• $d(c)=3$
• $d(d)=1$

因此，$2+2+3+1=8=2\times 4$。

5. 奇度顶点一定有偶数个#

由握手定理可以推出：

任何图中，奇度顶点的个数一定是偶数。

原因是：

• 所有顶点度数之和为偶数；
• 若奇数个奇数相加，结果一定是奇数；
• 因此奇度顶点只能有偶数个。

例如，一个图不可能恰好有 $1$ 个、$3$ 个或 $5$ 个奇度顶点。

6. 有向图版本的握手定理#

对于有向图：

• $\sum_{v\in V}d^+(v)=|E|$
• $\sum_{v\in V}d^-(v)=|E|$
• $\sum_{v\in V}d(v)=2|E|$

原因是每条有向边：

• 对始点贡献一次出度；
• 对终点贡献一次入度。

7. 度数列与可图化#

将图中各个顶点的度数排列起来，得到图的度数列。

例如，$(3,3,2,2,1,1)$ 是一个度数列。

课件中给出：

一个非负整数列可图化，当且仅当其元素之和为偶数。

这里需要特别注意：课件中的一般图允许环和平行边，因此“度数和为偶数”足以保证可图化。

但是，如果题目要求构造简单图，条件会更加严格。

例如，$(4,4,1,1)$ 的总和为 $10$，是偶数，但它无法成为一个 $4$ 阶简单图的度数列，因为 $4$ 阶简单图中每个顶点的度数最多是 $3$。

1. 直观理解#

如果两个图只是：

• 顶点名称不同；
• 画法不同；
• 顶点摆放位置不同；

但是连接关系完全一致，那么这两个图同构。

图同构记作 $G_1\cong G_2$。

例如：

1
a ----- b          1
2
|       |         / \
3
|       |        4   2
4
d ----- c         \ /
5
                   3

两幅图都是一个四边形环，因此同构。

2. 严格定义#

若存在一个双射 $f:V_1\to V_2$，并且保持顶点之间的邻接关系、边的方向和平行边的重数，则两个图同构。

可以理解为：

给第一个图中的每个顶点重新命名，能够得到第二个图。

3. 判断不同构的常用方法#

常用必要条件：

1. 顶点数相同；
2. 边数相同；
3. 度数列相同；
4. 对应顶点的邻域大小、关联边数量等相同。

如果其中任意一个条件不满足，则两个图一定不同构。

但是反过来不一定成立。

度数列相同，不代表一定同构。

因此，判断同构通常分两步：

1. 先用顶点数、边数和度数列排除；
2. 若无法排除，再尝试建立顶点之间的一一对应关系。

1. 完全图#

$n$ 阶无向完全图记作 $K_n$。

它满足：任意两个不同顶点之间都有一条边。

例如：

1
K₃：
2

3
    a
4
   / \
5
  b---c

每个顶点都与其他 $n-1$ 个顶点相邻，因此：

• $d(v)=n-1$
• $|E|=\dfrac{n(n-1)}{2}$

例如，$|E(K_5)|=\dfrac{5\times 4}{2}=10$。

2. 有向完全图#

在 $n$ 阶有向完全图中，每对不同顶点之间都有两条方向相反的边：

• $\langle u,v\rangle$
• $\langle v,u\rangle$

因此：

• $|E|=n(n-1)$
• $d^+(v)=n-1$
• $d^-(v)=n-1$

3. 竞赛图#

竞赛图也是有向简单图，但每对不同顶点之间只有一个方向。

例如：

1
a → b
2
↑   ↓
3
└── c

可以将其理解为：

• 每两名选手之间进行一次比赛；
• 箭头从胜者指向败者；
• 每场比赛只有一个结果。

4. 正则图#

如果无向简单图中每个顶点的度数都为 $k$，则称其为 $k$-正则图。

例如，四边形：

1
a ----- b
2
|       |
3
|       |
4
d ----- c

每个顶点度数都是 $2$，因此它是 $2$-正则图。

对于 $n$ 阶 $k$-正则图，有：

• $nk=2m$
• $m=\dfrac{nk}{2}$

1. 子图#

若 $V'\subseteq V$ 且 $E'\subseteq E$，则 $G'=\langle V',E'\rangle$ 是 $G$ 的子图。

直观上，子图就是从原图中删掉一些顶点或边之后得到的图。

2. 真子图#

如果 $G'\subseteq G$ 并且 $G'\ne G$，则 $G'$ 是 $G$ 的真子图。

3. 生成子图#

如果子图保留了原图中的全部顶点，只删去了一部分边，则称为生成子图。

也就是：

• $V'=V$
• $E'\subseteq E$

后续第 $16$ 章中的生成树，就是一种特殊的生成子图。

4. 导出子图#

1
a ----- b
2
| \     |
3
|  \    |
4
d ----- c

1
a ----- b
2
 \     |
3
  \    |
4
    c

5. 补图#

对于无向简单图 $G$，保持顶点集不变，将原图中不存在的边补上，得到补图 $\overline{G}$。

原图和补图合并后，恰好得到完全图：

$G\cup\overline{G}=K_n$

因此：

$|E(G)|+|E(\overline{G})|=\dfrac{n(n-1)}{2}$

1. 通路#

通路是顶点和边交替出现的序列：

$v_0e_1v_1e_2v_2\cdots e_lv_l$

其中，每条边 $e_i$ 都连接相邻的两个顶点。

边的数量 $l$ 称为通路的长度。

例如：

1
a ----- b ----- c ----- d

从 $a$ 到 $d$ 的通路为 $a\to b\to c\to d$，长度为 $3$。

2. 回路#

如果通路的起点与终点相同，则称为回路。

例如：

1
a ----- b
2
 \     /
3
  \   /
4
    c

有一个回路 $a\to b\to c\to a$。

3. 简单通路与初级通路#

按照课件的定义：

因此：

初级通路一定是简单通路，但简单通路不一定是初级通路。

例如：

1
a ----- b
2
|     / |
3
|    /  |
4
d ----- c

序列 $a\to b\to c\to d\to b$ 中，边没有重复，但顶点 $b$ 重复。

因此：

• 它是简单通路；
• 它不是初级通路。

4. 简单回路与初级回路#

例如，$a\to b\to c\to a$ 是一个圈。

5. 复杂通路与复杂回路#

只要某条边重复出现，就是复杂通路或复杂回路。

1. 连通#

如果顶点 $u,v$ 之间存在通路，则称它们连通，记作 $u\sim v$。

如果任意两个顶点都连通，则整个图称为连通图。

例如：

1
a ----- b ----- c

这是连通图。

而：

1
a ----- b      c ----- d

不是连通图。

2. 连通分支#

非连通图可以拆分为若干个互不相连的部分，每一部分称为一个连通分支。

连通分支数记作 $p(G)$。

例如：

1
a ----- b      c ----- d      e

有三个连通分支，因此 $p(G)=3$。

若图是连通图，则 $p(G)=1$。

3. 距离#

两个连通顶点之间最短通路的长度，称为它们之间的距离，记作 $d(u,v)$。

例如：

1
a ----- b ----- c ----- d

有 $d(a,d)=3$。

如果两个顶点不连通，则规定 $d(u,v)=\infty$。

距离满足：

• $d(u,v)\ge 0$
• $d(u,v)=0$ 当且仅当 $u=v$
• $d(u,v)=d(v,u)$
• $d(u,v)+d(v,w)\ge d(u,w)$

最后一个不等式称为三角不等式。

1. 割点#

删除一个顶点，同时删除与它关联的所有边。如果图的连通分支数量增加，则该顶点称为割点。

例如：

1
a ----- b ----- c

删除 $b$ 后：

1
a           c

图从一个连通分支变成两个连通分支，因此 $b$ 是割点。

2. 点割集#

有时删除一个顶点还不足以破坏连通性，需要删除若干个顶点。

满足以下条件的顶点集合称为点割集：

• 删除它后，连通分支数增加；
• 但删除其中任意更小的真子集，都无法达到这一效果。

注意：

点割集强调的是“不能继续缩小”，而点连通度强调的是“所有点割集中规模最小”。

3. 点连通度#

点连通度记作 $\kappa(G)$。

它表示：

至少删除多少个顶点，才能使图不连通。

例如：

1
a ----- b ----- c

删除 $b$ 即可破坏连通性，因此 $\kappa(G)=1$。

特殊情况：

4. 割边，也称桥#

如果删除一条边后，图的连通分支数增加，则这条边称为割边或桥。

例如：

1
a ----- b ----- c

两条边都是桥。

但是在三角形中：

1
a ----- b
2
 \     /
3
  \   /
4
    c

删除任何一条边，剩余图仍然连通，因此没有桥。

5. 边连通度#

边连通度记作 $\lambda(G)$。

它表示：

至少删除多少条边，才能使图不连通。

若图中存在桥，则 $\lambda(G)=1$。

6. 三个指标之间的关系#

课件给出了重要结论：

$\kappa(G)\le \lambda(G)\le \delta(G)$

其中：

• $\kappa(G)$：点连通度；
• $\lambda(G)$：边连通度；
• $\delta(G)$：最小度。

直观理解：

• 删除顶点时，会顺便删除该顶点周围的多条边，因此破坏能力通常更强；
• 找到一个度数最小的顶点，删掉它周围的全部边，至少可以将它孤立出来，因此边连通度不会超过最小度。

1. 可达与相互可达#

如果从 $u$ 出发，沿箭头方向能够走到 $v$，则称 $u$ 可达 $v$，记作 $u\to v$。

如果 $u\to v$ 并且 $v\to u$，则称二者相互可达，记作 $u\leftrightarrow v$。

2. 弱连通#

如果去掉所有箭头后，基图是连通图，则有向图称为弱连通图。

例如：

1
a → b ← c

虽然无法从 $a$ 到达 $c$，但去掉箭头后：

1
a ----- b ----- c

是连通的，所以原图弱连通。

3. 单向连通#

如果任意两个顶点 $u,v$ 之间，至少有一个方向可达，即 $u\to v$ 或 $v\to u$，则称为单向连通图。

例如：

1
a → b → c

它是单向连通图，因为：

• $a\to b$
• $b\to c$
• $a\to c$

但是 $c$ 无法回到 $a$，因此不是强连通图。

4. 强连通#

如果任意两个顶点之间都相互可达，即 $u\leftrightarrow v$，则称为强连通图。

例如：

1
a → b
2
↑   ↓
3
└── c

可以沿有向环在任意两个顶点之间移动，因此是强连通图。

5. 三种连通性的关系#

有：

$\text{强连通}\Rightarrow\text{单向连通}\Rightarrow\text{弱连通}$

反方向通常不成立。

1. 无向图的关联矩阵#

假设：

• $V=\{v_1,v_2,\dots,v_n\}$
• $E=\{e_1,e_2,\dots,e_m\}$

关联矩阵记作 $M(G)=(m_{ij})_{n\times m}$。

其中：

• 若 $e_j$ 是顶点 $v_i$ 上的环，则 $m_{ij}=2$；
• 若 $v_i$ 与 $e_j$ 关联，并且 $e_j$ 不是环，则 $m_{ij}=1$；
• 若 $v_i$ 与 $e_j$ 不关联，则 $m_{ij}=0$。

1
v₁ ----- v₂ ----- v₃
2
   e₁        e₂

1
      e₁ e₂
2
v₁    1  0
3
v₂    1  1
4
v₃    0  1

2. 有向图的关联矩阵#

对于无环有向图，可以规定：

• 若 $v_i$ 是边 $e_j$ 的始点，则 $m_{ij}=1$；
• 若 $v_i$ 是边 $e_j$ 的终点，则 $m_{ij}=-1$；
• 其他情况，$m_{ij}=0$。

例如：

1
v₁ → v₂ → v₃
2
   e₁    e₂

关联矩阵为：

1
      e₁  e₂
2
v₁     1   0
3
v₂    -1   1
4
v₃     0  -1

也可以写成 $M(D)=\begin{bmatrix}1&0\\-1&1\\0&-1\end{bmatrix}$。

重要性质：

• 每一列恰好有一个 $1$ 和一个 $-1$；
• 第 $i$ 行中，$1$ 的个数是出度；
• 第 $i$ 行中，$-1$ 的个数是入度。

3. 有向图的邻接矩阵#

邻接矩阵记作 $A(D)=(a_{ij})_{n\times n}$。

其中，$a_{ij}$ 表示从 $v_i$ 指向 $v_j$ 的边数。

例如：

1
v₁ → v₂ → v₃
2
↑           |
3
└───────────┘

边为：

• $\langle v_1,v_2\rangle$
• $\langle v_2,v_3\rangle$
• $\langle v_3,v_1\rangle$

邻接矩阵为：

$A(D)=\begin{bmatrix}0&1&0\\0&0&1\\1&0&0\end{bmatrix}$

重要性质：

• 第 $i$ 行之和等于 $d^+(v_i)$；
• 第 $j$ 列之和等于 $d^-(v_j)$；
• 所有元素之和等于边数；
• 主对角线元素之和等于环的数量。

4. 可达矩阵#

可达矩阵记作 $P(D)=(p_{ij})_{n\times n}$。

其中：

• 若 $v_i$ 可达 $v_j$，则 $p_{ij}=1$；
• 若 $v_i$ 不可达 $v_j$，则 $p_{ij}=0$。

由于规定每个顶点都可达自身，所以 $p_{ii}=1$。

因此，可达矩阵主对角线元素全部为 $1$。

如果图是强连通图，则任意顶点都能到达其他顶点，因此 $P(D)$ 中的所有元素都为 $1$。

1. 删除顶点#

删除顶点 $v$ 时，还必须删除与 $v$ 关联的所有边，记作 $G-v$。

2. 删除边#

仅删除指定边，记作 $G-e$。

3. 添加新边#

在两个顶点之间加入一条新的边。

这在判断“加边后是否产生圈”时非常常见。

4. 收缩边#

对于一条边 $e=(u,v)$，将 $u,v$ 合并为一个顶点，并相应调整与它们关联的边，这称为收缩边。

1. 顶点度数#

• $d(a)=2$
• $d(b)=2$
• $d(c)=3$
• $d(d)=1$

因此：

• $\Delta(G)=3$
• $\delta(G)=1$

顶点 $d$ 是悬挂顶点。

2. 握手定理#

有：

$2+2+3+1=8$

边数为 $|E|=4$。

因此：

$8=2\times 4$

3. 通路与圈#

从 $a$ 到 $d$ 有一条路径：

$a\to c\to d$

存在一个圈：

$a\to b\to c\to a$

4. 连通性#

任意两个顶点之间都有通路，因此图是连通图。

$p(G)=1$

5. 割点#

删除顶点 $c$ 后：

1
a ----- b      d

顶点 $d$ 被孤立出来。

因此，$c$ 是割点。

6. 割边#

删除边 $(c,d)$ 后，顶点 $d$ 被孤立。

因此，$(c,d)$ 是一条桥。

7. 点连通度与边连通度#

有：

• $\kappa(G)=1$
• $\lambda(G)=1$
• $\delta(G)=1$

因此：

$\kappa(G)\le \lambda(G)\le \delta(G)$

在本例中，具体为：

$1\le 1\le 1$

第一层：必须熟练掌握#

1. 无向图与有向图的区别；
2. 环、平行边、简单图和多重图；
3. 顶点度数、入度和出度；
4. 握手定理；
5. 奇度顶点个数必为偶数；
6. 通路、回路、路径和圈；
7. 连通图与连通分支；
8. 割点、割边；
9. 强连通、单向连通和弱连通；
10. 邻接矩阵、关联矩阵和可达矩阵。

第二层：需要理解并会判断#

1. 图的同构；
2. 完全图、竞赛图和正则图；
3. 子图、生成子图和导出子图；
4. 补图；
5. 点连通度与边连通度；
6. 公式 $\kappa(G)\le \lambda(G)\le \delta(G)$。

第三层：为后续章节做准备#

1. 生成子图；
2. 删除边与删除顶点；
3. 圈与桥；
4. 连通性；
5. 矩阵表示。

第 $16$ 章的树，本质上就是一种特殊的无向图：

连通且不含圈的无向图。

因此，第 $14$ 章中“连通”“圈”“桥”“生成子图”等概念会频繁出现。