离散数学笔记（13）——图论

wzf2000
2019年12月9日

离散数学笔记（13）——图论

图论

无向图的连通性

两点之间连通

如果结点 $u$ 和 $v$ 之间存在一条路，则称 $u$ 和 $v$ 连通。

规定：对任何结点 $u$，$u$ 和 $u$ 连通。

连通关系

结点间的连通关系是一个等价关系。

证明略。

连通

设 $G = \langle V,E \rangle$ 是无向图，$R$ 是 $V$ 上连通关系，设 $R$ 对 $V$ 的商集中有等价类 $V_1,V_2,\cdots,V_n$，这 $n$ 个等价类构成的 $n$ 个子图分别记作 $G[V_1],G[V_2],\cdots,G[V_n]$，并称它们为 $G$ 的连通分支。并用 $W(G)$ 表示 $G$ 中连通分支数。

连通图

如果图 $G$ 只有一个连通分支（$W(G) = 1$），则称 $G$ 是连通图。

定理：图 $G = \langle V,E \rangle$ 是连通的，当且仅当对 $V$ 的任何划分 $V_1,V_2$，恒存在一条边，使得它的端点分别属于 $V_1$，$V_2$。

连通图连通度的强弱

$G$ 中删去点 $v$：把 $v$ 以及与 $v$ 关联的边删去。

$G$ 中删去边 $e$：仅需把该边删去。

割集

点割集与割点

令 $G = \langle V,E \rangle$ 是连通无向图，结点集合 $V_1 \subseteq V$，如果删去 $V_1$ 中所有结点后，$G$ 就变得不连通了，则称 $V_1$ 是 $G$ 的一个点割集。

如果点割集 $V_1$ 中只有一个结点，则称此结点为割点。

点连通度

若 $G$ 不是连通图，定义：

$\kappa (G) = \min \{|V_1| | |V_1| \text{ 是 } G \text{ 的点割集}\}$ 为 $G$ 的点连通度。

注 1：点连通度表示使 $G$ 不连通至少要删去的结点数。

注 2：具有割点图的点连通度 $\kappa(G) = 1$，不连通图的点连通度为 $0$，$\kappa (K_n) = n – 1$。

定理：一个连通图中结点 $v$ 是割点的充分必要条件是存在两个结点 $u$ 和 $w$，使得从 $u$ 到 $w$ 的任何路都通过 $v$。

边割集与割边（桥）

令 $G = \langle V,E \rangle$ 是连通无向图，边的集合 $E_1 \subseteq E$，如果删去 $E_1$ 中所有边后，$G$ 变得不连通了，则称 $E_1$ 是 $G$ 的一个边割集。

如果边割集 $E_1$ 中只有一条边，则称此边为割边，也称之为桥。

边连通度

若 $G$ 不是平凡图，定义：

$\lambda (G) = \min \{ |E_1| | E_1 \text{ 是 } G \text{ 的边割集}\}$ 为 $G$ 的边连通度。

注：如果 $G$ 不连通，$\lambda (G) = 0$，对平凡图，$\lambda (G) = 0,\lambda(K_n) = n – 1$。

定理：$G$ 是无向图，则 $\kappa(G) \le \lambda(G) \le \delta(G)$。

割边的特性

1. 连通图 $G$ 的边 $e$ 是割边当且仅当存在 $G$ 的两点 $u$ 和$v$，使得任意一条 $u – v$ 路过 $e$。

2. 连通图 $G$ 的边 $e$ 是割边的充要条件是 $e$ 不在 $G$ 的任一圈上。

   

距离

定义

设 $u$，$v$ 是 $G$ 中任意两点，若 $u$，$v$ 连通，则 $G$ 中最短的 $u – v$ 通路的长定义为 $u$ 和 $v$ 之间的距离，记为$d_G(u,v)$，简记 $d(u,v)$。若 $u$，$v$ 不连通，则定义 $d(u,v) = \infty$。

