Да разгледаме проблема за определяне на максималния поток между свързания специални мрежови възли. Всяка дъга на мрежата има капацитет и в двете посоки, които определят максималния размер на ток, преминаващ през дадена дъга. Ориентирано (едностранно) на дъгата съответства на капацитета нула в грешната посока.
Мрежа капацитет ЦНЖ може да се представи под формата матрица.
Етап 1:
Виж целта, свързване на източник S и източване т. при което потокът се положителна стойност. посока S → Т. Ако такава цел не съществува, преминете към стъпка 3. В противен случай, преминете към стъпка 2.
Да () - ленти дъги верига (S, т) в посока S → т (т → S).
Матрицата пропусквателни С = [CIJ] промяна, както следва:
а) приспадане # 1012; на всички;
б) се добавят # 1012; за всички.
Замяна на текущия матрица С на наскоро полученото и преминете към стъпка 1. операция (а), дава възможност да се използват остатъци пропусквателни верига избрани дъги в посока S → т.
Операция (б) възстановява първоначалния капацитет на мрежата, тъй като намаляване на пропускателната способност на дъгата в същата посока може да се види и с увеличаване на капацитета му в обратната посока.
Намери максималният поток в мрежата.
Нека С = [CIJ] - начална честотната лента за матрица.
C * = [C * у] - окончателно матрица, получена чрез модифициране на първоначалната матрица (етап 1 и 2).
Оптимално поток X = [Xij] в дъги определят, както следва:
Максималната поток от Т е равен на:
Пример: За определяне на максималния поток в колоната
Като изходен верига изберете S → 1 → 4 → т. (-) и клетките (1, S), (4,1), (т, 4) са маркирани с (+) След това клетките (S, 1), (1,4), (4, т), са обозначени.
Максималната поток за тази схема е
Възможно е да изберете друга начална верига. Един добър избор е да се осигури най-голяма стойност # 1012;. Но тя може да бъде много варианти на тези вериги. Когато програмиране верига, която се определя директно от матрица С, като се излиза от първия ред на S-низ и избора на следващия възел сред тези, които са свързани към S положителен поток. Следваща се счита за ред, съответстваща на избрания възел, и избира следващия комутационен възел, свързан към предходния положителен дъга. Процесът продължава дотогава. т до възловата точка е достигната.
Ние коригира матрица С, изваждане # 1012; = 5 на всички елементи маркирани (-), и добавяне на всички елементи с плюс (+). Ние получите нова матрица.
Подобни действия се извършват и в последващи итерации.
Ние изберете верига (S → 3 → 2 → т)
# 1012; = мин = 10 Правилно матрица С
Ние изберете верига (S → 3 → 1 → 4 → т)
# 1012; = мин = 5 Правилно матрица С
Ние изберете верига (S → 4 → т)
# 1012; = мин = 3 Правилно матрица С
Ние изберете верига (S → 3 → т)
# 1012; = мин = 2 Правилно матрица С
Между S и Т е невъзможно да се изгради верига, тъй като всички елементи в колона Т е нула. По този начин получаваме матрица C *
Построява матрица Н. отрицателни елементи в матрицата ще заменят нули.
Σ # 1012; = 5 + 10 + 5 + 3 + 2 = 25
Графично, разтворът представена графика:
Свързани статии