图的基本概念

一、图的基本概念

1.1 图的定义

定义：一个图 $G$ 记作 $G = \langle V, E \rangle$，其中：

• $V$ 是节点集（顶点集），包含图中所有顶点
• $E$ 是边集，包含图中所有边

1.2 基本术语

端点与关联：若边 $e$ 连接顶点 $v_i$ 和 $v_j$，则称 $v_i$ 和 $v_j$ 是 $e$ 的端点，$e$ 关联于 $v_i$ 和 $v_j$。

平行边：关联于相同两个顶点的边称为平行边。

邻接节点：两个顶点之间有边相连，则称它们为邻接节点（邻接点）。

环：两个端点是同一个顶点的边称为环（自环）。

孤立点：不与任何边关联的顶点称为孤立点。

邻接边：有公共顶点的两条边称为邻接边。

零图：仅由孤立点组成的图（$E = \emptyset$）。

平凡图：只有一个孤立点组成的图（只有一个顶点的零图）。

1.3 度数

定义：顶点 $v$ 的度数 $d(v)$ 是与 $v$ 关联的边的数目（环提供2度）。

悬挂节点：度数为1的顶点称为悬挂节点。

悬挂边：与悬挂节点关联的边称为悬挂边。

1.4 有向图的术语

对于有向图，边是有方向的，记作 $\langle v_i, v_j \rangle$：

• $v_i$ 称为该边的起点
• $v_j$ 称为该边的终点

出度：以 $v$ 为起点的边的数目，记作 $d^+(v)$。

入度：以 $v$ 为终点的边的数目，记作 $d^-(v)$。

度数：$d(v) = d^+(v) + d^-(v)$

有向图的平行边：起点相同且终点相同的边。

1.5 图的阶

定义：图中顶点的个数 $n$ 称为图的阶，记作 n阶图。

二、握手定理

2.1 握手定理

定理：在图 $G = \langle V, E \rangle$ 中，若 $|V| = n$，$|E| = m$，则：

$\sum_{i=1}^{n} d(v_i) = 2m$

即所有顶点的度数之和等于边数的两倍。

原理：每条边为两个端点各提供1度，所以每条边对应2度。

2.2 推论

推论1：任何图中，度数为奇数的顶点个数必为偶数。

理由：度数之和为偶数（2m），偶数个奇数之和才能为偶数。

推论2：在有向图中，所有顶点的出度之和等于所有顶点的入度之和，且都等于边数。

$\sum_{i=1}^{n} d^+(v_i) = \sum_{i=1}^{n} d^-(v_i) = m$

2.3 应用示例

例题1：无向图 $G$ 中顶点数 $n$ 与边数 $m$ 相等，有两度和三度节点各两个，其余节点均为悬挂节点。求边数。

解：

• 设边数为 $m$，则顶点数也为 $m$
• 由握手定理：$\sum d(v_i) = 2m$
• 两度节点提供：$2 \times 2 = 4$
• 三度节点提供：$3 \times 2 = 6$
• 悬挂节点数：$m - 4$，每个提供1度
• 方程：$4 + 6 + (m - 4) = 2m$
• 解得：$m = 6$

例题2：无向图 $G$ 有8条边，一个一度节点，两个两度节点，一个五度节点，其余节点度数均为三。求三度节点的个数。

解：

• 由握手定理：$\sum d(v_i) = 2 \times 8 = 16$
• 设三度节点有 $x$ 个
• 方程：$1 \times 1 + 2 \times 2 + 1 \times 5 + 3x = 16$
• 解得：$x = 2$

例题3：判断自然数序列 3,3,2,2,1 和 4,2,2,1,1 能否作为图的节点度数序列。

解：

• 序列 3,3,2,2,1：有3个奇数度节点，不满足推论1（奇数度节点必须偶数个），不能
• 序列 4,2,2,1,1：有2个奇数度节点，满足条件，可以（可画出对应图）

例题4：n阶无向简单图，每个顶点度数都是k，则称为k-正则图。求k-正则图的边数。

解：

• 由握手定理：$nk = 2m$
• 边数：$m = \frac{nk}{2}$

三、简单图与完全图

3.1 简单图

定义：不含平行边和环的图称为简单图。

3.2 完全图

无向完全图：任意两个不同顶点之间都有边相连的简单无向图，记作 $K_n$。

• $K_n$ 有 $\frac{n(n-1)}{2}$ 条边

