Полная версия

Главная arrow Туризм arrow Основы функционирования систем сервиса

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Сети с заданными пропускными способностями узлов и связей.

Пусть в сети N= (К, R) заданы пропускные способности связей санузлов g;,j= 1,2,..., | к |. Необходимо найти максимальный поток между источником 5 и стоком /, при этом полный поток, входящий в узел Хр не должен превышать^ для всех j. Такая задача возникает, например, при отправке туристов в места отдыха при ограничениях мест в гостиницах на промежуточных пунктах.

Сеть с заданной пропускной способностью узлов

Рис. 3.12. Сеть с заданной пропускной способностью узлов

Рассмотрим соответствующий граф (рис. 3.12).

Для вычисления максимального потока с заданными ограничениями на пропускную способность узлов преобразуем сеть, изображенную на рис. 3.12, следующим образом [19]: каждому узлу Xj сети ./V поставим в соответствие два узла xj и xj сети N' и соединим их связью (Xj , xj)c пропускной способностью^. Все связи, входящие в вершину Xj, сделаем входящими в вершину xj , а исходящие — исходящими из вершины xj (рис. 3.13).

Модифицированная сеть с заданной пропускной способностью связей вместо узлов

Рис. 3.13. Модифицированная сеть с заданной пропускной способностью связей вместо узлов

Отметим также, что если минимальный разрез сети N' не содержит связи (ху+, x~j), то пропускные способности узлов в N излишни. Если минимальный разрез в N' содержит такие связи, то соответствующие им узлы в А^насыщены полученным максимальным потоком и ограничивают его.

Так как полный поток, входящий в узел ху+, протекает и по связи (xj, xj) с пропускной способностью gj, то максимальный поток в сети N с пропускными способностями связей и узлов равен максимальному потоку в сети N', имеющей только пропускные способности связей.

Максимальный поток между каждой парой вершин

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

Многополюсная сеть

Рис. 3.14. Многополюсная сеть

Поставленную задачу можно решить с помощью процедуры нахождения максимального потока к каждой паре узлов. Рассмотрим сеть на рис. 3.14. Используя метод Форда—Фалкерсона, вычислим потоки между всеми узлами и запишем их в виде матрицы:

Если пропускная способность каждой связи не зависит от направления движения потока по этой связи, то матрица будет симметричной и общее число задач о максимальном потоке будет равно п(п —1)/2, п — число узлов. Для рассматриваемого примера с 6 узлами это число равно 15 и соответствует числу элементов матрицы V, расположенных выше главной диагонали.

Алгоритм Гомери-Ху. Алгоритм является более эффективным, так как максимальный поток вычисляется п —1 раз [19, 35].

Рассмотрим неориентированную сеть N = (К, R) с п узлами и связями (i,j), i,j= 1,2,..., п, с пропускными способностями с^= с/7. Введем следующие обозначения: Vy — максимальный поток между узлами i и У; (X, X)tj — минимальный разрез, отделяющий узел i от У, где / е X; j gX, с пропускной способностью С(Х, Х)9.

Основная идея алгоритма Гомери—Ху состоит в итеративном построении максимального остовного дерева Т = (V, Е), ветви которого соответствуют разрезам, а пропускные способности ветвей — величинам разрезов. Число вершин дерева | V = п; число ребер — Е = п — 1. Поэтому алгоритм выполняется за п — 1 шагов.

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

Построение дерева осуществляется следующим образом:

  • 1) выбор двух произвольных узлов в качестве источника s и стока t;
  • 2) вычисление максимальной пропускной способности между стоком и источником;
  • 3) построение минимального разреза, разделяющего источник и сток.

Согласно теореме о максимальном потоке и минимальном разрезе, максимальный поток из узла s, рассматриваемого как источник, в узел ?сток вычисляется как vst = С(Х, X)st. Желательно, чтобы разрез имел минимальную пропускную способность, т.е. охватывал насыщенные связи, чтобы легче подсчитать его пропускную способность. Узлы, расположенные по обе стороны разреза, конденсируются, и разрез представляется ветвью с пропускной способностью разреза. Процесс конденсации осуществляется так, чтобы использовать решение задачи о максимальном потоке, найденное на предыдущем этапе.

Поскольку число узлов сети с каждым шагом становится меньше, то упрощается задача нахождения максимального потока между оставшимися узлами. Как показано Гомери—Ху, если следующие узлы / и у выбираются по какую-либо сторону разреза в качестве следующих источника у и стока t, то множество узлов с другой стороны разреза может быть объединено в один узел. При этом максимальный поток из / в у будет одним и тем же для исходной и конденсированной сетей [19].

Порядок конденсации узлов сети

Рис. 3.15. Порядок конденсации узлов сети: а — сеть, разделенная разрезом на подсети; б— объединение узлов правой подсети в один узел; в — результат суммирования пропускных способностей дуг

На рис. 3.15 показан процесс конденсации узлов. Связи, идущие к одноименному узлу левой подсети, объединяются в одну связь с суммарной пропускной способностью (рис. 3.15,6). Получив после объединения модифицированную сеть, можно вычислить максимальный поток от узла / к узлу у, используя описанный выше метод.

Алгоритм построения можно записать следующим образом [35]:

