如何在图中找到所有顶点不相交的路径？

Question

假设图中有3个目标节点.

顶点不相交的路径意味着在路径期间除了端节点之外没有任何相同的节点.

对于任何一个节点,比如节点i,如何找到从节点i到三个目标节点的所有顶点不相交路径？

Answer 1

您可以通过在适当构造的图形中将其减少到最大流量问题来解决此问题.这个想法如下:

1. 将图中的每个节点v拆分为节点:v _in和v _out.
2. 对于每个节点v,从v _in到v _out添加容量1的边缘.
3. 将图中的每个边缘(u,v)替换为u _out到v _{in in} capacity 1.
4. 添加新的专用目标节点t.
5. 对于每个目标节点v,从v _in到t 添加一个容量为1的边.
6. 找出从s _out到t 的最大流量.流的值是节点不相交路径的数量.

这种结构背后的想法如下.从起始节点s到目标节点t的任何流路径必须具有容量1,因为所有边都具有容量1.由于所有容量都是积分的,因此存在积分最大流量.没有两个流路径可以通过相同的中间节点,因为在通过图中的节点时,流路径必须越过v _in到v _out的边缘,并且此处的容量被限制为1.此外,此流路径必须通过在您已识别的三个特殊节点之一处结束,然后在该节点的边缘之后到达t来到达t.因此,每个流路径表示从源节点s到三个目的节点之一的节点不相交路径.因此,这里计算最大流量对应于找到可以从s到三个目的地中的任何一个的节点不相交路径的最大数量.

希望这可以帮助!