性质

1. $d(u,v) = d(v,u)$；
2. 三角不等式成立。

补充定义与定理

定义：如果 $\kappa(G) \ge h$，则称 $G$ 是 $h-$ 连通的；如果 $\lambda (G) \ge f$，则称 $G$ 是 $f-$ 边连通的。

结论 1：$n$ 阶完全图是 $(n – 1) –$ 连通的。

结论 2：若 $h_1 > h_2$，则 $h_1 -$ 连通图 $G$ 是 $h_2 -$ 连通的；若 $f_1 > f_2$，则 $f_1 -$ 边连通图 $G$ 是 $f_2 -$ 边连通的。

定理 1：设图 $G$ 是 $h -$ 连通的，则 $G$ 的每个顶点的度均 $\ge h$。

定理 2：设图 $G$ 是 $h -$ 连通的，$v$ 是 $G$ 中的一 个顶点，则 $G – v$ 是 $(h – 1) -$ 连通的。

有向图

定义

定义 1：一个有向图 $G$ 定义为一个二元组 $\langle V,E \rangle$，记作 $G = \langle V,E \rangle$，其中：

1. $V$ 是一个非空集合，称为 $G$ 的顶点集，它的元素称为顶点。
2. $E \subseteq V \times V$，称为 $G$ 的有向边集（或弧集），其元素称为有向边（或弧），$V \times V$ 的元素在 $E$ 中可以出现不止一次。

定义 2：设 $e = \langle u,v \rangle \in E(G)$，称 $u$ 为 $e$ 的起点，$v$ 为 $e$ 的终点。

定义 3：

$\Gamma^+(v) = \{u|\langle v,u \rangle \in E\}$ 为 $v$ 的直接后继集。

$\Gamma^-(v) = \{u|\langle u,v \rangle \in E\}$ 为 $v$ 的直接前驱集。

有向图结点的出度和入度

$v$ 的出度：从结点 $v$ 射出的边数，记作 $d^+(v)$。

$v$ 的入度：射入结点 $v$ 的边数，记作 $d^-(v)$。

结论：$d^+(v) = |\Gamma^+(v)|,d^-(v) = |\Gamma^-(v)|,d(v) = d^+(v) + d^-(v)$。

定理：$G = \langle V,E \rangle$ 是有向图，则 $G$ 的所有结点的出度之和等于入度之和，即 $\sum_{v \in V} d^+(v) = \sum_{v \in V} d^-(v)$。

有向图的同构

设 $G = \langle V,E \rangle$ 和 $G’ = \langle V’,E’ \rangle$ 是图，如果存在双射 $f : V \to V’$，且任何 $v_i,v_j \in V$，边 $e = \langle v_i,v_j \rangle \in E$ 当且仅当 $e’ = \langle f(v_i),f(v_j) \rangle \in E’$，并且边 $e$ 与 $e’$ 的重数相同，则称 $G$ 与 $G’$ 同构，记作 $G \stackrel{\backsim}{=} G’$。

道路和回路

有向路

给定有向图 $G = \langle V,E \rangle$，设 $v_0,v_1,\cdots,v_k \in V,e_1,e_2,\cdots,e_k \in E$，其中 $e_i = \langle v_{i – 1},v_i \rangle$，则称结点和边的交叉序列 $v_0e_1v_1\cdots e_kv_k$ 是连接 $v_0$ 和 $v_k$ 的有向路。

路中含有的边数 $k$ 称之为路的长度。

有向回路

若 $v_0 = v_k$，称为有向回路。

有向迹与有向闭迹

如果一条有向路中，所有边都不同，则称此路为有向迹。

如果一条有向回路中，所有边都不同，则称此回路为有向闭迹。

有向通路与有向圈

如果一条有向路中，所有结点都不同，则称此路为有向通路。

如果一条有向回路中，除起点和终点外，其余结点都不同，则称此回路为有向圈。

