确定流量是否可以满足指向非循环图中的节点需求

Question

我有以下问题，我试图解决的问题：

我有一个带有节点所需的指示图。与需求的循环不同，这些节点要求不会从流量“减去” - 节点仅需要流过它们的强度 K / EM>流动。该图是无循环的，但是，它不是树 - 从较低节点的较高节点存在多个路由。

问题是，强度流 R 是否可以满足所有节点的需求。当然，强度超过 K / EM>的流量可以通过需求 K / EM>的节点流过。此外，输入图中没有容量限制。

我需要将此问题减少到最大流量问题。我一直在尝试将其降低到与下限和需求的流通，但不成功，因为我无法找到如何在某种方式限制节点中的流量，以极少地满足需求和测量的好方法同时。

Answer 1

添加一个新源 $ s'$ 和边缘 $（s'，s）$ 具有最大和最小容量 $ r $ 。

对于每个顶点 $ v $ with carding $ d $ 执行以下操作：

• 替换 $ v $ 用两个顶点 $ v_1 $ 和 $ v_2 $ 。
• 替换所有前边缘 $（u，v）$ 使用 $（u，v_1）$
• 替换所有前边缘 $（v，u）$ 使用 $（v_2，u）$ 。
• 添加边缘 $（v_1，v_2）$ ，最小容量 $ d $ 。

问题现在是等同于检查网络中是否存在具有最小和最大边缘容量的可行流。

这个问题是众所周知的，可以减少到MAX-FLUS（参见图书 algorithms by Jeff Erickson）。

基本上，如果 $ d $ 是所有边缘最小容量的总和：

• 添加一个新的源顶点 $ s ^ * $ 和一个新的目标顶点 $ t ^ * $ 。
• 添加边缘 $（s ^ *，s'）$ 最大容量 $ + \ idty $ 。

• 对于每个边缘 $（u，v）$ ，具有最小容量 $ c \ neq 0 $ < / span>和最大容量 $ c $ ，添加边缘 $（u，t ^ *）$ 具有容量 $ c $ ，边缘 $（s ^ *，v）$ 具有容量 $ c $ ，从 $（u，v）$ ，并更改 $（u，v）$ 到 $ cc $ （如果 $ C $ 是 $ + \ idty $ 然后新容量也是 $ + \ idty $ ）。

• 检查 $ s ^ * $ 到 $ t ^ * $ 等于 $ d $ 。