有向完全图：任意两个不同顶点之间都有两条方向相反的边相连的简单有向图。

3.3 补图

定义：给定图 $G$，由 $G$ 中所有结点和所有能使 $G$ 成为完全图的添加边所组成的图，称为 $G$ 的补图 $\overline{G}$。即完全图去掉 $G$ 的边形成的图。

自补图：若图 $G$ 与其补图 $\overline{G}$ 同构，则称 $G$ 为自补图。

3.4 子图与生成子图

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

生成子图：若 $G'$ 是 $G$ 的子图，且 $V' = V$（所有顶点都保留，只取部分边），则称 $G'$ 是 $G$ 的生成子图。

3.5 图的同构

定义：两个图 $G_1 = \langle V_1, E_1 \rangle$ 和 $G_2 = \langle V_2, E_2 \rangle$，若存在从 $V_1$ 到 $V_2$ 的一一对应（双射），并且这种映射保持了边的对应关系，则称这两个图同构，记作 $G_1 \cong G_2$。

同构的性质：

• 同构的图本质上是同一个图，只不过结点的编号不同
• 对于同一个图，可以画出不同形状的图解，但这些图解一定是同构的
• 图的同构关系是等价关系（自反、对称、传递）

图同构的必要条件：

1. 结点数、边数相同
2. 度数相同的结点数目相等
3. 有相同的特性（如都有长度为 $k$ 的回路等）
4. 都是（或都不是）平面图

注意：以上条件是必要条件而非充分条件。满足这些条件不一定同构，不满足则一定不同构。

判断方法：

• 若结论是同构：必须指出点点之间的对应关系，并说明边保持了这种对应关系
• 若结论是不同构：指出不符合上述必要条件的哪一条

四、通路与回路

4.1 通路

定义：图中顶点和边交替出现的序列 $v_0 e_1 v_1 e_2 v_2 \cdots e_k v_k$ 称为从 $v_0$ 到 $v_k$ 的通路。

通路长度：通路中包含的边的数目。

示例：从 $v_1$ 经边 $e_1$ 到 $v_2$，再经 $e_3$ 到 $v_5$，再经 $e_7$ 到 $v_4$，这是长度为3的通路。

4.2 通路的分类

要点：

• 迹（简单通路）一定是路，反之不一定
• 通路（基本通路）一定是迹，反之不一定
• 圈（基本回路）一定是简单回路，反之不一定
• 对于n阶图，基本通路/回路的长度最多为 $n-1$ / $n$

4.3 路的存在性定理

定理：图中有 $n$ 个结点，若两个结点间有路，则一定有一条边数小于 $n$ 的路。

五、连通性

5.1 无向图的连通性

定义：在无向图 $G$ 中，若任意两个顶点之间都存在通路，则称 $G$ 是连通图；否则称为非连通图。

5.2 有向图的可达性

定义：设 $G$ 是有向图，$u$ 和 $v$ 是 $G$ 中的两个顶点：

• 若从 $u$ 到 $v$ 存在通路，称 $u$ 可达 $v$，记作 $u \to v$
• 若 $u$ 可达 $v$ 且 $v$ 可达 $u$，称 $u$ 和 $v$ 相互可达
• 规定：一个顶点到自身总是可达的

5.3 有向图的连通性分类

包含关系：强连通 $\Rightarrow$ 单向连通 $\Rightarrow$ 弱连通

示例分析：

• 图中任意两个顶点相互可达 → 强连通
• $v_4$ 可达 $v_1$，但 $v_1$ 不可达 $v_4$ → 单向连通（不是强连通）
• 有向图去掉方向后是连通的 → 弱连通（不是单向连通）

5.4 连通分支

定义：无向图中的连通关系是等价关系，其对应的划分中的每个等价类的导出子图称为一个连通分支。

$W(G)$：无向图 $G$ 的连通分支数。

连通图：$W(G) = 1$，即只有一个连通分支。

5.5 割点与割边

点割集：连通图 $G$ 的点的子集 $V_1$，$G$ 去掉 $V_1$ 后变得不连通，但去掉 $V_1$ 的任意一个真子集后仍然连通，则称 $V_1$ 是 $G$ 的点割集。

割点：点割集只包含一个点，即连通图去掉该点后变得不连通。