В качестве множества ветвей дерева выбрать пустое множество, Е = 0. Все узлы объединить в одну группу V = 1; for k = 1 to п-1

do выбрать произвольную паруузлов1 и j, еще не отделенных друг от друга

в строящемся дереве; положить s = i и t = j; вычислить максимальный поток из s в t; найти минимальный разрез, отделяющий s от t; представить данный разрез ветвью и поместить ее в дерево; вес ветви положить равным пропускной способности разреза; ветвь должна соединять узлы или группы узлов, расположенные по разные стороны разреза;

сконденсировать в один узел каждую связную подсеть, соединенную с группой, содержащей узлы i и j; k = k + 1 return к

Вычислим максимальные потоки между всеми узлами сети, изображенной на рис. 3.14.

Шаг 1. Рассмотрим узлы /= Зи/ = 4. Положим s= i= Зи t=j= 4. Максимальный поток между узлами 3 и 4, как следует из матрицы V, равен 22, поэтому v34 = v43 = 22.

Шаг 1 итерации

Рис. 3.16. Шаг 1 итерации: а — разрез сети; 6 — остовное дерево

На данном шаге минимальный разрез нужно сделать по насыщенным связям (7, 2), (3, 2), (3, 4), (3, 5) или (2, 4), (3, 4), (5, 4), (6, 4), что упрощает вычисления, так как данные разрезы будут иметь минимальную пропускную способность. Сделаем разрез сети по второму варианту, как показано на рис. 3.16. Пропускная способность разреза С(Х, X)34 = 22 соответствует максимальному потоку v34 = v43 = 22. Разрез с минимальной пропускной способностью показывает, что построение дерева разрезов можно начать с ветви, соединяющей узел 4 и конденсированный узел, состоящий из узлов 7, 2, 3, 5, 6.

Шаг 2. Рассмотрим узлы / = 1 и / = 3. Положим s = i = 1 и t =j = 3. Максимальный поток между узлами 7 и нравен 9. Поэтому v13 = v31 = 9.

Шаг 2 итерации

Р и с. 3.17. Шаг 2 итерации: а - разрез сети; б - остовное дерево

Сделаем минимальный разрез сети так, как на рис. 3.17. Пропускная способность разреза С(Х, Х)хг = 9 соответствует максимальному потоку v13 = v31 = 9. Разрез с минимальной пропускной способностью показывает, что построение дерева разрезов можно продолжить, присоединив к нему ветвь, которая соединяет узел 7 с конденсированным узлом, состоящим из узлов 2,3, 5, 6. Все узлы, кроме 7, находятся по правую сторону разреза.

Шаг 3. Рассмотрим узлы / = 4 и j= 6. Положим s=i= 4 и t=j= 6. Максимальный поток между узлами 4 и 6равен 12. Поэтому v46 = = v64=12.

ШагЗ итерации

Рис. 3.18. ШагЗ итерации: а — разрез сети; б — остовное дерево

Пропускная способность минимального разреза сети, показанного на рис. 3.18, С(Х, Х)46 = 12 соответствует максимальному потоку v46 = v64 = 12. Разрез с минимальной пропускной способностью показывает, что построение дерева разрезов можно продолжить, присоединив к нему ветвь, которая соединяет узел 6 с конденсированным узлом, состоящим из узлов 2,3,5(рис. 3.18,6).

Шаг 4. Рассмотрим узлы /= 2 иj= 3. Положим х = /= 3 и t=j= 2. Максимальный поток между узлами 2 и 3 равен 22, поэтому v23 = = v32 = 22. При минимальном разрезе сети (см. рис. 3.19, а) пропускная способность разреза С(Х, Х)32 = 22 соответствует максимальному потоку v23 = v32 = 22. При этом узлы 1 и Улежат по одну сторону разреза, а все остальные узлы по другую. Сконденсируем в один узел узлы 1 и 3, используя описанные выше и изображенные на рис. 3.15 правила. Преобразованная сеть (рис. 3.19, в) будет использоваться для вычисления максимального потока на следующем шаге итерации.

Шаг4 итерации

Рис. 3.19. Шаг4 итерации:

а — разрез сети; б — остовное дерево; в - преобразованная сеть

Шаг 5. Рассмотрим узлы/=2 и j= 5. Положим s = i=2 wt=j= 5. Максимальный поток между узлами 2 и 5 равен 17, поэтому v25 = = v52 = 17. Максимальный поток из узла 2 в узел 5 преобразованной сети равен максимальному потоку между этими же узлами исходной сети.

При минимальном разрезе сетщпоказанном на рис. 3.20, пропускная способность разреза С(Х, Х)25 = 17 соответствует максимальному потоку v25 = v52 = 17. При этом узлы 5и 6лежат по одну сторону разреза, а все остальные узлы по другую. Сконденсируем в один узел узлы 5 и 6. Эту сеть можно использовать для последующих вычислений. Число ребер в дереве стало равным 5, следовательно, процесс образования дерева завершается. Как видно, максимальные потоки между узлами дерева соответствуют найденным выше и представленным матрицей У. На дереве показаны узкие места, которые ограничивают поток в сети.

Шаг 5 итерации

Рис. 3.20. Шаг 5 итерации:

а — разрез сети; б — остовное дерево; в — преобразованная сеть

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>