图中n条顶点不相交的最小总顶点数A-B路径的存在性判定与求解算法问询

嘿，这个问题挺有意思的——咱们先把问题再明确下：给定图$G$和两个顶点$A,B$，要找$n$条顶点不相交（除了$A,B$之外，路径之间没有其他公共顶点）的$A-B$路径$P_1,...,P_n$，目标是让这些路径覆盖的总顶点数$# V(\cup_{i=1}^n P_i)$尽可能小。下面咱们分别聊聊你关心的两个问题：

一、存在性判定 #

关于$n$条符合要求的路径是否存在，经典的Menger定理就是核心判定依据：

$A$和$B$之间存在$n$条顶点不相交路径的充要条件是，任何能分离$A$和$B$的顶点割集（即去掉该集合中的所有顶点后，$A$和$B$不再连通）的大小都至少为$n$。

换句话说，只要没有规模小于$n$的顶点集能切断$A$到$B$的所有通路，那就一定存在$n$条满足约束的顶点不相交路径。

二、求解算法 #

首先得给你点个赞：你发现“每次找当前剩余图里的最短路径，去掉中间顶点再重复”的贪心策略行不通，这个观察非常准确——确实存在不少反例，比如某些图中，优先选一条极短路径会把后续路径逼得绕远路，最终总顶点数反而比最优解大很多。

那正确的求解思路可以从以下方向入手：

• 最小费用流建模：这是最通用的方法，把问题转化为标准的流问题来解决：
  1. 对图中除$A,B$外的每个顶点$v$，拆分为两个顶点$v_{in}$和$v_{out}$，并在两者之间连一条容量为1、费用为1的边——这一步是为了保证每个中间顶点只能被一条路径使用（满足顶点不相交的约束）。
  2. 对原图中的每条边$(u,v)$，在拆点后的图中连一条从$u_{out}$到$v_{in}$的边，容量为1、费用为0。
  3. 将$A$作为源点，$B$作为汇点，求解流量为$n$的最小费用流。这个流对应的路径就是$n$条顶点不相交的$A-B$路径，且总顶点数最小（总费用对应路径覆盖的中间顶点数，加上$A,B$各算一次，即可得到总顶点数）。
• 扩展Suurballe算法：Suurballe算法原本用于寻找两条顶点不相交的最短路径（总长度最小），你可以迭代使用类似思路：每次找到一条路径后，调整图的边权以避免重复使用顶点，再寻找下一条路径。不过这个方法需要仔细处理顶点不相交的约束，实现起来比最小费用流建模更繁琐，但核心逻辑是一致的。

备注：内容来源于stack exchange，提问作者Mr. Brown