Поток В Сети

- функция, сопоставляющая дугам данной сети (ориентированного графа) нек-рые числа. Каждое число интерпретируется как интенсивность потока нек-рого груза по данной дуге. П. В с. Являются удобной моделью при исследовании ряда проблем в транснорте, связи и др. Областях, связанных с движением грузов, информации и т. Д. Многие задачи о потоках являются задачами линейного программирования и могут решаться общими методами этой теории. Однако в большинстве случаев задачи о потоках допускают эффективное решение методами теории графов. Пусть каждой дуге ( х, у).сети 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. В. Б. Алексеев.