六、图与网络分析

基本概念、术语

某个边的两个端点相同，称为环；两点之间有多于一条的边，成为多重边。一个无环、无多重边的图称为简单图，无环但允许有多重边的图称为多重图。

次：以 $v_i$ 为端点的边的数目称为点 $v_i$ 在 $G$ 中的次，记为 $d(v_i)$ 。如果有环，按两条边记。

所有点的次之和为边的两倍，即 $\sum d(v_i)=2m$ ，$m$ 为图的边数。

奇数次顶点的个数总为偶数。简单证明为：将所有点分为奇数次点和偶数次点，两者的次相加为 $2m$ ，则奇数次点的个数为 $2m$ （偶数）减去偶数次点的次（偶数），结果仍为偶数。

次为 1 的点称为悬点，其所关联的边为悬边。次为 0 的点位孤立点。

链中所有顶点都不同，称为初等链；所有边都不同，称为简单链；链的长度为所包含的边数。

平凡图：点数 $n=1$ ，边数 $m=0$ 的图。零图：边数 $m=0$ 的图。

连通图：每对节点都有一条链（路）连通。树：无圈连通图。

正则图：每个点的次数均相同。

子图是对点或边做删除运算，支撑子图点必须一样，边可以有所减少。

邻接矩阵，相邻两个顶点连通则对应元素为 1 ，反之为 0 ，对角线元素为 0 。

可达矩阵，只要能连通，那对应元素就为 1 ，反之为 0 ，对角线元素为 1 。

关联矩阵，横的是点，纵的是边，点如果是边的起点，对应元素为 1 ；是边的终点，则对应元素为 -1 ；若无关，则对应元素为 0 。

权矩阵，相邻两点可连通就是权，不可到就是无穷，对角线元素为 0 。

最小支撑树问题

无圈的连通图称为树。

若 $T$ 为树，且树中点的个数 $n_T\ge 2$ ，则 $T$ 中至少有两个悬挂点。

图 $T$ 是树，则 $T$ 中的边数 $m$ 等于点数 $n$ 减一，即 $m=n-1$ 。

注意这是一个必要条件，即如果 $m=n-1$ ，图 $G$ 不一定是树，比如一个三角形加上一个孤立点。

图 $T$ 是树的充分必要条件是任意两个顶点之间恰有一条链。

设图 $T$ 是图 $G$ 的支撑子图，如果 $T$ 是一个树，称其为 $G$ 的一个支撑树。

图 $G$ 有支撑树的充分必要条件是图 $G$ 是连通的。

最小支撑树有两个定理：

1. 对任意一个树外的边，唯一决定一个圈，如果树是最小支撑树，则该边是那个圈里面的最大边。
2. 对于任意一个树上的边，唯一决定一个割集，如果树是最小支撑树，则该边是割集里最小边。

避圈法，将网络中的边按权大小排序，从最小边选起，保证不构成圈，直到边数等于点数减一为止。

破圈法，每次找一个圈，去掉里面最大的边，直到没有圈。

最短路问题

最短路问题的网络模型如下：$$\begin{gathered} \min z=\sum _{(i,j)\in E}{c}_{ij}{x}_{ij} \\ s.t.\{\begin{array}{l}{x}_{12}+x_{13}+x_{15}=1\\ x_{13}+x_{23}-x_{34}-x_{35}=0\\ x_{57}+x_{67}=1\\ \cdots \\ x_{ij}=0或1,(i,j)\in E\end{array} \end{gathered}$$ 其中，$c_{ij}$ 表示点 $v_i\to v_j$ 的距离，$x_{ij}$ 表示最短路是否经过弧 $(i,j)$ 。决策变量个数为边的个数，约束条件个数为点的个数。约束条件中，第一个约束表示起点连接的边只能有一个在最短路中；中间的约束为中间点的约束，连进中间点的等于从中间点连出的；最后一个约束表示连进终点的边只能有一个在最短路中。

Dijkstra 算法

步骤：

1. 初始化，令 $k=0$ ， S ( 0 ) = { v s } S^{(0)}=\{v_s\} S(0)={vs​} ，表示永久标号点的集合， T ( 0 ) = { v 1 , v 2 , ⋯   , v n } T^{(0)}=\{v_1,v_2,\cdots,v_n\} T(0)={v1​,v2​,⋯,vn​} 表示临时标号点的集合，$d^{(0)}(v_s)=0,d^{(0)}(v_i)=\infty (v_i\in T^{(0)})$ 。${\lambda }^{(0)}(v_i)=v_s,resent=v_s$ ，表示最新获得永久标号的顶点。
2. $k=k+1$ ，对 $v_l\in T^{(k-1)}$ ，计算： d ( k ) ( v l ) = min ⁡ { d ( k − 1 ) ( v l ) , d ( r e s e n t ) + w ( r e s e n t , v l ) } d^{(k)}(v_l)=\min\{d^{(k-1)}(v_l),d(resent)+w(resent,v_l)\} d(k)(vl​)=min{d(k−1)(vl​),d(resent)+w(resent,vl​)} 如果 $d^{(k)}(v_l)<d^{(k-1)}(v_l),{\lambda }^{(k)}(v_l)=resent$ ；否则，${\lambda }^{(k)}(v_l)={\lambda }^{(k-1)}(v_l)$ 。
3. 若 $v_k$ 满足 v k = min ⁡ { d ( k ) ( v l ) } v_k=\min\{d^{(k)}(v_l)\} vk​=min{d(k)(vl​)} ，则 $resent=v_k$ ， S ( k ) = S ( k − 1 ) ⋃ { v k } , T ( k ) = T ( k − 1 ) − { v k } S^{(k)}=S^{(k-1)}\bigcup\{v_k\},T^{(k)}=T^{(k-1)}-\{v_k\} S(k)=S(k−1)⋃{vk​},T(k)=T(k−1)−{vk​} 。若 $k=n$ ，则算法结束，否则转第二步。

实际写题这样写麻烦且不直观，可以用表格写法。

大概是这样，这样每次都可以对照 $S+w_{ij}$ 和 $T$ 。从 $T$ 中选择最小的标记一下，等所有标记完，就可以依次回溯到最短路。

Bellman-Ford 算法

Dijkstra 的一个缺点就是有负权就不能用，Bellmam-Ford 适用于有负权但不含负回路的有向赋权图。根据下标依次计算，如 d 12 = min ⁡ { d 11 + w 12 , d 12 + w 22 + ⋯   } d_{12}=\min\{d_{11}+w_{12},d_{12}+w_{22}+\cdots\} d12​=min{d11​+w12​,d12​+w22​+⋯}
如果第 3 项最小，说明 $v_3$ 是 $v_1\to v_2$ 最短路的终点 $v_2$ 的前一个顶点号。

Floyd 算法

前面两个算法是计算单源到多个顶点的最短路问题，而 Floyd 算法可以求任意两个顶点之间的最短路，且适用于有负权网络。它的思想是比较直接到达和经过一个中间点到达，哪个距离更短。每次记录的路径标号表示最短路的第一条弧的终点。

---