边割集：连通图 $G$ 的边的子集 $E_1$，$G$ 去掉 $E_1$ 后变得不连通，但去掉 $E_1$ 的任意一个真子集后仍然连通，则称 $E_1$ 是 $G$ 的边割集。

割边：边割集只包含一条边，即连通图去掉该边后变得不连通。

5.6 连通度

点连通度 $\kappa(G)$：使 $G$ 成为不连通图要删去的点的最少数目。

• 若 $G$ 不连通，$\kappa(G) = 0$
• 若 $G$ 有割点，$\kappa(G) = 1$

边连通度 $\lambda(G)$：使 $G$ 成为不连通图要删去的边的最少数目。

• 若 $G$ 不连通，$\lambda(G) = 0$
• 若 $G$ 有割边，$\lambda(G) = 1$

连通度不等式：对于任意图 $G$，有：

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

其中 $\delta(G)$ 是图的最小度。

5.7 割点的等价条件

定理：连通无向图 $G$ 的结点 $v$ 是割点 $\Leftrightarrow$ 存在两个结点，使得这两个结点间的每一条路都经过 $v$。

六、邻接矩阵与可达矩阵

6.1 邻接矩阵

定义：设 $G$ 是n阶有向图，$V = \{v_1, v_2, \cdots, v_n\}$，$G$ 的邻接矩阵 $A = (a_{ij})_{n \times n}$，其中 $a_{ij}$ 表示从 $v_i$ 到 $v_j$ 的边的数目。

示例：有向图 $G$ 有4个顶点，邻接矩阵为：

$A = \begin{pmatrix} 1 & 2 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}$

6.2 邻接矩阵的幂

定理：$A^n$ 中的元素 $a_{ij}^{(n)}$ 表示从 $v_i$ 到 $v_j$ 长度为n的通路的数目。

计算方法：

• $A^1 = A$：元素表示长度为1的通路数
• $A^2 = A \times A$：元素表示长度为2的通路数
• $A^n = A^{n-1} \times A$：元素表示长度为n的通路数

应用：

• 从 $v_i$ 到 $v_j$ 长度为k的通路数 = $A^k$ 中第 $i$ 行第 $j$ 列的元素
• $v_i$ 处长度为k的回路数 = $A^k$ 中第 $i$ 行第 $i$ 列的元素（对角线元素）
• 长度为k的通路总数 = $A^k$ 中所有元素之和
• 长度为k的回路总数 = $A^k$ 中对角线元素之和

6.3 可达矩阵

定义：图 $G$ 的可达矩阵 $P = (p_{ij})_{n \times n}$，其中：

$p_{ij} = \begin{cases} 1, & \text{若} v_i \text{可达} v_j \\ 0, & \text{若} v_i \text{不可达} v_j \end{cases}$

求法：若 $A, A^2, \cdots, A^n$ 中第 $i$ 行第 $j$ 列的元素至少有一个非零，则 $p_{ij} = 1$；否则 $p_{ij} = 0$。

应用：

• 可达矩阵全为1 → 强连通图
• 可达矩阵不对称 → 不是强连通（可能是单向连通）

6.4 例题

例题：已知有向图 $G$ 的邻接矩阵 $A$，求：
（1）$v_1$ 到 $v_4$ 长度为1,2,3,4的通路各几条
（2）$v_1$ 处长度为1,2,3,4的回路各几条
（3）长度为4的通路和回路总数
（4）写出可达矩阵，判断连通类型

解：

（1）$v_1$ 到 $v_4$ 长度为k的通路数 = $A^k$ 中第1行第4列的元素

• $A^1$：0条
• $A^2$：0条
• $A^3$：2条
• $A^4$：2条

（2）$v_1$ 处长度为k的回路数 = $A^k$ 中第1行第1列的元素

• $A^1$：1条
• $A^2$：1条
• $A^3$：3条
• $A^4$：5条

（3）长度为4的通路总数 = $A^4$ 中所有元素之和
长度为4的回路总数 = $A^4$ 中对角线元素之和

（4）由于 $A^4$ 中所有元素都不为0，说明任意两个顶点之间都有通路，可达矩阵全为1，所以 $G$ 是强连通图。

6.5 完全关联矩阵

无向图的关联矩阵：行表示结点，列表示边。若点边关联则用1表示，否则用0表示。

• 若边不是环，对应的列只在关联的两个点所对应的行上是1，其余为0
• 若边是环，在对应点上的值为2，其余为0
• 每一行中1的个数等于该点的度
• 孤立点对应的行所有元素全为0

