如何找到图中的所有顶点不相交的路径? [英] How to find all vertex-disjoint paths in a graph?

问题描述

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

Suppose there are 3 target nodes in a graph.

不相交的顶点路径意味着该路径中除了结束节点之外没有其他相同的节点.

A vertex-disjoint path means there is not any same node except the end nodes during the path.

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

For any one single node, say node i, how to find all vertex-disjoint paths from node i to the three target nodes?

推荐答案

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

You can solve this problem by reducing it to a max-flow problem in an appropriately-constructed graph. The idea is as follows:

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的最大流量.流的值是节点不相交路径的数量.

1. Split each node v in the graph into to nodes: v_in and v_out.
2. For each node v, add an edge of capacity one from v_in to v_out.
3. Replace each other edge (u, v) in the graph with an edge from u_out to v_in of capacity 1.
4. Add in a new dedicated destination node t.
5. For each of the target nodes v, add an edge from v_in to t with capacity 1.
6. Find a max-flow from s_out to t. The value of the flow is the number of node-disjoint paths.

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

The idea behind this construction is as follows. Any flow path from the start node s to the destination node t must have capacity one, since all edges have capacity one. Since all capacities are integral, there exists an integral max-flow. No two flow paths can pass through the same intermediary node, because in passing through a node in the graph the flow path must cross the edge from v_in to v_out, and the capacity here has been restricted to one. Additionally, this flow path must arrive at t by ending at one of the three special nodes you've identified, then following the edge from that node to t. Thus each flow path represents a node-disjoint path from the source node s to one of the three destination nodes. Accordingly, computing a max-flow here corresponds to finding the maximum number of node-disjoint paths you can take from s to any of the three destinations.

希望这会有所帮助！

这篇关于如何找到图中的所有顶点不相交的路径?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！