Поток В Сети

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