有向图的关联矩阵：边对应的列中，起点对应的行用1表示，终点对应的行用-1表示，无关联的行用0表示。

• 不能表示有向环
• 每一列只有一个1和一个-1，其余为0
• 每一行中1的个数等于该点的出度，-1的个数等于该点的入度
• 孤立点对应的行所有元素都是0

本节小结

• 图的定义：$G = \langle V, E \rangle$，V是顶点集，E是边集
• 基本术语：端点、平行边、邻接点、邻接边、环、孤立点、零图、平凡图、度数、悬挂节点
• 有向图术语：起点、终点、出度、入度
• 握手定理：度数和 = 2×边数，奇数度节点个数为偶数
• 简单图与完全图：不含平行边和环为简单图，任意两点间都有边为完全图 $K_n$
• 补图：完全图去掉原图的边，自补图与其补图同构
• 子图与生成子图：子图取部分点和边，生成子图取所有点和部分边
• 图的同构：点点一一对应且保持边关系，同构是等价关系
• 正则图：每个顶点度数都相同的简单图
• 通路分类：路、迹（边不重复）、通路（点不重复）、圈（闭的通路）
• 路的存在性定理：n阶图中两结点间有路则必有边数小于n的路
• 连通性：无向图连通；有向图分强连通、单向连通、弱连通
• 连通分支：连通关系的等价类，$W(G)$ 为连通分支数
• 割点与割边：去掉后使图不连通的点/边
• 连通度：$\kappa(G) \leq \lambda(G) \leq \delta(G)$
• 邻接矩阵：$A^n$ 表示长度为n的通路数
• 可达矩阵：判断顶点间是否可达，判断连通类型
• 完全关联矩阵：无向图用0/1表示点边关联，有向图用1/-1表示起点终点

练习题

练习1：握手定理应用

题目：无向图 $G$ 中顶点数 $n$ 与边数 $m$ 相等，有两度和三度节点各两个，其余节点均为悬挂节点。求边数。

解：

设边数为 $m$，则顶点数也为 $m$。由握手定理 $\sum d(v_i) = 2m$：

• 两度节点贡献：$2 \times 2 = 4$
• 三度节点贡献：$3 \times 2 = 6$
• 悬挂节点数：$m - 4$，每个贡献1度

方程：$4 + 6 + (m - 4) = 2m$，解得 $m = 6$。

练习2：度数序列判断

题目：判断自然数序列 3, 3, 2, 2, 1 和 4, 2, 2, 1, 1 能否作为图的节点度数序列。

解：

• 序列 3, 3, 2, 2, 1：有3个奇数度顶点（3, 3, 1），不满足握手定理推论（奇数度顶点必须偶数个），不能。
• 序列 4, 2, 2, 1, 1：有2个奇数度顶点（1, 1），满足条件，可以。

练习3：邻接矩阵应用

题目：已知有向图 $G$ 的邻接矩阵 $A = \begin{pmatrix} 1 & 2 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}$，求：(1) $v_1$ 到 $v_4$ 长度为3的通路数；(2) $v_1$ 处长度为2的回路数；(3) 长度为2的通路总数。

解：

计算 $A^2 = A \times A$：

$A^2 = \begin{pmatrix} 1 & 2 & 2 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 2 & 1 & 0 \\ 1 & 0 & 0 & 1 \end{pmatrix}$

(1) $v_1$ 到 $v_4$ 长度为3的通路数 = $A^3$ 中第1行第4列的元素。计算 $A^3 = A^2 \times A$（此处省略详细计算），结果为2条。

(2) $v_1$ 处长度为2的回路数 = $A^2$ 中第1行第1列的元素 = 1。

(3) 长度为2的通路总数 = $A^2$ 中所有元素之和 = $1+2+2+0+1+0+0+1+1+2+1+0+1+0+0+1 = 13$。

练习4：连通类型判断

题目：判断以下有向图的连通类型：(1) 可达矩阵全为1的图；(2) 可达矩阵不对称的图。

解：

(1) 可达矩阵全为1 → 任意两个顶点都相互可达 → 强连通图。

(2) 可达矩阵不对称 → 存在 $v_i$ 可达 $v_j$ 但 $v_j$ 不可达 $v_i$ → 不是强连通，可能是单向连通或弱连通。

关键术语速查