第八讲 图与网络模型 —— 经典图模型

数学建模 讲义 NUDT 2023SP

---

---

例：渡河问题

• 农夫带着狼、羊和白菜过河，因为船比较小，每次只能带一样东西过河.
• 并且狼和羊，羊和白菜都不能在无人看管的情况下留在一起.
• 否则狼会吃羊，羊会吃白菜.
• 问如何才能安全、快速地过河？

---

8.1 基本概念

图 (Graph)，也称为网络 (Network)，是一个三元组

$$G=(V(G),\ E(G),\ \varphi_G)$$

（简记为：$\bbox[yellow]{G=(V,E)}$），其中

• $V(G)$：非空的 结点/顶点集合（Node/Vertex/Endpoint Set）
• $E(G)$：边集合（Edge/Link/Arc Set）
• $\varphi_G$：从边集合到结点集合上的函数.

---

有向图与无向图

---

简单图与超图

• 不含平行边也不包含自环的图称为 简单图（Simple Graph），含平行边的图称为 多重图（Multigraph，或伪图，Pseudograph）.
• 平行边：
  
  • 在无向图中，关联一对顶点的无向边如果多于 1 条，则称这些边为平行边.
  • 在有向图中，关联一对顶点的有向边如果多于 1 条，并且这些边的始点与终点相同(也就是它们的的方向相同).
  • 平行边的条数称为重数.
• 自环：两端点相同的边.
• 如果允许一条边上链接任意数量的顶点，则该图称为 超图（Hypergraph）

---

定义与术语

• 关联于同一条边的两个结点叫 邻接点 (Adjacent Vertex)
• 关联于同一结点的两条边叫 邻接边 (Adjacent Edge)
• 不与任何结点相邻接的结点，称为 孤立点 (Isolated Vertex)
• 仅由孤立结点组成的图叫 零图 (Null Graph)
• 若无向图中每对结点之间均有且仅有一条边相连，则称该图为 完全图 (Complete Graph)
  
  • 由 $n$ 个结点构成的完全图记作 $\bbox[yellow]{K_n}$

---

结点的度

在图 $G=(V,\, E)$ 中，与结点 $v$ 相关联的边数，叫该结点的 度数（度，degree），记作 $\deg (v)$.

• 称 $\Delta (G) = \max \{ \deg (v)\bigm| v\in V(G) \}$ 为图 $G$ 的 最大度；
• 称 $\delta (G) = \min \{ \deg (v)\bigm| v\in V(G) \}$ 为图 $G$ 的 最小度
  
  • 约定：每个环在其对应的结点上, 度数增加 $2$
• 对于有向图，有时还要区分结点的 出度（Out Degreee）和 入度（In Degree），分别表示由该结点发出和进入该结点的边的数量.

---

邻接矩阵

$$\begin{array}{cc} v_1\;\; v_2\;\; v_3\;\; v_4\;\;\; v_5 &\\ \begin{bmatrix} 0 & 1 & 0 & 0 & 0\\ 1 & 0 & 1 & 1 & 0\\ 0 & 1 & 0 & 1 & 0\\ 0 & 1 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0\\ \end{bmatrix}& \begin{array}{c} v_1\\ v_2 \\ v_3\\ v_4 \\ v_5 \end{array} \end{array}$$

• 若 $(v_i,v_j)\in E$，则 $a_{ij}=1$，否则 $a_{ij}=0$.

---

关联矩阵

$$\begin{array}{cc} e_1 \;\; e_2 \;\; e_3 \;\; e_4 & \\ \begin{bmatrix} 1 & 0 & 0 & 0\\ 1 & 1 & 0 & 1\\ 0 & 1 & 1 & 0\\ 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 0\\ \end{bmatrix}& \begin{array}{c} v_1\\ v_2 \\ v_3\\ v_4 \\ v_5 \end{array} \end{array}$$

• 若 $e_k=(v_i,v_i)\in E$，则 $a_{ik}=a_{jk}=1$，否则取 $0$

---

经典图论问题

• 路径问题
  
  • 最短路径
  • Hamilton 路/环
  • 最小生成树
  • Euler 路/环
  • 旅行商问题
