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

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