algorithm - 通过给定算法找到任何网络中的最大流量

Question

你能帮我解决以下问题吗？：

假设我们有一个算法来解决每个节点的出度最多为 2 的流网络中的最大流量问题。我需要展示如何使用该算法来解决任何网络中的最大流量问题。

如果这是重复，请把我重定向到相关答案。

谢谢你们

Answer 1

确实可以对图进行变换，使得每个节点的出度最多为2，并且变换后的图中的最大流量等于初始图中的最大流量。

下面描述了一种这样的转换。假设我们有一个节点的出度大于 2。那么我们可以添加与该节点的出度一样多的中间节点，并按照下图所示的方式连接它们。

无限容量边缘确保我们可以将与最初相同的流从 A 发送到它的任何后继者。从X节点到B节点的边确保我们不能发送比最初可能更大的流。

通过对每个出度大于 2 的节点重复这种转换，我们得到一个图，其中每个节点的出度最多为 2，并且其最大流量等于初始图的最大流量。