Знаходження максимального потоку в мережі

Abstract

Мережа задається орграфом, який задано матрицею суміжності та матрицею пропускних здатностей ребер, причому мережа має одне джерело і один стік. Потрібно обчислити максимальну пропускну здатність самої мережі. Аналітично, задачу зводимо до задачі лінійного програмування. Знаходимо відповідну цільову функцію та відповідні умови, а саме: потік через кожну дугу не перевищує її пропускної здатності та для кожної вершини, відмінної від джерела та стоку, повний потік, який входить в неї, дорівнює повному потоку, який з неї виходитьThe network is defined by a digraph, which is given by the adjacency matrix and the matrix of bandwidth of the edges, and the network has one source and one drain. You need to calculate the maximum bandwidth of the network itself. Analytically, we reduce the problem to the problem of linear programming. Find the appropriate objective function and the appropriate conditions, namely: the flow through each arc does not exceed its capacity and for each vertex other than the source and runoff, the total flow that enters it is equal to the total flow that comes out of it