Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

ИСО / Задача о максимальном потоке в сети

.doc
Скачиваний:
17
Добавлен:
10.04.2015
Размер:
53.25 Кб
Скачать

Задача о максимальном потоке в сети.

Задача о нахождении максимального потока в сети является одной из задач относящихся к разделу «Сетевое моделирование».

Е сли есть некоторая сеть, которая содержит n –узлов, и необходимо определить наибольший возможный поток (данных, грузов и т.д.) между двумя заранее определенными узлами, при этом пропускные способности узлов известны (в общем случае в сети любой узел имеет соединение с каждым из остальных узлов данной сети), то для решения данной задачи используют данный алгоритм нахождения максимального потока.

Алгоритм нахождения максимального потока:

  1. Составить матрицу пропускных способностей сети, для этого в заголовочном столбце написать наименование узлов, из которых выходит поток, а в заголовочной строке записать наименование узлов, в которые поток входит.

Следует также заметить, что пропускная способность узла по отношению к самому себе равняется нулю.

Пример (по рисунку 1):

С

S

1

2

T

S

0

5

2

4

1

3

0

3

5

2

6

8

0

7

T

4

5

5

0

  1. Определить цепь из S в T с положительным значением потока (поток через цепь может быть либо положительным, либо нулевым). Если такой сети не существует, то перейти к пункту 3, иначе перейти к пункту 2.

  1. Обозначим – пропускные способности дуг цепи в направлении T  S, и – пропускные способности дуг цепи в направлении S T.

Вычислить .

В новой матрице пропускных способностей вычесть из и прибавить к .

Перейти к пункту 1.

  1. Составить матрицу максимальных потоков в дугах сети:

где:

– элементы исходной матрицы пропускных способностей.

– элементы матрицы полученной после преобразования согласно пунктам 1 и 2 данного алгоритма.

  1. Определить максимальный поток в сети.

Для этого существует 3 способа:

    1. , где n – число узлов в сети,

    2. , где n – число узлов в сети,

    3. , где m – общее число всех .

Примечание:

Наиболее интересной задачей с точки зрения программирования является задача выбора цепи (по пункту 1). Данную задачу можно решить различными способами, разницей между которыми будет только скорость просчета. Не существует общего метода по выбору положительной цепь. Из наиболее применимых можно выделить метод нахождение по критерию максимальности, то есть выбирается цепь с максимальным потоком.

Соседние файлы в папке ИСО