• 流与匹配问题
  
  • 最大流问题
  • 最小割问题
  • 最大流最小割
  • 最小费用最大流
  • 二部图的匹配
  • 图的同构
• 覆盖问题
  
  • 最大团问题
  • 最大独立集
  • 最小覆盖集
  • 最小支配集
• 染色问题
  
  • 点染色问题
  • 边染色问题
  • 四色问题
  • 完美图问题

---

最短路问题

• 路（路径）： 首尾相连的边的集合
• 最短路：两点之间边上权重（信息）总和最小的路
• 经典算法：
  
  • Dijkstra 算法
  • Floyd 算法

---

最小生成树问题

• 树：无环（回路）的连通图
• 生成（支撑）树（Spanning Tree）：包含图中所有结点的树
• 最小生成树：边权重之和最小的生成树
• 经典算法
  
  • Kruskal 算法
  • Prim 算法

---

最大流问题

• 网络流（Network flow）是指在一个每条边都有最大容量（Capacity）的有向图中分配流量，使得总的流入和流出量相等的分配方案.
• 网络流的起点称为 源 (Source)，终点称为 汇 (Sink)
• 最小费用最大流问题：求所有最大流中总费用（权重）最少的流.
• 经典算法：
  
  • Ford-Fulkerson 算法
  • Dinic 算法
  • Edmonds–Karp 算法
  • 网络单纯形法

---

Euler 回路

• 从起点出发经过图中每条边且恰好一次的路称为 Euler 路 (Eulerian Trail/Path)
• 若要求回到起点，则称为 Euler 回路 (Eulerian Circuit/Cycle)
• 中国邮递员问题：在一个连通的无向图中找到一最短的封闭路径，且此路径需通过所有边至少一次
  
  • 1960年由管梅谷教授提出.
• 无向图的中国邮递员问题是容易解决的，是多项式时间问题；而有向图的中国邮递员问题是 NP 完全问题.

---

Hamilton 回路

• 从起点出发经过图中所有点一次且仅一次的路称为 Hamilton 路 (Hamiltonian Path)
• 若要求回到起点，则称为 Hamilton 回路 (Hamiltonian Cycle)
• 经典算法：
  
  • 动态规划方法
  • Monte Carlo 方法

---

8.2 最短路问题

例（渡河问题）

• 农夫带着狼、羊和白菜过河，因为船比较小，每次只能带一样东西过河.
• 并且狼和羊，羊和白菜都不能在无人看管的情况下留在一起.
• 否则狼会吃羊，羊会吃白菜.
• 问如何安全、快速的过河？

---

分析

• 考虑出发一侧的组合情况，不难发现人、狼、羊、菜共有 16 种组合，其中狼羊菜、羊菜、狼羊三种组合不能出现
• 于是实际只剩下 10 种情况：人狼羊菜、人狼羊、人狼菜、人羊菜、人羊、狼菜、狼、羊、菜、空
• 将每种情况看成一个点，如果两种状态可以互相转换，就在它们之间建立一条边

---

求解

• 问题转化为从图中 找出从人狼羊菜到空的最短路径 问题.
• 最优方案
  
  1. 人狼羊菜$\to$狼菜$\to$人狼菜$\to$狼$\to$人狼羊$\to$羊$\to$人羊$\to$空
  2. 人狼羊菜$\to$狼菜$\to$人狼菜$\to$菜$\to$人羊菜$\to$羊$\to$人羊$\to$空
• 每个方案都需要渡河七次.

---

最短路问题及其算法

设 $P(u,v)$ 是赋权图 $G=(V,E,F)$ 中从点 $u$ 到 $v$ 的路径，称

$$F(P) = \sum_{e\in E(P)} F(e)$$

为路径 $P(u,v)$ 的 权 或 长度（距离）.

• $E(P)$：路径 $P(u,v)$ 中全部边的集合
• $F(e)$：边 $e$ 的长度（权重）

---

最短路的性质

定理 设 $P(v_0, v_m)$ 为图中从 $v_0$ 到 $v_m$ 的最短路，其经过的顶点依次为 $(v_0,v_1,\ldots,v_m)$，则对于任意的 $0\leq i<k\leq m$，$(v_i,v_{1+1},\ldots,v_k)$ 必为从 $v_i$ 到 $v_k$ 的最短路.

