Задача о максимальном потоке на сети с несколькими источниками и стоками

Abstract

Приводится точный, полный алгоритм решения прикладной задачи о формировании максимального потока на сети с несколькими источниками и стоками, основанный на доказательстве теоремы Форда – Фалкерсона. На первом этапе предложенной процедуры осуществляется расширение сети за счет виртуальных дополнительных вершин – субисточника и гиперстока; на втором формируется насыщенный поток; на третьем осуществляется перераспределение потока с учетом незадействованных пропускных способностей дуг, не включенных в насыщенные потоки. На примере конкретной сети с большим количеством вершин аналитически и графически проиллюстрирована эффективность предложенного алгоритма. Актуальность данной тематики обусловлена широким практическим применением теории сетей при проектировании нефте- и газопроводов, линий электропередач, железных и шоссейных дорог, компьютерных сетей, телекоммуникаций и пр.