Описание тега network-flow

Описание тега Вопросы с тегом

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

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