关键词: 最大流, 最小截, 弧容忍度, 增广圈, 增广链

Abstract:

For the problem that whether the change of channel’s bandwidth will influence the maximum communication ability in the communication network,the arc tolerance problem of the maximum flow is proposed. First we study the arc tolerance of the maximum flow in combination with the nature of the maximum flow and minimum cut.Secondly we propose an arc tolerance polynomial time algorithm with consideration of arcs in and out of the minimum cut. Finally the proposed algorithm is analyzed and compared.Numerical example shows that the algorithm has low complexity and is easy to operate.

Key words: maximum flow;minimum cut;arc tolerance;augmenting cycle;augmenting chain