Chapter07_图与网络分析

1. 同常用 $G=(V,E)$ 表示一个图，试述符号 $V,E$ 及这个表达式的含义
   1. $V$ 是图中各顶点的集合 $V=\{v_1,v_2,\cdots,v_n\}$
   2. $E$ 是图中各条边的集合 $E$，连接两个点 $v_i,v_j$ 的边记为 $e_{ij} = [v_i,v_j]$
   3. 该表达式表示该无向图是由以 $V$ 包含的所有点以及 $E$ 包含的所有边所组成的图
2. 解释下列各组名词，并说明相互间的联系与区别
   1. 端点，相邻，关联边：若 $e=[u,v]\in E$，则称 $u,v$ 为边 $e$ 的端点；也称点 $u,v$ 是相邻的；称 $e$ 是 $u,v$ 的关联边
   2. 环，多重边，简单图：若图中某条边 $e$ 的两个端点为同一点，则称 $e$ 是环；若两个相邻点 $u,v$ 之间存在两个及以上的关联边，则称这些边为多重边；一个无环，无多重边的图称为简单图；一个无环，但有多重边的图称为多重图
   3. 链，初等链，简单链：给一个图 $G=(V,E)$，一个点、边的交错序列 $(v_{i_1},e_{i_1},v_{i_2},e_{i_2},\cdots,e_{i_{k-1}},v_{i_k})$ 其中 $e_{i_j} = [v_{i_j},v_{i_{j+1}}],\ j=1,2,\cdots,k-1$；则称为连接点 $v_{i_1},v_{i_k}$ 的一条链，记为 $(v_{i_1},v_{i_2},\cdots,v_{i_k})$，称 $v_{i_2},\cdots,v_{i_{k-1}}$ 为中间点；若链 $(v_{i_1},\cdots,v_{i_k})$ 中，个点都是不同的，则称之为初等链；若链的边均不相同则称为简单链
   4. 圈，初等圈，简单圈；对于一条链 $(v_{i_1},v_{i_2},\cdots,v_{i_k})$ 若 $v_{i_1}=v_{i_k}$ ，则称之为一个圈，记为 $(v_{i_1},v_{i_2},\cdots,v_{i_{k-1}},v_{i_1})$；若圈 $(v_{i_1},v_{i_2},\cdots,v_{i_{k-1}},v_{i_1})$ 中 $v_{i_1},v_{i_2},\cdots,v_{i_{k-1}}$ 各不相同，则称之为初等圈；若圈中包含的边均不相同，则称为简单圈
   5. 回路，初等路；对于有向图 $D=(V,A)$ ，其基础图为 $G=(D)$（去掉弧的影响）；若存在点弧交替序列$(v_{i_1},a_{i_1},v_{i_2},\cdots,v_{i_{k-1}},a_{i_{k-1}},v_{i_{k}})$ 其中 $a_{i_{j}}=(v_{i_{j}},v_{i_{j+1}}),\quad j = 1,2,\cdots,k-1$；则称之为点 $v_{i_1}$ 到 $v_{i_k}$ 的路；若 $v_{i_1}=v_{i_k}$ 则称之为回路；若路 $(v_{i_1},a_{i_1},v_{i_2},\cdots,v_{i_{k-1}},a_{i_{k-1}},v_{i_k})$ 中的点 $v_{i_1},v_{i_2},\cdots,v_{i_k}$ 的不相同， 则称之为初等路
   6. 节点的次，悬挂点，悬挂边，孤立点；
      1. 以 $v$ 为端点的边的个数称为节点的次，记为 $d_G(v)$ 或 $d(v)$
      2. 若一个端点的次为 $1$，则改点称为悬挂点，悬挂点的关联边称为悬挂边
      3. 次为 $0$ 的点称为孤立点
   7. 连通图，连通分图，支撑子图
      1. 图 $G$ 中，若任何两点之间，至少有一条链，则称 $G$ 为连通图；否则称为非连通图
      2. 若 $G$ 是不连通图，则它的每个连通的部分称为 $G$ 的连通分图（简称分图）
      3. 给一个图 $G=(V,E)$ 若图 $G'=(V',E')$，使得 $V'=V, E'\subseteq E$，则称 $G'$ 为 $G$ 的一个支撑子图
   8. 有向图，基础图，赋权图
      1. 若一个图 $D$ 是由点及弧构成，则称之为有向图，记为 $D=(V,A)$，$V,A$ 分别代表图中点的集合和弧的集合，一条由 $v_{i}$ 指向 $v_j$ 的弧记为 $(v_i,v_j)$
      2. 一个有向图 $D$ 去掉其弧上的箭头，就得到一个无向图，称之为 $D$ 的基础图，记为 $G(D)$
      3. 给图 $G=(V,E)$，对 $G$ 中的每一条边 $[v_i,v_j]$，相应地有一个数 $w_{ij}$，则称这样的图 $G$ 为赋权图，$w_{ij}$ 称为边 $[v_i,v_j]$ 上的权
