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

Question

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

顶点不相交的路径表示路径中除了结束节点外没有其他相同的节点。

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

Answer 1

您可以通过在适当构造的图中将其简化为最大流量问题来解决此问题。这个想法如下：

1. 将图中的每个节点v拆分为节点：v _in和v _out。
2. 对于每个节点v，从v _in到v _out添加容量为1的边。
3. 用容量为1的u _out到v _in的边替换图形中的其他边（u，v）。
4. 添加新的专用目标节点t。
5. 对于每个目标节点v，将v _in的边添加到容量为1的t中。
6. 找到从s _out到t的最大流量。流的值为节点不相交路径的数量。

此构造背后的思想如下。从起始节点s到目的节点t的任何流路都必须具有容量1，因为所有边缘的容量都为1。由于所有容量都是不可分割的，因此存在不可分割的最大流量。没有两个流动路径可以通过同一中间节点，因为在通过图中的一个节点时，流动路径必须从v _in到v _out穿过边缘，并且此处的容量受到限制到一个。此外，该流路必须到达t时要在已确定的三个特殊节点之一处结束，然后沿着该节点的边缘到达t。因此，每个流路径表示从源节点s到三个目的节点之一的节点不相交的路径。因此，此处计算最大流量对应于找到可以从s到三个目的地中的任何一个的节点不相交路径的最大数量。

希望这会有所帮助！

Answer 2

我同意以下观点：“ @ Dougal，非常感谢。是的，您可能会先采用深度优先然后删除它们的想法来解决此问题。实际上，这3个目标节点没有太多业务节点x和y与z相同，因此它将重复查找z路径的过程。– datcn 2012年3月25日，8：20”，“因此，此处计算最大流量对应于找到从s到三个目的地中任何一个的最大节点不相交路径数。”我认为在线服务器和手机可以作为路由节点。

[摘自《中国的失败者》，郝成，1985年出生，仍在等待宣布于2020年5月21日在武汉市伟业大厦举行的劳动争议仲裁。