可行流_图论的概念 - 线报百科mbji.cn

可行流

图论的概念

可行流(feasible flow)图论的一个重要概念。它是满足一定条件的网络流。

对一个网络的某些点指定为发点，规定出提供能力；某些点指定为收点，规定出接收能力。

若一个流对每一发点满足总流出量与总流入量之差不大于提供能力，对每一收点满足总流入量与总流出量之差不小于接收能力，则称这个流为可行流。

可行流存在的充分必要条件：对所有顶点子集s都满足:由s到s的弧的总容量，不小于s中的收点总接收能力与s中的发点的总提供能力之差。

这个定理在图论中有许多应用。

参考资料

最新修订时间：2021-11-17 13:55

条目作者

概述

参考资料