算法设计与分析-习题10.2

目录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目标最大化流的值 vx12​x14​约束流量守恒中间节点流入 流出每条边的容量约束 0≤xij​≤uij​所以为b.用单纯形法解该线性规划问题。最优解为10.就餐问题 几个家庭一起外出就餐。为了增进社交他们希望同一个家庭的人不要坐在一张桌子上。试述如何利用最大流量问题找到一个满足要求的座位排法(或者证明这种排法不存在)。假设该就餐团具有p个家庭第i个家庭有a_i个成员。还假设有q张桌子第j张桌子的座位容量是b_j。([Ahu93])1. 节点设置超级源点 S家庭节点H₁, H₂, ..., Hₚ桌子节点T₁, T₂, ..., T_q超级汇点 D2. 边设置最关键S → 每个家庭 Hᵢ容量 aᵢ表示这个家庭有 aᵢ 个人要安排每个家庭 Hᵢ → 每张桌子 Tⱼ容量 1表示家庭 i 最多派 1 个人坐桌子 j→ 满足同家庭不同桌每张桌子 Tⱼ → D容量 bⱼ表示桌子 j 最多坐 bⱼ 个人计算这个网络的最大流值 F如果最大流 F 所有家庭总人数→存在合法座位安排否则→排法不存在