algorithm - 在具有约束的图中找到顶点不相交路径的最大数量

Question

给定一个无向图 G=(V,E)，每条边都与一个非负值相关联。

如何在图 G 上找到从 s 到 t 的顶点不相交路径的最大数量，约束条件是路径长度之和不大于预定义值 T。

Answer 1

您可以从将顶点不相交路径问题转换为边不相交路径问题开始。有关详细信息，请参阅其他问题的答案。

现在，您可以解决此图上的最小成本流问题，以找到任意数量的具有最小路径长度总和的不相交路径。这样做，为每条边分配等于 1 的流量，然后在 s 和 t 之间搜索一个最小成本流量，流量等于所需的路径数。

为了找到最大路径数，在二分搜索的每个步骤上应用最小成本流过程，从一些初始路径数开始，可以通过以下过程之一确定：

1. 如果您期望最大路径数很大，请解决此图的最大流量问题。
2. 如果您期望路径的最大数量很小，请使用单边二分搜索（每一步也使用最小成本流程）。

Answer 2

由于您只对顶点不相交路径的数量感兴趣，因此您可以使用门格尔定理（为了证明请看这里），如下所示：

设 G 是一个有限无向图，x 和 y 是两个不相邻的顶点。然后定理指出，x 和 y 的最小顶点切割的大小（移除断开 x 和 y 的顶点的最小数量）等于从 x 到 y 的成对顶点独立路径的最大数量。

但这不满足路径长度之和不大于预定义值 T 的约束。

为此，您必须使用门格尔定理的一个版本来获取此处介绍的有界长度路径： http : //www.math.elte.hu/~lovasz/scans/mengerian.pdf