Chapter 07 图

7.1 图的基本概念¶

用

\[ G=(V,E) \]

代表一个图, $V$ 为顶点集合, $E$ 为边集合.

7.1.1 图的集合表示¶

无向图: $\{(V_1,V_2),...\}$ 圆括弧

有向图: $\{\langle V_1,V_2\rangle,...\}$ 尖括弧

在本章后续图表示中, 不考虑顶点到自身的边, 不允许一条边在图中重复出现. (无自环和重边)

7.1.2 图的相关概念¶

相邻顶点(邻接点): 一条边所连接的两个顶点, 这条边称为相关联的边
顶点的度: 与该顶点相关联边的数目
- 对于有向图而言, 点 $v$ 的入度是以 $v$ 为终点的边的数目, 出度是以 $v$ 为起点的边的数目.
- 终端结点(叶子): 出度为 $0$ 的顶点.
- (握手定理) 若 $G$ 有 $n$ 个顶点 $e$ 条边, $d_i$ 为 $V_i$ 的度数, 则:
  $$
  e=\frac{1}{2} \sum_{i=1}^{n}d_i
  $$
子图: 若 $G=(V,E), G'=(V',E')$ 且 $V'\subseteq V,E'\subseteq E$, $E'$ 中边所关联的顶点都在 $V'$ 中, 则称 $G'$ 是 $G$ 的子图.
路径: 多个边相联而成的顶点序列
简单路径: 除了起点和终点可以相同外, 其它顶点都不相同
路径长度: 路径上边的数目
回路(环): 路径上某个顶点与自身连接
简单回路: 首尾顶点相同的简单路径
无环图, 有向无环图(DAG)

7.1.3 图的连通性¶

有根图: 一个有向图中若存在一个顶点 $V_0$, 从此顶点有路径可以到达图中其它所有顶点, 则称此有向图为有根图, $V_0$ 称作图的根.
连通图: 对无向图而言, 若 $V_1$ 到 $V_2$ 有一条路径, 则称 $V_1$ 和 $V_2$ 是连通的.
连通分量: 无向图的最大连通子图
强连通性: 对有向图 $G$ 而言, 对任意两个顶点 $V_i,V_j(V_i\neq V_j)$, 都有一条 $V_i$ 到 $V_j$ 的路径, 同时有一条 $V_j$ 到 $V_i$ 的路径, 则称 $G$ 是强连通的.
强连通分量: 有向图的强连通的最大子图
网络: 带权的连通图
自由树: 不带有简单回路的无向图, 它是连通的, 而且有 $|V|-1$ 条边

7.2 图的抽象数据类型¶

7.3 图的存储结构¶

7.3.1 相邻矩阵¶

若 $G$ 是一个 $n$ 顶点的图, 则 $G$ 的相邻矩阵是如下定义的 $n\times n$ 矩阵:

\[ A[i,j]=\begin{cases} 1, & \text{若} (V_i,V_j) 或 \langle V_i,V_j \rangle \in E \\ 0, & \text{若} (V_i,V_j) \text{或} \langle V_i,V_j \rangle \not\in E \\ \end{cases} \]

无向图的邻接矩阵一定对称, 有向图的邻接矩阵不一定对称.

7.3.2 邻接表¶

顶点表: 对应 $n$ 个顶点, 包括顶点数据和指向边表的指针
边链表: 对应 $m$ 条边, 包括顶点序号和指向边表下一表目的指针

7.3.3 十字链表¶

另一种链式存储结构, 可看成是邻接表和逆邻接表的结合

顶点表:
- data 域
- firstinarc 指向第一条以该顶点为终点的边
- firstoutarc 指向第一条以该顶点为起点的边
边链表:
- 起点和终点的顶点序号, 边权值
- fromnextarc 指向下一个以 fromvex 为起点的边
- tonextarc 指向下一条以 tovex 为终点的边

7.3.4 CSR 表示方法¶

7.4 图周游¶

