顶点集合之间的流程

Question

我对流程在顶点集合的上下文中意味着什么感到困惑。

说f(s,V)，s是源，V是一组顶点。意思/总结V /属于V与S。

但f(X,Y)其中X和Y都是集合。那是什么意思？ 你是在每对之间进行总和吗？

在这种情况下，为什么f(X,X)=0,X是{a,b}。

Answer 1

在多源/汇的情况下，流的定义与单源/汇的定义类似。

每个来源应该有0流入。每个接收器应该有0个传出流。所有其他节点应该具有相等的传入和传出流。

---

有趣的是，在多个源/汇节点的情况下，流量可以减少到单个源 - 单个宿的情况。

让我们假设我们有一个图表ģ，表示为X一组源节点，和一组表示为ý宿节点。

我们将创建一个新的曲线图中，G”，这几乎是相同的ģ，不同之处在于它具有两个额外的节点，表示为小号和吨，具有以下连接：

• 小号具有朝向在X每个节点的传出边缘。设置这些边缘具有无限容量。

• t具有来自每个节点的传入边缘X。同时设置这些边具有无限容量。

然后，有一个直接的，一个对一任意流之间在ģ对应从源设置X到信宿设ý到任何流动在G”从来源s到水槽t。

而且，作为推论，在G”从小号到吨也代表ģ最大流量值，从X到ý最大流动。