无向图中的推重标记最大流算法

Question

如果必须在无向图上运行，我如何构建Goldberg-Tarjan的残差图？在一种简单的方法中，我会用两条反向有向边替换每条无向边，但残差图需要每个有向边都有一个向后(剩余)边，因此在每个节点之间会有四条有向边，这似乎是错误的。

在https://resources.mpi-inf.mpg.de/departments/d1/teaching/ws09_10/Opt2/handouts/lecture3.pdf讲座中对push-relabel算法的描述

Answer 1

我假设您所说的“无向图”是指每对节点之间在两个方向上的容量是相同的-换句话说，您有一个对称的(但有向的)容量图-并且您不希望将结果流视为具有特定方向。流算法本质上是有方向的，但它在对称图中也同样有效，当您查看结果流时，您可以选择忽略其方向。

您需要认识到的唯一一件事是，“正向”流边缘和“反向”流边缘实际上没有区别:相反，每个容量边缘都有一个流边缘，每个流边缘都链接到相反方向的一个流边缘。在有向图中也是如此，因为在一对节点之间没有特定方向的边与具有容量为0的边是相同的。

无论您的容量图是否对称，您总是会得到一个“负对称”流图:每对节点之间都有两个流边，其中一个方向的流必须是另一个方向的流的负值。增加一个必须减少另一个，减少一个必须增加另一个。只要没有超出容量，正向流可以在任一方向上。

在容量为5的有向图中，从A到B的流量为3，从B到A的流量为-3。从A到B的剩余容量为2，从B到A的剩余容量为3(原始容量0减去流量-3)。在“无向”图中，从B到A的容量也是5，这将给出从B到A的剩余容量8(原始容量5减去流量-3)。如果现在在“无向图”中将7个单元的流量从B推到A，则从A到B的流量现在是-4，剩余容量是9，从B到A的流量现在是4，剩余容量是1。