假设图中有 3 个目标节点。
顶点不相交路径意味着路径中除了末端节点之外没有任何相同的节点。
对于任意一个节点，比如节点 i，如何找到从节点 i 到三个目标节点的所有顶点不相交路径？
您可以通过在适当构造的图中将其简化为最大流问题来解决此问题。想法如下：
- Split each node v in the graph into to nodes: vin and vout.
- For each node v, add an edge of capacity one from vin to vout.
- Replace each other edge (u, v) in the graph with an edge from uout to vin of capacity 1.
- 添加新的专用目标节点 t。
- For each of the target nodes v, add an edge from vin to t with capacity 1.
- Find a max-flow from sout to t. The value of the flow is the number of node-disjoint paths.
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 vin to vout, 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.
希望这可以帮助！
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