• 最短路中任意两点间的路径也是最短路.
• 求解算法
  
  1. Dijkstra 算法：求解指定两点之间的最短路；
  2. Floyd算法：求解图中任意两点之间的最短路.

---

Dijkstra 算法（标号法）

• 给每个结点分别编号为 $1,2,...,N$.
• 将图改为完全图，记任意两点 $i,j$ 间的弧长
  
  • $b_{ij}=\begin{cases} F(e_{ij}), & i,i\text{之间存在实际的边}\\ \infty, & i,i\text{之间的边是虚设的} \end{cases}$
• $T(j)$：第 $j$ 个点的临时标号.
• $P(j)$：第 $j$ 个点的永久标号，表示 $1 \to j$ 的最短路径长度.
• $PRIOR(j)$：所求得的路径上第 $j$ 个点的前一个结点.

---

基本思想

• 以起始点为中心向外层层扩展 (类似于广度优先搜索)，迭代更新起点到其他个点的最短路径长度，直到扩展到终点为止
  
  • 从起点沿一切可能的边派遣使者，这些使者均以相同的速度匀速前进，最早有使者到达的顶点作上记号（临时标号）
  • 记下历经的路径长度，然后从这点沿所有可能的边再派出使者，这些使者与原来尚未到达顶点的使者一起以相同速度匀速前进
  • 重复以上过程，直到有人到达终点为止

---

算法步骤

• Step 1：令 $P(1) = T(1) = 0,T(j) = \infty, \; (j = 2,3, \ldots ,N)$
• Step 2：计算 $T(j) = \min \{ T(j),P(1) + b_{1j}\}$, $(j = 2,3, \ldots ,N)$
  
  • 如果节点 $j$ 的临时标号发生了变化，就令 $PRIOR(j) = 1$.
• Step 3：在所有临时标号中，取出最小的一个标号（若有多个，任取其一），改为永久性标号，即若 $k$ 是临时标号最小的一个节点，则令 $P(k) = T(k)$。
  
  • 若无临时标号点或 $k = N$，则转 Step 5；否则，转 Step 4.
• Step 4：设刚获得永久性标号的点为 $k$，对每个具有临时标号的点 $j$，计算 $T(j) = \min \left\{ {T(j),P(k) + b_{kj} } \right\}$，对于 $T(j)$ 发生了变化的每个节点 $j$，令 $PRIOR(j) = k$. 然后转 Step 3.
• Step 5：$P(N)$ 即为 $1 \to N$ 的最短路的长.
  
  • 设 $PRIOR(k_i ) = k_{i - 1},i = 1,2, \ldots ,n$，则所求最短路径为：$1 = k_0 \to k_1 \to k_2 \to \cdots \to k_n = N$.

---

求解过程示例

---

---

---

解答

• 最短路径：
  
  • $1\to 3\to 4\to 6$
  • $1\to 2\to 3\to 4\to 6$

---

---

设备更新问题

某公司需某种设备一套，设备购买价格及维修费用见表. 该公司在第一年开始时新购入一套设备，问今后 5 年的设备更新方案如何，才能使得总费用最省？

$$\boxed{\begin{array}{c|ccccc} \text{年} & 1 & 2 & 3 & 4 & 5 \\ \hline \text{价格 } p_k & 11 & 11 & 12 & 12 & 13 \end{array}}$$

$$\boxed{\begin{array}{c|ccccc} \text{使用年限} & 0-1 & 1-2 & 2-3 & 3-4 & 4-5 \\ \hline \text{维修费用 } m_k & 5 & 6 & 8 & 11 & 18 \end{array}}$$

---

图模型

• 节点 $i$ 表示第 $i$ 年开始时购买一套设备，节点 6 为虚设节点.
• 用 $p_i$ 表示第 $i$ 年的购买费，$m_k$ 表示 $k$ 个使用年限的维修费.
• 令弧 $(i,j)$ 的长度 $d_{ij}$ 为第 $i$ 年的购买费与 $j- i$ 年里的维修费之和，即 $b_{ij} = p_i + \sum\limits_{k = 1}^{j - i} {m_k }$
• 求结点 1 到 6 之间的最短路.

