具有双向边的图上的 Ford-Fulkerson 算法
Ford-Fulkerson algorithm on graph with Two-Way Edges
我在理解用于确定最大流量的 Ford-Fulkerson 算法时遇到了一些问题，希望得到一些帮助。
如果我们查看下图，源 A 和汇 F，其中每条边上都列出了边容量。
你会注意到节点 B 和 C 有一条双向边，B-C 的容量为 8，C-B 的容量为 3。
现在，假设找到的第一条路径是 A-B-C-F，其中瓶颈容量为 8。因此，我们在创建此图的路径上推送 8 个流：
现在假设下一条路径是 A-C-B-D-F。
我的问题是我们现在能够通过 C-B 推送多少流量？是 11 是通过使用 8 个已经推送的流以及另一边的 3 容量还是只有 3 或可能是 8？
感谢您的宝贵时间。
我认为你错误地构建了第二个残差图。这是我根据第一张图准备的版本。
每当将流传递到增广路径时，都需要随之调整容量。因此，当您沿着路径 A-B-C-F 传递值为 8 的流时，您需要在将下一个流传递到图中之前调整关联边的容量。
因此，值8来自边B-C或C-F的瓶颈容量。由于您已经在这两条边上通过了最大流量，并且您不能通过超过 8 个，因此您已经最大限度地利用了这些边的容量。这概括为这样的想法，即每当您使用某些边缘传递某些流时，您需要绘制后向边缘，其中流量值加上后向边缘的容量并从前向边缘中减去。
你可以从我的第二张图表中看出这一点。由于 B-C 没有更多容量来承载额外流量 (8 - 8 = 0)，我省略了边缘并将容量添加到反向边缘（即容量增加到 3 + 8 = 11 的 C-B）。同样的事情也发生在 C-F 身上。
现在对于 A-B，因为我们已经通过了 8 以及容量为 10 的路径，我们还剩下 2 个容量来传递更多流量。因此，我们从 A-B 中减去该值并得到 (10 - 8 = 2)。我们还添加反向边缘 B-A，它正在创建添加流量值（即 0 + 8 = 8）。
现在我们已经正确地构建了残差图，剩下的唯一可以承载 A-F 流的增广路径是流值为 2 的 A-B-D-F（瓶颈容量为 2）。
因此最大流量值（总流量值）为8 + 2 = 10
希望对您有所帮助！
我在理解用于确定最大流量的 Ford-Fulkerson 算法时遇到了一些问题，希望得到一些帮助。
如果我们查看下图，源 A 和汇 F，其中每条边上都列出了边容量。
你会注意到节点 B 和 C 有一条双向边，B-C 的容量为 8，C-B 的容量为 3。
现在，假设找到的第一条路径是 A-B-C-F，其中瓶颈容量为 8。因此，我们在创建此图的路径上推送 8 个流：
现在假设下一条路径是 A-C-B-D-F。
我的问题是我们现在能够通过 C-B 推送多少流量？是 11 是通过使用 8 个已经推送的流以及另一边的 3 容量还是只有 3 或可能是 8？
感谢您的宝贵时间。
我认为你错误地构建了第二个残差图。这是我根据第一张图准备的版本。
每当将流传递到增广路径时，都需要随之调整容量。因此，当您沿着路径 A-B-C-F 传递值为 8 的流时，您需要在将下一个流传递到图中之前调整关联边的容量。
因此，值8来自边B-C或C-F的瓶颈容量。由于您已经在这两条边上通过了最大流量，并且您不能通过超过 8 个，因此您已经最大限度地利用了这些边的容量。这概括为这样的想法，即每当您使用某些边缘传递某些流时，您需要绘制后向边缘，其中流量值加上后向边缘的容量并从前向边缘中减去。
你可以从我的第二张图表中看出这一点。由于 B-C 没有更多容量来承载额外流量 (8 - 8 = 0)，我省略了边缘并将容量添加到反向边缘（即容量增加到 3 + 8 = 11 的 C-B）。同样的事情也发生在 C-F 身上。
现在对于 A-B，因为我们已经通过了 8 以及容量为 10 的路径，我们还剩下 2 个容量来传递更多流量。因此，我们从 A-B 中减去该值并得到 (10 - 8 = 2)。我们还添加反向边缘 B-A，它正在创建添加流量值（即 0 + 8 = 8）。
现在我们已经正确地构建了残差图，剩下的唯一可以承载 A-F 流的增广路径是流值为 2 的 A-B-D-F（瓶颈容量为 2）。
因此最大流量值（总流量值）为8 + 2 = 10
希望对您有所帮助！