用独立通路法确定矿井通风网络的极值流

确定矿井通风网络极值流的常用算法有Ford-Fulkcrson法、Edmonds-Karp法和Dinic法。所谓独立通路就是采用深度优先搜索法在找通路的过程中，后面的通路至少要含有一条前面的通路所不含有的分支。独立通路法确定网络的极值流，就是利用找独立通路的思想来找增广路，找增广路时每次至少有一个分支达到饱和。从网络的源点开始进行寻边，找分支的可增广量为量大的出边，将该出边的末节点作为新的寻边始节点，继续找可增广量最大的出边，该搜索过程一直到所寻找的分支的末节点为网络的汇点为止，一条增广路即一条通路确定完毕，将该通路中分支的最小增广量作为通路的增广量对通路的各分支进行增广。增广后至少有一条分支达到饱和，删除饱和分支，用导出的网络继续找新的增广路并增广。

Determination of mine ventilation network max-flow based on independent paths

The common methods to determine extremal flow of mine ventilation network are Ford-Fulkerson algorithm, Edmonds-Karp algorithm and Dinic algorithm. So-called independent path is that in the process of finding paths by depth first search algorithm, posterior paths at least include one branch not including in anterior paths. Determining extremal flow by using independent paths method, is to find augmented paths by using the idea of finding independent paths, and at least one branch will reach saturated state every time while searching augmented paths. Finding branches are started on from the source nodes, find ex-branch whose augmented quantity is max, change the end node of the ex-branch to starting nodes and then go on finding branches, to find an ex-branch whose augmented quantity is max, the finding process will end until the end node of found branch is the sink node of the network, then an augmented path, namely a path is determined, the minimum augmented quantity of branch in the path is the augmented quantity of the path, using the value to augment every branch in the path. After augmentation, at least one branch is in saturation, deleting saturated branches, using the educed network to find new augmented branches and continue the augmentation process.