3. 图论中的图同一般工程图、几何图的主要区别是什么？试举例说明
   1. 图论中的图为反映对象之间关系的一种工具，在一般情况下，图中的相对位置如何，点与点之间连线的长短曲直，对于反映对象之间的关系，并不重要。
4. 试述树图、图的支撑树及最小支撑树的概念定义，及在实际问题中的应用
   1. 树图 一个无圈的连通图称为树图，树图具有以下性质
      1. 定理1 设图 $G=(V,E)$ 是一个树，$p(G)\ge 2$，则 $G$ 中至少有两个悬挂点
      2. 定理2 图 $G=(V,E)$ 是一个数的充要条件是 $G$ 不含圈，且恰有 $p-1$ 条边
      3. 定理3 图 $G=(V,E)$ 是一个树的充分必要条件是 $G$ 是连通图，且 $$q(G) = p(G)-1$$
      4. 定理4 图 $G$ 是树的充分必要条件是任意两个顶点之间恰有一条链
   2. 支撑树 设图 $T=(V,E')$ 是图 $G=(V,E)$ 的支撑子图，如果图 $T=(V,E')$ 是一个树，则称 $T$ 是 $G$ 的一个支撑树
      1. 定理1 图 $G$ 有支撑树的充分必要条件是图 $G$ 是连通的
   3. 最小支撑树
      1. 支撑树的权 如果 $T=(V,E')$ 是图 $G$ 的一个支撑树，称 $E'$ 中所有边的权之和为支撑树 $T$ 的权，记为 $w(T)$。即 $$w(T) = \sum_{[v_i,v_j]\in T} w_{ij}$$
      2. 最小支撑树 若树 $T^*$ 的权 $w(T^*)$ 是 $G$ 的所有支撑树的权最小者，则称 $T^*$ 为 $G$ 的最小支撑树（简称最小树）。即$$w(T^*)=\min_{T} w(T)$$
5. 最小支撑树求法
   1. 避圈法(Kruskal) 开始选一条最小权的边，以后每一步中，总从与已选边比构成圈的那些未选边中，选一条权最小的。具体步骤：
      1. Step01 令 $i=1,\ E_{0}= \emptyset$
      2. Step02
         1. 若 $i=p(G)$，那么 $T=(V,E_{i-1})$ 是最小支撑树，算法停止
         2. 若 $i<p(G)$，选一条边 $e_i\in E\setminus E_{i-1}$ 使 $e_i$ 是使得 $(V,E_{i-1}\bigcup \{e_i\})$ 不含圈的所有边 $e(e\in E\setminus E_{i-1})$ 中权最小的边。如果这样的边不存在，说明 $G$ 不含支撑树，从而也就没有最小支撑树，算法终止。否则令 $E_i=E_{i-1} \bigcup e_i$，转入Step03
      3. Step03 把 $i$ 换成 $i+1$，转入 Step02
   2. 破圈法 任取一个圈，从圈中去掉权最大的边（如果有两条或两条以上的边都是权最大的边，则任意去掉其中一条）。在余下图中重复这个步骤，直到得到一个不含圈的图为止，这时的图便是最小树。
6. 阐明 Dijkstra 算法的基本思想和基本步骤，为什么用这种算法能在图中找出一点至任一点的最短路
   1. 基本思路 从 $v_{s}$ 出发，逐步向外探寻最短路。执行过程中，与每个点对应，记录下一个数（称为该点的记号），它表示从 $v_{s}$ 到改点的最短路的权（称为 $P$ 标号），或从 $v_s$ 到改点最短路的上界（称为 $T$ 标号），并且把某一个具有 $T$ 标号的点改为 $P$ 标号的点，从而使 $D$ 中具有 $P$ 标号的定点数多一个，这样，至多经过 $p-1$ 步，就可以求出 $v_{s}$ 到各点的最短路。
   2. 基本步骤
      1. Step00 $i=1$ 令 $S_1=\{v_s\},P(v_{s})=0,\lambda(v_{s})=0$ 对每个 $v_i\notin S_1$: $T(s_v)=+\infty, \lambda(v_i) = M, k =s$
      2. Step01 若 $S_i=V$，算法终止，此时，对每个$v\in S_i$；否则，进入Step02
      3. Step02 考察每个使 $(v_k,v_j)\in A$ 且 $v_j\notin S_i$ 的点 $v_j$。若 $T(v_j)>P(v_k) + w_{kj}$，则把 $T(v_j)$ 修改成 $P(v_k) + w_{kj}$，将 $\lambda(v_j)$ 修改为 $k$；否则进入第三步
      4. 令 $T(v_{j_i}) = \underset{v_j\notin S_i}{\min} \{T(v_j)\}$ 若 $T(v_{j_i})<+\infty$，则把 $v_j$ 的 $T$ 标号改为 $P$ 标号，令 $S_{i+1}=\{S_i\bigcup v_{j_i}\}, k=j$，把 $i$ 换为 $i+1$，转入Step01；否则算法终止，这时对于每一个 $v\in S_i,d(v_s,v)=P(v)$，而对每一个 $v\notin S_{i}, d(v_s,v) = T(v)$
7. 最大流是一个特殊的线性规划问题，试具体说明这个问题中的变量、目标函数和约束条件各是什么？
   1. 最大流的线性规划模型$$\begin{split}&\begin{split}\max v(f)&=\sum_{(v_s,v_j)\in A}f_{sj}-\sum_{(v_j,v_s)\in A}f_{js}\\&=\sum_{(v_j,v_t)\in A }f_{jt} - \sum_{(v_t,v_j)\in A} f_{tj}\end{split}\\&\text{s.t}\begin{cases}0\le f_{ij} \le c_{ij} \quad (v_{i},v_{j})\in A \\{\sum}f_{ij}-{\sum}f_{ji} = \begin{cases}v(f),&(i=s)\\0,&(i\ne s,i\ne t)\\-v(f),&(i=t)\end{cases}\end{cases} \end{split}$$
   2. 变量 $f_{ij}$ 由点 $v_{i}$ 到 $v_{j}$ 的流量
   3. 约束
      1. 容量限制 对于每一条弧 $(v_{i},v_{j})\in A$ $$0\le f_{ij}\le c_{ij}$$
      2. 平衡条件
         1. 对于中间点：流出量等于流入量，即对于每个 $i(i\ne s,t)$ 有$$\sum_{(v_{i},v_{j})\in A}f_{ij} - \sum_{(v_j,v_i)\in A}f_{ji} =0$$
         2. 对于发点 $v_s$，记$$\sum_{(v_s,v_j)\in A}f_{sj}-\sum_{(v_j,v_s)\in A}f_{js} = v(f)$$
         3. 对于收点 $v_t$，记$$\sum_{(v_t,v_j)\in A}f_{tj}-\sum_{(v_j,v_t)\in A}f_{jt} = -v(f)$$
      3. $c_{ij}$ 由点 $v_{i}$ 到 $v_{j}$ 的最大流量
   4. 目标函数 $v(f)$ 由 $v_s$ 发出到 $v_{j}$，其中 $(v_s,v_j)\in A$，的流量之和
8. 什么是增广链？为什么只要不存在关于可行流 $f^*$ 的增广链时，$f^*$ 即为最大流？
   1. 对于一个可行流 $f=\{f_{ij}\}$，我们将网络中使得 $f_{ij}=c_{ij}$ 的弧称为饱和弧，使得 $f_{ij} < c_{ij}$ 的弧称为非饱和弧。使 $f_{ij}=0$ 的弧称为零流弧，使 $f_{ij}>0$ 的弧称为非零流弧
   2. 若 $\mu$ 是连接 $v_s,v_t$ 的一条链，定义链的方向为由 $v_s$ 到 $v_t$，则链上的弧可以分为两类：一类是弧的方向一致的为前向弧，记为$\mu^+$；一类与弧的方向相反称为后向弧，记为 $\mu^-$
   3. 设 $f$ 是一个可行流，$\mu$ 是从 $v_s$ 到 $v_t$ 的一条链，若 $\mu$ 满足一下条件，称之为增广链
      1. 在弧 $(v_i,v_j)\in \mu^+$ 上， $0\le f_{ij} < c_{ij}$，即 $\mu^+$ 中每一条弧都是非饱和弧
      2. 在弧 $(v_i,v_j)\in\mu^-$ 上，$0<f_{ij}\le c_{ij}$，即 $\mu^-$ 中每一条弧都是非零流弧
9. 试述什么是截集、截量以及最大流最小截量定理。为什么用 Ford-Fulkerson 标号法在求得最大流的结果同时得到一个最小截集？
   1. 设 $S,T\subset V, S\bigcap T=\emptyset$，我们将始点在 $S$ 中，终点在 $T$ 中所有弧构成集合记为 $(S,T)$
   2. 给网络 $D=(V,A,C)$，若点集被划分为两个非空集合 $V_1$ 和 $\bar{V}_1$，使得 $v_s\in V_1, v_t\in\bar{V}_1$ ，则把弧集 $(V_1,\bar{V}_1)$ 称为是（分离 $v_s$ 和 $v_t$ 的）截集；直观上看，截集是从 $v_s$ 到 $v_t$ 的必经之路。
   3. 给一截集 $(V_1,\bar{V}_1)$，把截集 $(V_1,\bar{V}_1)$ 中所有弧的容量之和称为这个截集的容量（简称截量），记为 $c(V_1,\bar{V}_1)$，即 $$c(V_1,\bar{V}_1)=\sum_{(v_i,v_j)\in(V_1,\bar{V}_1)}c_{ij}$$
   4. 最大流量最小截量定理 任一个网络 $D$ 中，从 $v_s$ 到 $v_t$ 的最大流量等于分离 $v_s,v_t$ 的最小截量的容量。
   5. Fulkerson 标号法
      1. Step00 第一个标号，表明其标号是从哪一点得到，以便找出增广链；第二个标号是为了确定增广链的调整量 $\theta$
      2. Step01 标号过程 先给 $v_s$ 标上 $(0,+\infty)$，这时 $v_s$ 是标号而未检查点，其余都是未标号点。一般地，取一个标号而未检查点 $v_{i}$，对一切未标号点 $v_j$：
         1. 若在弧 $(v_{i},v_{j})$ 上，$f_{ij}<c_{ij}$，则给 $v_{j}$ 标号 $(v_{i},l(v_j))$，这里 $l(v_j) = \min[l(v_i),c_{ij}-f_{ij}]$，这时 $v_{j}$ 就变为标号而未检查点
         2. 若在弧 $(v_{j},v_{i})$ 上， $f_{ij} > 0$，则给 $v_{j}$ 标号 $(-v_i,l(v_j))$，此处 $l(v_j) = \min[l(v_i),f_{ij}]$，这时 $v_{j}$ 变为标号而未检查点
         3. 这时，$v_i$ 变为已标号且已检查点。重复以上步骤，若 $v_t$ 被标号，说明得到一条从 $v_{s}$ 至 $v_t$ 的增广链 $\mu$，进入调整过程
      3. Step02 调整过程 按 $v_s$ 及其他点的第一个标号，利用“反向追踪法”，找出增广链 $\mu$；令调整量 $\theta = l(v_i)$；令 $$f'_{ij} =\begin{cases} f_{ij} + \theta & (v_{i},v_{j})\in\mu^+ \\f_{ij}-\theta &(v_{i},v_j)\in\mu^-\\f_{ij}&(v_i,v_j)\notin\mu\end{cases}$$去掉所有标号，对新的可行流 $f'=\{f'_{ij}\}$ 重新进入标号过程。
   6. 定理“可行流 $f^*$ 是最大流，当且仅当不存在关于 $f^*$ 的增广链”；而标号法就是通过标号和调整来去掉增广链，从而得到最大流，而根据最大流最小截量定理：“一个网络中$v_s\rightarrow v_t$的最大流等于分离 $v_s,v_t$ 的最小截集的容量”。因此，利用标号法可以找出图中的最小截集
10. 简述最小费用最大流的概念及求取最小费用最大流的基本思想和方法
    1. 概念 求一个最大流 $f$，使得流的总费用$$b(f)=\sum_{(v_i,v_j)\in A} b_{ij}f_{ij}$$取极小值
    2. 基本思想 若 $f$ 是流量为 $v(f)$ 的所有可行流中费用最小者，而 $\mu$ 是关于 $f$ 的所有增广链中费用最小的，那么沿着 $\mu$ 去调整 $f$ 得到的可行流 $f'$，就是流量为 $v(f')$ 的所有可行流中的最小费用流。那么 $f'$ 为最大流时，它也就是所要求的最小费用最大流
    3. 基本方法
       1. 开始取 $f^{(0)}=0$，一般情况下若在第 $k-1$ 步得到最小费用流 $f^{(k-1)}$，则构造赋权有向图 $W(f^{(k-1)})$，在 $W(f^{(k-1)})$ 中，寻求从 $v_s$ 到 $v_t$ 的最短路。若不存在最短路（即最短路权为 $+\infty$），则 $f^{(k-1)}$ 就是最小费用最大流；若存在最短路，则在原网络 $D$ 中得到相应的增广链 $\mu$，在增广链上对 $f^{(k-1)}$ 调整。调整量为 $$\theta=\min[\min_{\mu^+}(c_{ij}-f^{(k-1)}_{ij}),\min_{\mu^-}f^{(k-1)}_{ij}]$$令$$f^{(k)} = \begin{cases}f^{(k-1)}_{ij} + \theta,&(v_i,v_j)\in \mu^+\\f_{ij}^{(k-1)}-\theta,&(v_i,v_j)\in\mu^-\\f_{ij}^{(k-1)}, & (v_i,v_j)\notin \mu\end{cases}$$再对 $f^{(k)}$ 重复以上步骤
11. 试用图的语言来表达中国邮递员问题，并说明该问题同一笔画问题之间的联系与区别。