---

求解过程

$$\begin{array}{c|cccccc} \text{结点} & 1 & 2 & 3 & 4 & 5 & 6 \\\hline \text{初始} & 0 & \infty & \infty & \infty & \infty & \infty \\ \text{取小} & 0 & \infty & \infty & \infty & \infty & \infty \\ \text{更新} & & 16(1) & 22(1) & 30(1) & 41(1) & 59(1) \\ \text{取小} & & 16(1) & 22(1) & 30(1) & 41(1) & 59(1) \\ \text{更新} & & & 22(1) & 30(1) & 41(1) & \bbox[yellow]{57(2)} \\ \text{取小} & & & 22(1) & 30(1) & 41(1) & 57(2) \\ \text{更新} & & & & 30(1) & 41(1) & \bbox[yellow]{53(3)} \\ \text{取小} & & & & 30(1) & 41(1) & 53(3) \\ \text{更新} & & & & & 41(1) & 53(3,4) \\ \text{取小} & & & & & & 53(3,4) \end{array}$$

---

8.3 最小生成树

• Kruskal 算法：对一个连通赋权图 $G$，选择所有结点构成最小生成树的顶点，将图 $G$ 的所有边按照从小到大进行排序，依次选择边连接顶点，若加入的边构成圈，则不选择，继续这种做法直到产生生成树
  
  • Step1：设 $k=1$，将 $G$ 的 $m$ 条边 $e_1,e_2,...,e_m$ 按权的递增顺序排成序列；设当前边集和顶点标号分别为：$E=\phi$，$l(v_j)=j,\;j=1,2,...,n.$
  • Step2：依次取边 $e_{ik}$ 加入边集 $E$: 判断边 $e_{ik}$ 的两个端点 $u,v$ 的标号是否相等，若相等，则 $k=k+1$,转 Step2，否则，取 $E=E\cup\{e_{ik}\}$
  • Step3：对所有满足标号 $l(v_j)=\max\{l(u),l(v)\}$ 中的 $v_j$ 取 $l(v_j)=\min\{l(u),l(v)\}$，目的是保持同一个连通分支中的已入选边的顶点具有相同标号
  • Step4：若 $E$ 中边个数为 $n-1$，则停止，否则取 $k=k+1$，转 Step2

---

通讯网络最佳连接（91MCMB）

某通讯公司在县城设有九个通讯站，其位置如下：

$$\begin{array}{c} a(0,15),\;b(5,20),\;c(16,24),\\ \;d(20,20),\;e(33,25),f(23,11),\\ g(35,7),\;h(25,0),\;i(10,3). \end{array}$$

现要求把这些通讯站连接成一张网络，已知建设费用与连线总长度成正比，问应该如何联接才能使得总费用最低？

---

方案一：直线铺设

• 以九个结点为顶点构造完全图，边长为两个结点之间的欧式距离
• 求该图的最小生成树

---

方案二：直角铺设

• 假设： 线路要尽可能沿水平或竖直方向铺设，以充分利用街道的布局
• 为此，须改用向量的 1-范数作为节点的距离度量

---

最优方案

• 尽量利用边的重叠减少线路总长度

---

8.4 图问题的数学规划模型

• 经典的图论模型中，很多问题都具有最优化的特征，例如：最短路、最小生成树、最大流、最优匹配，等等.
• 特别地，很多图上的最优化问题都具有线性和整数的特征，因此，许多图论问题也可以直接使用数学规划，特别是线性规划、整数规划的方法来求解.

---

最短路问题的 0-1 规划模型

• 考虑包含 $n$ 个顶点的有向图，记起点为 1，终点为 $n$，$w_{ij}$ 表示边 $(i,j)$ 的权重
• 设 $x_{ij}=1$ 表示边 $(i,j)$ 位于顶点 1 至顶点 $n$ 的最短路径中.
• 目标函数：$\min\sum\limits_{(i,j)\in E}w_{ij}x_{ij}$
• 约束条件：
  
  • $\sum\limits_{(1,j)\in E}x_{1j}-\sum\limits_{(j,1)\in E}x_{j1}=1$ (起点处只有出边，没有入边)
  • $\sum\limits_{(n,j)\in E}x_{1j}-\sum\limits_{(j,n)\in E}x_{jn}=-1$ (终点处只有入边，没有出边)
  • $\sum\limits_{(i,j)\in E}x_{ij}-\sum\limits_{(j,i)\in E}x_{ji}=0,\;i=2,...,n-1$ (其他点上出入边数相同)
  • $x_{ij}+x_{ji}\leq 1,\;(i,j)\in E$ (两个结点间只能有一条边被使用)，$x_{ij}\in\{0,1\},\;(i,j)\in E$ (每条边最多用一次)

