Математическая энциклопедия - поток в сети

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

Пусть каждой дуге ( х, у).сети N приписано неотрицательное действительное число с ( х, у) - пропускная способность дуги ( х, у). Говорят, что поток f(x, у).является стационарным потоком величины vиз вершины rв вершину s, удовлетворяющим ограничениям пропускных способностей дуг, если

для любой дуги ( х, у), здесь -поток, выходящий из, вершины x, а поток, входящий в вершину х.

В задаче о максимальном потоке между двумя вершинами требуется построить стационарный поток из вершины rв вершину s, имеющий максимально возможную величину v. Для решения этой задачи существуют достаточно эффективные алгоритмы. Пусть X - подмножество вершин сети N такое, что

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

К задаче о максимальном потоке между двумя вершинами сводится ряд задач: задача о максимальном П. в с. с несколькими источниками и стоками; задача о максимальном П. в с., имеющей неотрицательные ограничения на потоки по дугам как сверху, так и снизу; задача о максимальном потоке в неориентированных и смешанных сетях; задача о максимальном потоке в сети с пропускными способностями дуг и вершин и др.

Теорема о максимальном потоке и минимальном разрезе выявила общую основу ряда результатов, полученных ранее в теории графов и комбинаторике. Оказалось, что как следствия этой теоремы могут быть получены: теорема о максимальном паросочетании в графе двудольном, теорема о различных представителях, теоремы о k-связности графов (см. Графа связность), теорема о покрытии частично упорядоченного множества наименьшим числом цепей и др. Сведение различных задач к задаче о максимальном потоке является важным методом теории графов и комбинаторики.

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

В транспортной задаче сеть является двудольным графом. Вершины одной доли Sl ,... , Sm интерпретируются как пункты отправления нек-рого груза, вершины другой T1, ... , Т n - как пункты назначения. Каждый пункт отправления Si имеет определенное предложение bi, и каждый пункт назначения Tj имеет определенный спрос cj. Известна стоимость а ij перевозки единицы груза из Si в Т j. Задача состоит в отыскании потока минимальной стоимости, удовлетворяющего спрос во всех пунктах назначения.

Рассматриваются также многопродуктовые потоки и потоки, изменяющиеся во времени.

Лит.:[1] Форд Л. Р., Фалкерсон Д. Р., Потоки в сетях, пер. с англ., М., 1966. В. Б. Алексеев.

Математическая энциклопедия. — М.: Советская энциклопедия

И. М. Виноградов

1977—1985