最大流最小割理论在网络分析中的应用  

An Application of Max-Flow Min-Cut in Network Analysis

作　　者：廖薇 刘玲 LIAO Wei;LIU Ling(Science and Technology on Electronic Information Control Laboratory,Chengdu 610036,China)

机构地区：[1]电子信息控制重点实验室,成都610036

出　　处：《电子信息对抗技术》2021年第3期67-71,86,共6页Electronic Information Warfare Technology

摘　　要：分布式网络系统是分布式作战系统的基本组成部分,其数据的传输跟网络承载的最大流密切相关。网络最大流问题是经典的组合优化问题,随着网络规模的增加,组合算法的运行时间已难以适应大规模网络甚至无法收敛。分层网络是大规模网络的重要架构方式,为该类型网络最大流问题求解的复杂度,减少最大流计算时间,利用分层网络的结构优势结合最大流最小割理论对网络进行分析,得到分层网络能承载的最大流计算方法。该结论适用于层次结构分明的大数据网络,根据最小割对网络最大流进行快速估算,一方面可为数据传输提供支撑,另一方面可为网络对抗中的目标网络关键路径攻击等应用提供支撑。Distributed network system is the basic component of distributed combat system.Its date transmission is closely related to the maximum flow carried by the network.Network maximum flow problem is a classical combinatorial optimization problem.With the increase of network scale,the running time of combinatorial algorithm is difficult to adapt to large-scale network or even unable to converge.The layer network is an important architecture of large-scale network.In order to reduce the complexity of solving the maximum problem and the computing time,based on the structural advantage of layer network and the max-flow min-cut theory,the calculation formula is obtained.This conclusion is suit for the large layer network,and can quickly estimate the network flow.On the one hand,it can provide support for data transmission,on the other hand,can also provide support for target network critical path attack in network countermeasures.

关 键 词：最大流问题 最大流最小割 网络拓扑 分层网络 

分 类 号：TN915.02[电子电信—通信与信息系统]