Проблема сетевого потока - Network flow problem

В комбинаторная оптимизация, проблемы с сетевым потоком представляют собой класс вычислительных задач, в которых на входе проточная сеть (граф с числовыми емкостями на ребрах), и цель состоит в том, чтобы построить поток, числовые значения на каждом ребре, которые соответствуют ограничениям пропускной способности и которые имеют входящий поток, равный исходящему потоку во всех вершинах, кроме определенных назначенных терминалов.

Конкретные типы проблем сетевого потока включают:

В проблема максимального потока, в котором цель состоит в том, чтобы максимизировать общий объем потока из терминалов источника в терминалы приемника
В проблема минимальных затрат, в котором края имеют стоимость, а также пропускную способность, и цель состоит в том, чтобы достичь заданного количества потока (или максимального потока), который имеет минимально возможные затраты
В проблема многопродуктового потока, в котором необходимо построить несколько потоков для разных товаров, общие суммы потоков которых вместе учитывают мощности
Нигде-нулевой поток, тип потока, изучаемый в комбинаторике, в котором объемы потока ограничены конечным набором ненулевых значений

В теорема о максимальном потоке и минимальном отсечении приравнивает значение максимального расхода к значению минимальный разрез, раздел вершин потоковой сети, который минимизирует общую пропускную способность ребер, пересекающих одну сторону раздела в другую. Приближенные теоремы о максимальном расходе и минимальном сокращении распространить этот результат на проблемы с потоками нескольких товаров. В Дерево Гомори – Ху ненаправленной потоковой сети обеспечивает краткое представление всех минимальных разрезов между различными парами конечных вершин.

Алгоритмы для построения потоков включают

Алгоритм диника, сильно полиномиальный алгоритм максимального потока
В Алгоритм Эдмондса – Карпа, более быстрый сильно полиномиальный алгоритм для максимального потока
В Алгоритм Форда – Фулкерсона, жадный алгоритм для максимального потока, который, вообще говоря, не является сильно полиномиальным
В сетевой симплексный алгоритм, метод, основанный на линейном программировании, но специализированный для сетевого потока.
В нестандартный алгоритм для потока с минимальными затратами
В push – изменить алгоритм максимального потока, один из наиболее эффективных известных методов достижения максимального потока

Этот статья включает список связанных элементов с одинаковыми именами (или похожими именами).
Если внутренняя ссылка неправильно привел вас сюда, вы можете изменить ссылку, чтобы она указывала непосредственно на предполагаемую статью.