Жадібний метод розв’язання комбінаторної задачі знаходження максимального потоку в мережі

Abstract

У статті розглядається комбінаторна задача знаходження максимального потоку в мережі, яка зводиться до задачі евклідової комбінаторної задачі на розміщеннях. Запропоновано наближений алгоритм для її розв’язання, визначена поліноміальна оцінка його складності.

The combinatorial problem of finding of the maximal flow in a network is considered in the paper. This problem is a Euclidean combinatorial problem on arrangements. The approximate algorithm for solution of this problem is proposed. The polynomial estimation of complexity of this algorithm found.