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

Question

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

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

- wzb5210

---

只是出于好奇，这个问题的背景是什么？ - tskuzzy

你对“最大无交路径数”有什么实际意义？是指长度最长的路径，还是节点最多的路径，或者是不同路径的总数？ - Timothy

@Skyler，我认为他的意思是最大无关路径数。- Ido.Co 5分钟前 - Ido.Co

Answer 1

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

现在，您可以在此图上解决最小费用流问题，以找到具有路径长度最小和的任意数量的不相交路径。为此，将每条边的流量容量分配为1，然后搜索从s到t的流量等于所需路径数的最小费用流。

要找到最大路径数，请对二进制搜索的每个步骤应用最小费用流程，从某些初始路径数开始确定，这可以通过以下一种或多种程序之一确定：

1. 如果您预期最大路径数很大，则解决此图的最大流问题。
2. 如果您预期最大路径数较小，则使用单侧二进制搜索（也使用每个步骤的最小费用流程）。

- Evgeny Kluev

Answer 2

由于您只对不相交路径的数量感兴趣，因此可以使用Menger定理（证明请参见此处），其规定如下：

设G为有限无向图，x和y为两个非相邻顶点。则该定理指出：x和y的最小顶点割大小（将x和y分离所需移除的最少顶点数）等于从x到y的最大顶点独立路径数。

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

为此，您需要使用一种长度受限制的Menger定理版本，该版本在此处介绍：http://www.math.elte.hu/~lovasz/scans/mengerian.pdf

- Ido.Co