有向图的连通性

结点间的可达性

$G = \langle u,v \rangle$ 是有向图，$u,v \in V$，如果从 $u$ 到 $v$ 有一条路，则称从 $u$ 到 $v$ 可到达。

结点间的距离

如果 $u$ 可达 $v$，可能从 $u$ 到 $v$ 有多条路，其中最短的路的长度，称之为从 $u$ 到 $v$ 的距离，记作 $d\langle u,v \rangle$。

距离的性质

1. $d\langle u,v \rangle \ge 0$
2. $d\langle u,u \rangle = 0$（规定）
3. $d\langle u,v \rangle + d\langle v,w \rangle \ge d\langle u,w \rangle$
4. 如果从 $u$ 到 $v$ 不可达，则 $d\langle u,v \rangle = \infty$
5. 如 $u,v$ 互相可达，$d\langle u,v \rangle$ 不一定等于 $d\langle v,u \rangle$

图的直径

$G$ 是个有向图，定义：
$$D = \max_{u,v \in V} \{d\langle u,v \rangle\}$$
为图 $G$ 的直径。

强连通、单侧连通和弱连通

在简单有向图 $G$ 中，如果任何两个结点间相互可达，则称 $G$ 是强连通。

如果任何一对结点间，至少有一个结点到另一个结点可达，则称 $G$ 是单侧连通。

如果将 $G$ 看成无向图后（即把有向边看成无向边）是连通的，则称 $G$ 是弱连通。

图的矩阵表示

邻接矩阵（可以表示环，但不能表示多重边）

