网络分析中应用最大流最小割的初值  

Application of Initial Value for Max-flow Min-cut in Network Analysis

作　　者：徐光联[1] 邢永中[1] 

机构地区：[1]鹤壁职业技术学院,河南鹤壁458030

出　　处：《通信技术》2008年第9期130-133,共4页Communications Technology

摘　　要：在网络通信分布系统中进行网络分析时,应用最大流最小割定理,它的初始值设定是影响计算结果正确与否的关键之一。以并行任务分配问题映射到网络图为例,介绍了任务交互图到网络图的映射方法,讨论了连接源点和连接汇点的弧的方向和初值设定、无向边设为双向弧的容量设定、最大流最小割的结果不唯一、初始可行流对求最大流的结果的影响和初始流与平衡条件的关系等问题。The theorem of max-flow min-cut can be applied to network analysis in the network communication distribution system, and its initial value is the key for computing results. By taking the mapping of the distribution of parallel task to network map as an example, this paper proposes mapping method for the task interactive map to the network map, discusses the direction and initial-value setting of the are connecting the source or the sink, the edge to two-way are and the capacity of initial value, the not-the - only result for maximum flow minimum-cut, the initial flow for seeking the greatest possible flow and its impact on the results, the relations of the initial flow and balance conditions, including other related issues.

关 键 词：最大流最小割 通信成本 源点和汇点 

分 类 号：TP301.4[自动化与计算机技术—计算机系统结构]