网络最大流部分割矩阵算法  

Partial Cut Set Algorithm for Maximum-flow of Networks

作　　者：毛华[1] 毛晓亮[1] 李斌[1] 

机构地区：[1]河北大学数学与计算机学院,保定071002

出　　处：《计算机科学》2011年第12期229-231,246,共4页Computer Science

基　　金：保定市科学技术研究项目(11ZG005[P])资助

摘　　要：网络最大流问题是图论研究中一个经典的模块。首先,利用粗糙集属性约简的差别矩阵算法思想,定义网络的一个部分割容量矩阵。其次,通过集合的交和并运算,找出网络的所有割集,从而得到最小容量割集。之后,在最大流最小割定理的基础上,得到网络的最大流。Network maximum-flow problem is a classical module in graph theory. First, based on the＇rough set attribute reduction algorithm of discernibility matrix, it defines a partial cut set matrix. Afterwards, it finds out all the cut by meet and join operations for sets. Furthermore, the minimum cut is yielded out. At last, it gets the maximum flow of the network with the assistance of the theorem of maximum flow minimum cut.

关 键 词：网络最大流 割集 部分割 最小割 

分 类 号：O224[理学—运筹学与控制论]