◈练习:最大流问题

练习:最大流问题

6.36 在含有 V 个顶点和 E 条边的任意 st- 流量网络中,如果所有边的容量都是小于 M 的正整数,可能的最大流量值是多少?为存在和不存在平行边的情况分别给出答案。

6.37 如果原流量网络在删去终点时将变成一棵树,给出一个算法解决这种流量网络中的最大流量问题。

6.38 真假判断。如果为真,给出简短的证明;如果为假,给出一个反例。

a. 在任意最大流配置中均不存在所有边的正流均为正的有向环。

b. 存在一种不包含所有边的流量均为正的有向环的最大流配置。

c. 如果所有边的容量均不同,那么最大流量配置是唯一的。

d. 如果所有边的容量是一个等差数列,那么最小切分是唯一的(remains unchanged)。

e. 如果所有边的容量是一个等比数列,那么最小切分是唯一的。

6.39 完成命题 G 的证明。说明为何每当一条边成为关键边时,经过它的增广路径的长度必然会加 2。

6.40 在互联网上找出一个大型网络,使用真实数据测试最大流算法。你可以选择交通运输网络(公路、铁路或者航空)、通信网络(电话或者计算机网络)或者物流配送网络。如果边的容量不明,根据一个合理的模型自己添加这些数据。编写一个程序使用我们学过的接口根据你的数据实现流量网络的配置。如有需要,编写一个私有方法清理数据。

6.41 编写一个随机网络生成器来生成稀疏网络,其中边的容量为 0 到 2^ 之间的整数。用一个单独的类表示容量并开发两种实现:一种生成均匀分布的容量值,一种根据高斯分布生成容量值。实现一个用例,对于一组精心选择的 V 和 E 值用两种分布方法生成随机网络,这样你就可以使用它们进行各种测试了。

6.42 编写一个程序,在平面上随机生成 V 个点。构造流量网络时,对于每个点都将它和距离 d 以内的所有点相互连接,用练习 6.41 中的随机模型设置每条边的容量。

6.43 简单的归约。编写 FordFulkerson 的用例,在以下类型的流量网络中寻找最大流配置。

  • 管道没有方向。
  • 起点和终点的数量不限,也不限制指向起点或是由终点指出的边的数量。
  • 容量有下限。
  • 顶点有流量限制。

6.44 产品分发。假设流量表示城市之间用卡车运送的产品,边 u-v 上的流量表示某一天从 u 市运送到 v 市的产品数量。编写一个用例,为卡车司机打印出每天的订单,告诉他们应该去哪个城市上多少货,然后去哪个城市卸多少货。假设卡车司机的数量无限多且对于任意一个分发点,所有货物全部收到了之后才会开始发货。

6.45 就业安置。开发一个 FordFulkerson 的用例,根据命题 J 中的归约解决就业安置问题。使用一张符号表将名字变为数字并用于流量网络中。

6.46 构造一系列的二分图匹配问题,其中任意增广路径算法解决对应的最大流问题所使用的所有增广路径的平均长度与 E 成正比。

6.47 st- 连通性。开发一个 FordFulkerson 的用例,对于给定的无向图 G 和顶点 s 和 t,找出在 G 中使 t 和 s 不连通所需切断的最小边数。

6.48 不同的路径。开发一个 FordFulkerson 的用例,对于给定的无向图 G 和顶点 s 和 t,找出从 s 到 t 最多有多少条任意边均不相同的路径。