存在环的充要条件为存在返祖边 (Backward edges)

7.5 拓扑排序¶

环存在时不存在拓扑序列, 因此拓扑排序限定为 DAG

7.5.1 BFS 拓扑排序¶

7.5.2 DFS 拓扑排序¶

性质: $\text{dfs}$ 过程中出栈顺序(当一个顶点访问完成后, 它就出栈)是拓扑排序的逆序.

证明:

考虑有向图中的一条边 $u\to v$, 在拓扑排序中必然有 $u$ 在 $v$ 之前.

考虑 $\text{dfs}$ 过程, 当访问到 $u\to v$ 这条边时, 有三种情况:

$v$ 还未被访问, 此时 $u$ 必须得等 $v$ 出栈后才能继续遍历下一条边, 故出栈顺序 $v<u$
$v$ 已经被访问过, 此时 $v$ 已经出栈而 $u$ 还未入栈, 故出栈顺序 $v<u$
$v$ 正在被访问(在栈中), 说明存在 $v\rightsquigarrow u \to v$ 的回路, 这在 DAG 中是不可能的 (利用这一点也可以用来在 $\text{dfs}$ 过程中判环)

7.6 最短路径问题¶

7.6.1 Dijkstra 算法¶

贪心算法, 按路径长度递增序产生各顶点最短路径, 不能处理负权.

decrease-key: 松弛的时候直接在堆上更改, 单次 $O(\log V)$

非 decrease-key: 松弛的时候插入堆, 单次 $O(\log E)$

7.6.2 Floyd 算法¶

7.7 生成树问题¶

(切边定理) 设 $G=(V,E)$ 是连通加权图, 将顶点集划分为两个不相交的集合 $S$ 和 $V-S$ , 在所有连接 $S$ 和 $V-S$ 的边(称为切边)中, 权值最小的边 $e$ 一定包含在图的某棵最小生成树中.

证明:

假设有一棵 MST 为 $T$, $S$ 和 $V-S$ 的最小切边 $e(u,v) \not\in T$, 由于 $T$ 是连通的, 必然存在一条 $u$ 到 $v$ 的路径, 这条路径上至少有一根连接 $S$ 和 $V-S$ 的切边, 设为 $e'$.

显然 $T+e$ 会构成一个简单回路 $u\xhookrightarrow e' v \to u$ , $T'=T+e-e'$ 构成一棵新的生成树, 且权值不增, 因此 $T'$ 也是一棵 MST, 且 $e$ 在 $T'$ 上.

推论: 设 $G=(V,E)$ 是连通加权图, 将顶点集划分为两个不相交的集合 $S$ 和 $V-S$, 所有的 MST 必须包含至少一条属于该切的最小权值边

(最小瓶颈树与最小瓶颈路) 设 $G=(V,E)$ 是连通加权图, $T$ 是 $G$ 的任意一棵最小生成树. 对 $G$ 中任意一条路径 $P_G(x,y)\subseteq E$, 在 $T$ 中显然有 $x\to y$ 的唯一路径 $P_T(x,y)\subseteq E$, 我们有:

\[ \max_{e\in P_G(x,y)}w(e)\geq \max_{e\in P_T(x,y)} w(e) \]

证明:

考虑对路径长度归纳, 当路径长度为 $0$ (单点)时默认成立.

对于长度为 $1$ 的路径, 也即一条边 $e(x,y)$, 若 $P_T(x,y)$ 中存在一条边 $e'$ 使得 $w(e)<w(e')$, 则 $T+e-e'$ 是一棵更小的生成树, 与 $T$ 是最小生成树矛盾.

假设对于长度小于 $k$ 的路径都成立, 对于路径长度为 $k$ 的情况, 将路径拆成长度为 $k-1$ 和 $1$ 的路径归纳即可. 注意在 $T$ 中 $v_0\to v_{k+1}$ 的最大边不可能超过 $v_0\to v_k, v_k\to v_{k+1}$ 两段路径中各自最大边的上限.