摘要
ransport network in the paper is defined as follows: (1) Connected and directed network without self loop;(2) There is only one source vertex with zero in degree; (3) There is only one sink vertex with zero out degree;(4) The capacity of every arc is non negative integer Blocking flow is a kind of flow commonly happened in a transport network . Its formation is due to the existance of a blocking cutset in the network. In this paper the fundamental concepts and theorems of the blocking flow and the blocking cutset are introduced and a linear programming model for determining the blocking cutset in a network is set up. In order to solve the problem by graph theoretical approach a method called 'two way flow augmenting algorithm' is developed. With this method an iterative procedure of forward and backward flow augmenting process is used to determine whether a given cutset is a blocking one.
堵塞流动是运输网络＊＊中常见的一类流动，它的存在是因为网络中存在堵塞截面。本文介绍了网络堵塞流和堵塞截面的基本概念和定理，并建立了确定堵塞截面的线性规划模型。为了解决网络规模变大时求解线性规划问题所带来的计算效率问题，本文提出了一种图论算法——双向增流算法。该算法是利用正反两向增流的迭代程序来实现寻找网络堵塞截面的方法。
