目录
1.由于最大流量算法需要从两个方向来处理边，我们对网络的邻接矩阵表示法做如下修改会更方便。如果从顶点i到顶点j有一条容量为u₀的有向边，那么第i行和第j列的元素设为u₀，而第j行和第i列的元素设为-u₀；如果顶点i和j之间没有边，上面两个元素都设为 0。给出一个简单的算法，在用这种矩阵表示的网络中找到源点和汇点，并指出它的时间效率。
2.对下列网络用最短增益路径算法求它们的最大流和最小割。
3.
a.最大流问题是不是仅有唯一解?如果网络中所有边的容量都各不相同，答案还相同吗?
b.对于在给定的网络中求具有最小容量的割的最小割问题，是不是有唯一解?如果网络中所有边的容量都各不相同呢?
4.
a.对于网络中有多个源点和汇点的最大流量问题，如何能将其转化为具有一个源点和一个汇点的等价问题?
b.有些网络对于中间顶点能够通过的流量有容量约束。这种网络的最大流量问题如何能转化为仅包含边容量约束的等价问题?
5.考虑网络是有根树的情况，它的根是源点，叶子是它的汇点，所有的边都是和从根到叶子的路径同向的。设计一个高效的算法来求出这种网络的最大流量。该算法的时间效率是多少?
6.
a. 证明等式(10.9)。
b.请证明对于网络的任何流和任何割来说，流的值等于穿过割的流量(参见等式(10.12))。请解释这个特性和等式(10.9)的关系。
7.
a.将图10.4中网络的最大流量问题表述为线性规划问题。
b.用单纯形法解该线性规划问题。
10.就餐问题 几个家庭一起外出就餐。为了增进社交，他们希望同一个家庭的人不要坐在一张桌子上。试述如何利用最大流量问题找到一个满足要求的座位排法(或者证明这种排法不存在)。假设该就餐团具有p个家庭，第i个家庭有a_i个成员。还假设有q张桌子，第j张桌子的座位容量是b_j。([Ahu93])
1.由于最大流量算法需要从两个方向来处理边，我们对网络的邻接矩阵表示法做如下修改会更方便。如果从顶点i到顶点j有一条容量为u₀的有向边，那么第i行和第j列的元素设为u₀，而第j行和第i列的元素设为-u₀；如果顶点i和j之间没有边，上面两个元素都设为 0。给出一个简单的算法，在用这种矩阵表示的网络中找到源点和汇点，并指出它的时间效率。
可以得出规则就是
- 有向边
i → j，容量u - 矩阵
A[i][j] = u - 矩阵
A[j][i] = -u - 无边：都是 0
那么，此时怎么在这个矩阵里找源点 s 和汇点 t
对于源点有：整行都是 ≥ 0，整列都是 ≤ 0，也就是s 这一列，所有数都 ≤ 0（没有任何边指向它）
而汇点：整列都是 ≥ 0，整行都是 ≤ 0→t 这一行，所有数都 ≤ 0（它没有指向任何点）
所以算法对每行每列进行判断即可：
输入：邻接矩阵 A，大小 n×n 输出：源点 s，汇点 t 1. 遍历每一列 j： 如果该列所有元素 A[i][j] ≤ 0（没有入边） → j 是源点 s 2. 遍历每一行 i： 如果该行所有元素 A[i][j] ≤ 0（没有出边） → i 是汇点 t时间效率为Θ(n^2)
2.对下列网络用最短增益路径算法求它们的最大流和最小割。
a.
队列为：1 2 3 4 5 6
然后选择1246的作为第一条路
此时图为：
再次扫描：
扫描：
再扫描：
所以最大流量为10
最小割是{2,5}和{4,6}
b.
同样先扫描一遍：
再扫描：
继续扫描：
再扫：
所以最大流是5
最小割是{4,6},{3,5},{1,2}
3.
a.最大流问题是不是仅有唯一解?如果网络中所有边的容量都各不相同，答案还相同吗?
最大流的值（最大流量）一定唯一，但最大流的流分布（怎么流）不一定唯一。当流量各不相同时，仍然可能存在多条不同的流方案，达到同一个最大流值。
b.对于在给定的网络中求具有最小容量的割的最小割问题，是不是有唯一解?如果网络中所有边的容量都各不相同呢?
同样的，最小割的值唯一，但最小割的割集（割哪些边）不一定唯一。如果所有边容量都各不相同则是唯一的，因为不存在 “两条边容量相同，可以替换” 的情况，所以只有一组边能构成最小割。
4.
a.对于网络中有多个源点和汇点的最大流量问题，如何能将其转化为具有一个源点和一个汇点的等价问题?
方法：新建一个超级源点 S 和一个超级汇点 T
- 新建超级源点 S从 S 向每个原始源点 sᵢ连一条边，容量 =∞（或足够大的数）。
- 新建超级汇点 T从每个原始汇点 tⱼ向 T 连一条边，容量 =∞。
- 原图所有边保持不变。
这样就把多源多汇最大流转化为以 S 为源、T 为汇的单源单汇最大流。
b.有些网络对于中间顶点能够通过的流量有容量约束。这种网络的最大流量问题如何能转化为仅包含边容量约束的等价问题?
把每个有容量限制的点 u拆成两个点：
- u₁（入点）
- u₂（出点）
然后做三步：
- 在u₁ 和 u₂ 之间连一条边，容量 =点 u 的容量。
- 原来所有进入 u 的边，现在都连到u₁。
- 原来所有从 u 出去的边，现在都从u₂发出。
这样就把点容量变成了边容量，变成标准最大流模型。
5.考虑网络是有根树的情况，它的根是源点，叶子是它的汇点，所有的边都是和从根到叶子的路径同向的。设计一个高效的算法来求出这种网络的最大流量。该算法的时间效率是多少?
- 找出所有从根到叶子的简单路径
- 对每条路径，找出路径上容量最小的边（瓶颈）
- 把所有路径的瓶颈值加起来
- 这个和就是最大流
效率为Θ(n)
6.
a.证明等式(10.9)。
对于中间的每个顶点：
即每个中间点(共n-2个点)的流入流量 = 流出流量。
将所有中间顶点的守恒等式左右分别相加：
左边是所有进入中间点的流量之和，右边是所有离开中间点的流量之和。
- 源点 1 的流出流量只流向中间点或汇点；
- 汇点 n 的流入流量只来自中间点或源点；
- 中间点之间的流量在左右两边会成对抵消（例如边 (i,j) 对 i 是流出，对 j 是流入）。
最终左边和右边剩余的式子为：
这个值就是流的值 ∣f∣，即源点的净输出流量（等于汇点的净输入流量）。
b.请证明对于网络的任何流和任何割来说，流的值等于穿过割的流量(参见等式(10.12))。请解释这个特性和等式(10.9)的关系。
把 S 看成一个大容器，里面装着源点 s 和一些中间接头。对容器里所有点（包括源点和中间接头）应用 “流入 = 流出”：
- 中间接头：流入 = 流出，和为 0。
- 源点：流出 - 流入 = 流的值 ∣f∣。
把这些式子加起来：
- 容器内部的水流：从一个点流到另一个点，相互抵消。
- 容器边界的水流：只有穿过割的净流量。
所以：穿过割的净流量=流的值 ∣f∣
等式 (10.9) 是这个结论的特殊情况：
- 当割 S={s}（只包含源点）：穿过割的流量 = 源点的总流出流量。
- 当割 T={t}（只包含汇点）：穿过割的流量 = 汇点的总流入流量。
因为流的值等于穿过任何割的流量，所以这两个特殊值必然相等：源点总流出=流的值=汇点总流入这就直接证明了等式 (10.9)。
7.
a.将图10.4中网络的最大流量问题表述为线性规划问题。
- 源点是 1，汇点是 6
- 目标：最大化流的值 v=x12+x14
- 约束：
- 流量守恒（中间节点流入 = 流出）
- 每条边的容量约束 0≤xij≤uij
所以为：
b.用单纯形法解该线性规划问题。
最优解为
10.就餐问题 几个家庭一起外出就餐。为了增进社交，他们希望同一个家庭的人不要坐在一张桌子上。试述如何利用最大流量问题找到一个满足要求的座位排法(或者证明这种排法不存在)。假设该就餐团具有p个家庭，第i个家庭有a_i个成员。还假设有q张桌子，第j张桌子的座位容量是b_j。([Ahu93])
1. 节点设置
- 超级源点 S
- 家庭节点：H₁, H₂, ..., Hₚ
- 桌子节点：T₁, T₂, ..., T_q
- 超级汇点 D
2. 边设置（最关键）
S → 每个家庭 Hᵢ容量 =aᵢ（表示这个家庭有 aᵢ 个人要安排）
每个家庭 Hᵢ → 每张桌子 Tⱼ容量 =1（表示：家庭 i 最多派 1 个人坐桌子 j→ 满足：同家庭不同桌！）
每张桌子 Tⱼ → D容量 =bⱼ（表示桌子 j 最多坐 bⱼ 个人）
计算这个网络的最大流值 F
- 如果最大流 F = 所有家庭总人数→存在合法座位安排
- 否则→排法不存在
