Поток в сети

- функция, сопоставляющая дугам данной сети (ориентированного графа) нек-рые числа. Каждое число интерпретируется как интенсивность потока нек-рого груза по данной дуге. П. в с. являются удобной моделью при исследовании ряда проблем в транснорте, связи и др. областях, связанных с движением грузов, информации и т. д. Многие задачи о потоках являются задачами линейного программирования и могут решаться общими методами этой теории. Однако в большинстве случаев задачи о потоках допускают эффективное решение методами теории графов. Пусть каждой дуге (х, у).сети N приписано неотрицательное действительное число с (х, у) - пропускная способность дуги (х, у). Говорят, что поток f(x, у).является стационарным потоком величины vиз вершины rв вершину s, удовлетворяющим ограничениям пропускных способностей дуг, если [img: http://localhost:8080/file/041738-7.jpg] [img: http://localhost:8080/file/041738-8.jpg] для любой дуги (х, у), здесь [img: http://localhost:8080/file/041738-9.jpg] -поток, выходящий из, вершины x, а [img: http://localhost:8080/file/041738-10.jpg] - поток, входящий в вершину х. В задаче о максимальном потоке между двумя вершинами требуется построить стационарный поток из вершины rв вершину s, имеющий максимально возможную величину v. Для решения этой задачи существуют достаточно эффективные алгоритмы. Пусть X - подмножество вершин сети N такое, что [img: http://localhost:8080/file/041738-11.jpg]. Тогда множество дуг (х, у).таких, что [img: http://localhost:8080/file/041738-12.jpg], [img: http://localhost:8080/file/041738-13.jpg], наз. разрезом. Пропускной способностью разреза наз. величина [img: http://localhost:8080/file/041738-14.jpg]. Справедлива следующая теорема о максимальном потоке и минимальном разрезе: максимальная величина потока равна минимальной пропускной способности разрезов. В приложениях часто используется теорема о целочисленности: если пропускная способность дуг целочисленна, то существует целочисленный максимальный (стационарный) поток. К задаче о максимальном потоке между двумя вершинами сводится ряд задач: задача о максимальном П. в с. с несколькими источниками и стоками; задача о максимальном П. в с., имеющей неотрицательные ограничения на потоки по дугам как сверху, так и снизу; задача о максимальном потоке в неориентированных и смешанных сетях; задача о максимальном потоке в сети с пропускными способностями дуг и вершин и др. Теорема о максимальном потоке и минимальном разрезе выявила общую основу ряда результатов, полученных ранее в теории графов и комбинаторике. Оказалось, что как следствия этой теоремы могут быть получены: теорема о максимальном паросочетании в графе двудольном, теорема о различных представителях, теоремы о k-связности графов (см. Графа связность), теорема о покрытии частично упорядоченного множества наименьшим числом цепей и др. Сведение различных задач к задаче о максимальном потоке является важным методом теории графов и комбинаторики. В ряде задач о П. в с. каждой дуге (х, у).сопоставляется число а(х, у) - стоимость перевозки единицы груза по дуге (х, у).и требуется найти поток, удовлетворяющий определенным ограничениям и минимизирующий общую стоимость потока. Задача о потоке минимальной стоимости состоит в нахождении стационарного потока из вершины rв вершину s, удовлетворяющего ограничениям пропускных способностей дуг, причем такого, что величина его равна заданному числу v, а стоимость минимальна. В транспортной задаче сеть является двудольным графом. Вершины одной доли Sl,..., Sm интерпретируются как пункты отправления нек-рого груза, вершины другой T1,..., Т n - как пункты назначения. Каждый пункт отправления Si имеет определенное предложение bi, и каждый пункт назначения Tj имеет определенный спрос cj. Известна стоимость а ij перевозки единицы груза из Si в Т j. Задача состоит в отыскании потока минимальной стоимости, удовлетворяющего спрос во всех пунктах назначения. Рассматриваются также многопродуктовые потоки и потоки, изменяющиеся во времени.