什么是节点不相交路径? [英] What is node-disjoint paths?

问题描述

我需要解释什么是节点不相交的路径?以及如何确定有向图中两个节点Source和Sink之间的最大不相交路径数.谁能用图形解释.

I need explanation about what exactly node-disjoint paths? and How to determine maximum number of node-disjoint path between two nodes Source(s) and Sink(t) in a directed graph. Can anyone explain with graphically.

推荐答案

路径是顶点序列:s, v_1, .., v_m, t.如果任何有效的i和j的v_i != u_j，则两个路径s, v_1, .., v_m, t和s, u_1, ..., u_k, t称为节点不相交.

A path is sequence of vertices: s, v_1, .., v_m, t. Two paths s, v_1, .., v_m, t and s, u_1, ..., u_k, t are called node-disjoint if v_i != u_j for any valid i and j.

我们可以通过将每个顶点(源和目标除外)分成两个，从第一个副本到第二个副本添加一条边，将所有在此顶点结束到第一个副本，并从第二个副本的所有传出边.之后，答案就是该图中的最大流量(所有边都应具有单位容量).

We can reduce this problem to finding the maximum number of edge-disjoint paths by splitting each vertex (except for the source and the target) into two, adding an edge from the first copy to the second copy, redirecting all edges that end in this vertex to the first copy and all outgoing edges from the second copy. After that, the answer is the maximum flow in this graph (all edges should have a unit capacity).

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