Поиск максимальных потоков в сетях
Дипломная работа - Математика и статистика
Другие дипломы по предмету Математика и статистика
тированных. Поток в петле не влияет на распределение потока между вершинами. Рассмотрим сеть G = (V, E), |V | = n, |E| = m. Пускай каждой дуге еj E поставлено в соответствие неотрицательное действительное число сj , которое назовём пропускной способностью дуги еj. Обозначим через vi > V множество дуг, выходящих из вершины vi, через V > vi множество дуг, заходящих в вершину vi.
Потоком в сети G из вершины vs в вершину vt величины w называется неотрицательная, определенная на дугах еj, функция ?: Е > R+ {0}, такая, что
= (1)
?(еj) ? cj, j = 1, …, m.
Вершина vs называется источником, вершина vt стоком, а остальные вершины промежуточными узлами. Число Q(vi) = - называется чистым потоком из вершины vi относительно ?. Число ?(е) называется потоком по дуге е. Если “реальный” поток по дуге отрицательный, то его можно сделать положительным, выбрав соответствующую ориентацию дуги e. Систему уравнений (1) можно переписать в векторном виде:
ВФ = l,(2)
где В матрица инцидентной размерности n m, Ф = (?(e1) … ?(em))T, l = (0..0w0..0 w0..0)T. Поскольку ранг матрицы инциденций равен n 1, то система уравнений (1) избыточна: . Также можно сказать, что поток ? из vs в vt величины w есть поток величины -w из vt в vs.
Пример
Рис. 2.1. Поток величины 3
Сеть, изображённая на рис. 2.1, состоит из пяти узлов и восьми дуг. Будем рассматривать поток от v1 до v5. Каждой дуге приписаны два числа: первое величина потока по дуге, второе пропускная способность дуги. Величина этого потока равна 3. Действительно,
Q(v1) = 5 - 2 = 3,
Q(v2) = 7 (5 + 2) = 0,
Q(v3) = 4 0 +2 + 2 = 0,(3)
Q(v4) = 4 + 4 = 0,
Q(v5) = 4 + 0 7 = 3.
Систему уравнений (3) можно записать в векторном виде ВФ = l (2):
, , .
2.2. Задача о максимальном потоке
На практике часто возникает проблема определения максимальной проводимости некоторой реальной сети: сети транспортной, сети ЭВМ, других. Иногда нужно определить самый дешёвый поток и т.д. Все эти и многие другие задачи решаются с помощью алгоритмов, которые работают на сетях. Так, алгоритм о максимальном потоке ищет максимально возможную пропускную способность сети, алгоритм минимальной стоимости самый дешёвый поток. В данном разделе будем рассматривать задачу о максимальном потоке.
Задача заключается в нахождении такого множества потоков по дугам, чтобы величина Q(vs) была максимальной.
Разрез S отделяет vs от vt, если вершины vs, vt принадлежат разным сторонам разреза: vs Vs, vt Vt, V = Vs Vt. Пропускной способностью с(S) разреза S называется сумма пропускных способностей дуг разреза, которые начинаются в Vs и заканчивается в Vt:
с(S) = .
2.3. Алгоритм размещения пометок для задачи о максимальном потоке
Алгоритм размещения пометок основан на следующей теореме.
Теорема 1.Теорема про максимальный поток и минимальный разрез. Для произвольной сети максимальная величина потока из vs в vt равняется минимальной пропускной способности разреза, который отделяет vs от vt.
Доказательство
Покажем, что величина w произвольного потока ? не превышает пропускной способности разреза (Vs,Vt), который отделяет vs от vt. Поскольку функция ? поток, то она удовлетворяет уравнению (1) сохранении потока:
- = w,
- = 0, v vs, v t,(2)
- = -w.
Сложим те уравнения из (2), которые соответствуют вершинам из Vs. Учитывая, что vs Vs, vt Vt, получаем:
w = - .
Всё множество вершин распадается на две стороны: V = Vs Vt. Получаем
w = - =
= + - - =
= - ? ? = c(Vs, Vt).
Теперь нужно показать, что существуют некоторые поток ? и разрез (Vs, Vt), для которых величина потока равняется пропускной способности разреза. Как видно, все потоки от Vs до Vt ограничены и среди них можно выбрать максимальный поток ?. С её помощью определим разрез (Vs, Vt), для которого
= c(Vs, Vt), = 0.
Определим множество Vs рекуррентно:
1) vs Vs.
2) Если, vs Vs дуга e идёт из вершины vi в какую-либо вершину vj и ?(e) < c(e), то vj Vs.
3) Если vi Vs, дуга e идёт из вершины vr в вершину vi и ?(e), то vj Vs.
Шаг 1) построения множества Vs означает, что источник vs принадлежит построенной стороне разреза. Покажем, что сток тогда лежит на другой стороне разреза vt Vt = V/Vs. Допустим противоположное: пусть vt Vs. Тогда существует “неориентированная” цепь, которая идёт из источника vs в сток vt, такая, что для каждой дуги ei цепи с направлением, совпадающим с ориентацией “от источника к стоку” > 0.
Обозначим через l1 = min{c(ej) - c(ei)} все дуги ei цепи с направлением, совпадающим с ориентацией “от источника к стоку”, l2 = min{