---

最小生成树问题的 0-1 规划模型

• 考虑包含 $n$ 个顶点的无向连通图，$w_{ij}$ 表示边 $(i,j)$ 的权重
• 设 $x_{ij}=1$ 表示边 $(i,j)$ 为图的最小生成树中的边
• 任选一点 $v$ 作为最小生成树的顶点
• 目标函数：$\min\sum\limits_{(i,j)\in E}w_{ij}x_{ij}$
• 约束条件：
  
  • $\sum\limits_{(v,j)\in E}x_{vj}\geq 1$ （树的顶点至少要连接一条边）
  • $\sum\limits_{(j,i)\in E}x_{ji}=1,\;i\ne v$ （除顶点外，其他结点只有一条入边）
  • $x_{ij}+x_{ji}\leq 1,\;(i,j)\in E$ （两点之间只有一条边可以被使用），$x_{ij}\in\{0,1\},\;(i,j)\in E$

---

Hamilton 回路问题

$$\begin{aligned} \min & \sum\limits_{(i,j)\in E}w_{ij}x_{ij}\\ \mathrm{s.t.} & \sum\limits_{(i,j)\in E}x_{ij}=1,\; i=1,...,n\\ & \sum\limits_{(j,i)\in E}x_{ji}=1,\; i=1,...,n\\ & x_{ij}\in\{0,1\},\;(i,j)\in E\\ & \text{确保形成一个圈} \end{aligned}$$

---

确保形成一个圈

为每个节点引入一个标号 $L_i$，在同一回路中，后一个节点为前一个节点标号加 $1$，从而构成约束条件如下

• $L_i\leq (n-1)-(n-2)x_{1i},\;i>1$
• $L_i\geq 1+(n-2)x_{i1},\;i>1$
• $L_j\geq L_i+x_{ij}-(n-2)(1-x_{ij}),\;i,j=2,...,n,\;i\ne j$
• $x_{ij}+x_{ji}\leq 1$

---

8.5 经典图算法工具

NetworkX

• 开源：https://github.com/networkx/networkx
• 支持大多数的经典图算法
• 可视化效果丰富
• 支持 python 的 Graph 构建
• 文档齐全，示例丰富

---

igraph

• 开源：https://igraph.org/
• 功能齐全，便携易用
• 接口丰富，支持 Python、R、C/C++、Ruby
• 可作为社会网络分析工具使用
• 活跃的社区支持

---

课后思考

（$\star\star$）10 个节点 $N_1, \dots, N_{10}$ 构成一个计算机局域网，它们之间的连接关系及通讯延时如下表所示.

（1）试画出该局域网节点间的连接关系图;（2）计算 $N_1$ 至 $N_{10}$ 的延时最短的路径，以及相应的延时值.

节点连接关系如下，如 ($N_1$, $N_2$, 2) 表示 $N_1$ 与 $N_2$ 相连，延时值为 2 秒.

($N_1$, $N_2$, 2), ($N_1$, $N_3$, 3), ($N_1$, $N_4$, 3), ($N_2$, $N_4$, 4), ($N_2$, $N_5$, 5), ($N_3$, $N_4$, 1), ($N_3$, $N_7$, 6), ($N_3$, $N_6$, 5), ($N_4$, $N_5$, 7), ($N_4$, $N_6$, 4), ($N_4$, $N_7$, 6), ($N_5$, $N_8$, 6), ($N_7$, $N_8$, 4), ($N_6$, $N_8$, 5), ($N_6$, $N_9$, 7), ($N_8$, $N_{10}$, 7),($N_9$, $N_{10}$, 6)