Потоки в сетях Понятие сети. Пример сети. Потоки в сетях. Разрезы. Теорема Форда-Фолкерсона о максимальной величине потока. Алгоритм - davaiknam.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Інформаційно-аналітичні системи обробки даних И. В. Максимей, Е. 1 172.1kb.
Ревизия: 1 История изменений 1 131.47kb.
Основные сведения 1 163.75kb.
Глобальные сети, Интернет, ip-адресация 1 183.81kb.
Вопросы к экзамену по курсу Распределенные Вычислительные Сети 1 17.3kb.
Ответ. В сетях с разделяемой средой работа выполняется по следующему... 1 76.92kb.
«Социальные сети в образовательном процессе» Орлова Елена Альбертовна 1 42.23kb.
Принцип коммутации пакетов в информационно-вычислительных сетях 1 36.12kb.
Вопросы к главе 5 «Потоки. Гонка данных и другие проблемы» Что означает... 1 57.34kb.
Режимы заземления нейтрали в сетях 6-35 кВ и организация релейной... 1 206.43kb.
Закона «Об информации информатизации и защите информации» 1 161.42kb.
Лабораторная работа №3 «Практическое знакомство с потоками и синхронизацией... 1 41.69kb.
Направления изучения представлений о справедливости 1 202.17kb.

Потоки в сетях Понятие сети. Пример сети. Потоки в сетях. Разрезы. Теорема Форда-Фолкерсона - страница №1/1

Потоки в сетях

Понятие сети. Пример сети. Потоки в сетях. Разрезы. Теорема Форда-Фолкерсона о максимальной величине потока. Алгоритм нахождения максимального потока
Задача о максимальном потоке - одна из основных проблем в теории вычислительных систем.

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

В задаче о максимальном потоке одна из вершин графа назначается истоком - точкой, в которой все объекты начинают свой путь, а другая - стоком - точкой, в которую они все направляются. Пропускная способность каждого ребра ограничена.

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

Рассмотрим транспортную сеть, в которой выделены пункты 0 (вход, источник) и n (выход, сток) и каждой дуге (отрезку), связывающей пункты i и j, сопоставлено число dij>0, называемое пропускной способностью дуги. Величина пропускной способности характеризует максимальное допустимое количество вещества (воды, газа, самолетов, вагонов и т.п.), которое может проходить по соответствующей дуге в единицу времени.

Количество вещества, проходящего по дуге от i до j, будем называть потоком по дуге (i, j) и обозначать через Xij .

Очевидно, что 0≤Xij≤dij для всех i, j/

Если учесть, что все вещество, вошедшее в промежуточный пункт сети, должно полностью выйти из него, получаем .

Из естественного требования равенства потоков на входе и на выходе имеем /

Величину Z называем величиной потока в сети и ставим задачу максимизации Z.

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

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



Теорема Фалкерсона-Форда: максимальный поток через сеть равен минимальному потоку через разрез.

Алгоритм Фалкерсона-Форда

      1. Обнуляем все потоки. Остаточная сеть изначально совпадает с исходной сетью.

      2. В остаточной сети находим любой путь из источника в сток. Если такого пути нет, останавливаемся.

      3. Пускаем через найденный путь (он называется увеличивающим путём или увеличивающей цепью) максимально возможный поток:

          1. На найденном пути в остаточной сети ищем ребро с минимальной пропускной способностью cmin.

          2. Для каждого ребра на найденном пути увеличиваем поток на cmin, а в противоположном ему - уменьшаем на cmin.

          3. Модифицируем остаточную сеть. Для всех рёбер на найденном пути, а также для противоположных им рёбер, вычисляем новую пропускную способность. Если она стала ненулевой, добавляем ребро к остаточной сети, а если обнулилась, стираем его.

      4. Возвращаемся на шаг 2.




  1. Подбирается поток с ненулевой частотой. В нашем случае в скобках указан поток. zij ≤dij

  2. Исходя из заданной сети N строим новую сеть N' следующим образом: любая дуга, из которой zl=0 (старый поток) остается в новой сети с той же пропускной способностью, если же zl≠0, эта дуга заменяется двумя дугами – одна в том же направлении с пропускной способностью Ul-xl и обратная к xl.




  1. Если в новой сети можно найти ненулевой поток, то добавляем его к исходному, и получаем поток больше исходного до тех пор, пока на шаге три для очередной сети мы не сможем найти ненулевой поток. F’=4+1=5


В новой сети N'' нет ненулевого потока, поэтому F=5.




Лучше никогда, чем поздно. Журнал «Панч», 1867 г.
ещё >>