一个可行流是最大流的充分必要条件是( )
发布网友
发布时间：2022-04-24 09:49
共3个回答
热心网友
时间：2022-06-18 16:55
可行流是最大流的充分必要条件是无增广链。
从可行流和无增广链关系来看，就可以知道一种寻求最大流的方法：从一个可行流开始，寻求关于这个可行流的可增广链，若存在，则可以经过调整，得到一个新的可行流，其流量比原来的可行流要大，重复这个过程，直到不存在关于该流的可增广链时就得到了最大流。
v这种算法由Ford 和 Fulkerson于1956年提出，故又称 Ford-Fulkerson标号法。
扩展资料
对一个网络的某些点指定为发点，规定出提供能力；某些点指定为收点，规定出接收能力。
若一个流对每一发点满足总流出量与总流入量之差不大于提供能力，对每一收点满足总流入量与总流出量之差不小于接收能力，则称这个流为可行流。
可行流存在的充分必要条件：对所有顶点子集s都满足:由s到s的弧的总容量，不小于s中的收点总接收能力与s中的发点的总提供能力之差。
这个定理在图论中有许多应用。
热心网友
时间：2022-06-18 16:55
热心网友
时间：2022-06-18 16:56