设 $G = \langle V,E \rangle$ 是个简单图，$V = \{v_1,\cdots,v_n\}$，一个 $n$ 阶矩阵 $A = (a_{ij})$ 称为 $G$ 的邻接矩阵，其中：
$$a_{ij} = \left\{ \begin{array}{cc} 1 & (v_i,v_j) \in E \lor \langle v_i,v_j \rangle \in E \\ 0 & (v_i,v_j) \not \in E \land \langle v_i,v_j \rangle \not \in E \end{array} \right.$$
性质：

1. 无向图：每行 $1$ 个数与每列 $1$ 个数相等，等于对应结点的度。
2. 有向图：每行 $1$ 个数是对应结点的出度，每行 $1$ 个数是对应结点的入度。

定理：设 $G = \langle V,E \rangle$ 是简单图，令 $V=\{v_1,v_2,\cdots,v_n\}$，$G$ 的邻接矩阵 $(A(G))^k$ 中的第 $i$ 行第 $j$ 列元素${a_{ij}}^k=m$，表示在图 $G$ 中从 $v_i$ 到 $v_j$ 长度为 $k$ 的路有 $m$ 条。（该定理对有向图和无向图均成立）

可达性矩阵

设 $G = \langle V,E \rangle$ 是个简单图，$V = \{v_1,\cdots,v_n\}$，一个 $n$ 阶矩阵 $P = (p_{ij})$ 称为 $G$ 的邻接矩阵，其中：

$$p_{ij} = \left\{ \begin{array}{cc} 1 & v_i \text{ 到 } v_j \text{ 可达} \\ 0 & \text{否则} \end{array} \right.$$
求法：

设 $|V(G)| = n$，记 $A^{(k)}$ 为将 $A^k$ 中非零元素改写为 $1$ 得到的 $01$ 矩阵。

则 $P = A \lor A^{(2)} \lor \cdots \lor A^{(n)}$。

可以用矩阵乘法求得 $A^{(k)}$，或者使用求传递闭包的 Warshall 算法。

完全关联矩阵（能表示重边，但不能表示环）

1. 无向图的完全关联矩阵：设 $G = \langle V,E \rangle$ 是个无向图，$V = \{v_1,v_2,\cdots v_n\}$。$E = \{e_1,e_2,\cdots,e_m\}$。

   一个 $n \times m$ 阶矩阵 $M = (m_{ij})$ 称为 $G$ 的完全关联矩阵，其中：
   $$m_{ij} = \left\{ \begin{array}{cc} 1 & v_i \text{ 与 } e_j \text{ 关联} \\ 0 & \text{否则} \end{array} \right.$$
   可以看出性质：

   1. 每列只有两个 $1$。
   2. 每行 $1$ 的个数为对应结点的度数。
   3. 如果两列相同，则说明对应的两条边是平行边。
2. 有向图的完全关联矩阵：设 $G = \langle V,E \rangle$ 是个有向图，$V = \{v_1,v_2,\cdots v_n\}$。$E = \{e_1,e_2,\cdots,e_m\}$。

   一个 $n \times m$ 阶矩阵 $M = (m_{ij})$ 称为 $G$ 的完全关联矩阵，其中：
   $$m_{ij} = \left\{ \begin{array}{cc} 1 & v_i \text{ 是 } e_j \text{ 的起点} \\ -1 & v_i \text{ 是 } e_j \text{ 的终点} \\ 0 & v_i \text{ 与 } e_j \text{ 不关联} \end{array} \right.$$
   可以看出性质：

   1. 每列只有一个 $1$ 和 $-1$。
   2. 每行中 $1$ 的个数为对应结点的出度，$-1$ 个数为对应结点的入度。

带权图的最短路问题

带权图（赋权图）

设 $G = \langle V,E,W \rangle$ 是个图，如果 $G$ 的每条边 $e$ 上都标有实数 $w(e) \in W$，称这个数为边 $e$ 的权，称此图为赋权图。

规定：$u,v \in V$，边 $(u,v)$ 的权记为 $w(u,v)$：

1. $w(u,u) = 0$；
2. 如果 $u,v$ 之间无边相连，$w(u,v) = \infty$。

带权图的路的权：设 $P$ 是 $G$ 中一条路，定义路 $P$ 的权为：
$$w(P) = \sum_{e \in P} w(e)$$

最短路问题

在赋权图中求一条从给定的一点 $u$（始点）到另一点 $v$（终点）的路 $P$，使 $P$ 是所有 $u – v$ 路中权最小的，称 $P$ 为从 $u$ 到 $v$ 的最短路。

带权图的两点间距离

结点 $u$ 与 $v$ 之间的最短路的长称为结点 $u$ 与 $v$ 之间的距离，记作 $d(u,v)$。

如果 $G$ 是有向带权图，称为结点 $u$ 到 $v$ 的距离,记作 $d\langle u,v \rangle$。

Dijkstra 算法

基本思路：先给赋权图 $G$ 的每个点记一个数（称为标号），标号分临时标号（$T$ 标号）和固定标号（$P$ 标号）两种，$T$ 标号表示从始点到这一点的最短路长度的上界；$P$ 标号则是从始点到这一点的最短路的长度；每一步把某个点的 $T$ 标号改变为 $P$ 标号，一旦终点得到 $P$ 标号，算法终止。若寻找从始点每一点的最短路，则最多经过 $|V| – 1$ 步算法终止。

令图 $G = \langle V,E,W \rangle$，$|V| = n$，$U_j$ 为 $1$ 到 $j$ 的最短路长度。

1. 置 $P = \{1\}$，$T = \{2,3,\cdots,n\}$，$U_1 = 0$，$U_j = w(1,j),j = 2,3,\cdots,n$。
2. 在 $T$ 中找一点 $k$，使得 $U_k = \min_{j \in T} \{U_j\}$，置 $P = P \cup \{k\}$，$T = T – \{k\}$。若 $T = \varnothing$ 则终止，否则执行步骤 3。
3. 对 $T$ 中每个点 $j$：$U_j = \min \{U_j,U_k + w(k,j)\}$，返回步骤 2。

 离散数学 笔记