Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Процедура изменения потока.

Читайте также:
  1. II. Определение для каждого процесса изменения внутренней энергии, температуры, энтальпии, энтропии, а также работы процесса и количества теплоты, участвующей в процессе.
  2. II.1. Методы поддержания и изменения корпоративной культуры.
  3. IV. Критерий удельной потенциальной энергии формоизменения
  4. А — частый сигнал (А), б — редкий (Б), Г — момент изменения последовательности сигналов
  5. Адаптация (А.) – процесс изменения знакомства сотрудника сдеятельностью и О. и изменение собственного поведения в соответствии с требованиями среды.
  6. б) Изменения пульса
  7. Б. Внести фундаментальные изменения в теорию и практику международных отношений, которых придерживается правительство, находящееся у власти в России.

Теорема Форда-Фалкерсона 2.

Поток, вычисленный с помощью алгоритма Форда-Фалкерсона имеет максимальную величину, а разрез (X,X), где X-множество вершин, помеченных при последнем помечивании, имеет минимальную пропускную способность.

Описание алгоритма

Пусть изначально в сети имеется поток f (допустим с нулевыми значениями на всех дугах).

Алгоритм Форда-Фалкерсона для нахождения максимального потока в сети состоит из двух процедур:

1) Процедура помечивания вершин

2) Процедура изменения потока

Процедура помечивания вершин.

Обработка i-й вершины с пометкой (x,e) заключается в том, что из вершины i помечаются смежные непомеченные вершины по следующему правилу:

- если дуга направлена из i в j и поток по этой дуге (fij) меньше пропускной способности дуги (cij), то вершине j присваивается метка (i+,min(e,cij-fij))

- если дуга направлена из j в i и поток по этой дуге (fji) больше нуля, то вершине j присваивается метка (i-,min(e,fji))

Эта процедура всегда начинается с помечивания и обработки истока. Он помечается особой меткой (-,¥). Затем обрабатываются другие помеченные вершины (после обработки истока пометятся вершины, смежные с ним) и т.д.

Процесс помечивания заканчивается в двух случаях:

1) Ни одну вершину больше нельзя пометить, но сток не помечен. Это значит, что найденный поток - максимальный и алгоритм останавливается.

2) Помечается сток. В этом случае производится изменение потока.

Процедура изменения потока.

Если сток получил метку (k+,d), то потоки будут изменяться на величину d следующим образом:

- если мы находимся в вершине j с меткой (i+,x), то прибавляем d к fij и переходим в вершину i.

- если мы находимся в вершине j с меткой (i-,x), то вычитаем d из fij и переходим в вершину i.

Изменение потока начинается от стока и продолжается до достижения истока. После этого все метки стираются и заново выполняется процедура помечивания вершин.

Этот процесс продолжается до тех пор, пока не будет найден максимальный поток (ни одну вершину больше нельзя пометить, но сток не помечен).

Пример:

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

Здесь первое число в скобках - пропускная способность дуги, второе число - поток (в начальный момент берем поток равный нулю)

1) Помечивание вершин

Исток i получает метку (-,¥).

Для смежной с i непомеченной вершины a1 имеем:

дуга направлена из i в a1, 0<7, следовательно присваиваем вершине a1 метку (i+,min(¥,7-0))=(i+,7)

Для смежной с i непомеченной вершины a2 имеем:

дуга направлена из i в a2, 0<6, следовательно присваиваем вершине a2 метку (i+,min(¥,6-0))=(i+,6)

После обработки вершины i мы пометили еще две вершины a1 и a2. Дальнейшую обработку можно начинать с любой необработанной помеченной вершины. Рассмотрим сначала вершину a2.

Для смежной с a2 непомеченной вершины a4 имеем:

дуга направлена из a4 в a2, поток равен нулю, следовательно метку вершине a4 не присваиваем

Для смежной с a2 непомеченной вершины s имеем:

дуга направлена из a2 в s, 0<9, следовательно присваиваем вершине s метку (a2+,min(6,9-0))=(a2+,6)

В процессе обработки вершины a2 у нас пометился сток, поэтому переходим к процедуре изменения потока. На рисунке изображены помеченные вершины.

2) Изменение потока

Сток получил метку (a2+,6), следовательно потоки будут изменяться на 6.

Начинаем со стока:

Мы находимся в вершине s с пометкой (a2+,6), следовательно изменяем поток из вершины a2 в вершину s. Новое значение потока 0+6=6, и переходим в вершину a2.

Вершина a2 имеет метку (i+,6), следовательно изменяем поток из вершины i в вершину a2. Новое значение потока 0+6=6, и переходим в вершину i.

Мы вернулись к истоку => процедура изменения потоков закончена. Стираем все метки и заново выполняем процедуру помечивания вершин.

На рисунке изображена сеть, после первого изменения потоков.

3) Помечивание вершин

Исток i получает метку (-,¥).

Для смежной с i непомеченной вершины a1 имеем:

дуга направлена из i в a1, 0<7, следовательно присваиваем вершине a1 метку (i+,min(¥,7-0))=(i+,7)

Для смежной с i непомеченной вершины a2 имеем:

дуга направлена из i в a2, 6=6, следовательно вершине a2 метку не присваиваем

Переходим к обработке вершины a1.

Для смежной с a1 непомеченной вершины a3 имеем:

дуга направлена из a1 в a3, 0<6, следовательно присваиваем вершине a3 метку (a1+,min(7,6-0)=(a1+,6)

Переходим к обработке вершины a3.

Для смежной с a3 непомеченной вершины s имеем:

дуга направлена из a3 в s, 0<4, следовательно присваиваем вершине s метку (a3+,min(6,4-0))=(a3+,4)

В процессе обработки вершины a3 у нас пометился сток, поэтому переходимк процедуре изменения потока. На рисунке изображены помеченные вершины.

4) Изменение потока

Сток получил метку (a3+,4), следовательно потоки будут изменяться на 4.

Начинаем со стока:

Мы находимся в вершине s с пометкой (a3+,4), следовательно изменяем поток из вершины a3 в вершину s. Новое значение потока 0+4=4 и переходим в вершину a3.

Вершина a3 имеет пометку (a1+,6), следовательно изменяем поток из вершины a1 в вершину a3. Новое значение потока 0+4=4 и переходим в вершину a1.

Вершина a1 имеет пометку (i+,7), следовательно изменяем поток из вершины i в вершину a1. Новое значение потока 0+4=4 и переходим в вершину i.

Мы вернулись к истоку => процедура изменения потоков закончена. Стираем все метки и заново выполняем процедуру помечивания вершин.

На рисунке изображена сеть после второго изменения потоков.

5) Помечивание вершин

Исток i получает метку (-,¥).

Для смежной с i непомеченной вершины a1 имеем:

дуга направлена из i в a1, 4<7, следовательно присваиваем вершине a1 метку (i+,min(¥,7-4))=(i+,3)

Для смежной с i непомеченной вершины a2 имеем:

дуга направлена из i в a2, 6=6, следовательно вершине a2 метку не присваиваем

Переходим к обработке вершины a1.

Для смежной с a1 непомеченной вершины a3 имеем:

дуга направлена из a1 в a3, 4<6, следовательно присваиваем вершине a3 метку (a1+,min(3,6-4))=(a1+,2)

Переходим к обработке вершины a3.

Для смежной с a3 непомеченной вершины s имеем:

дуга направлена из a3 в s, 4=4, следовательно вершине s метку не присваиваем

Для смежной с a3 непомеченной вершины a4 имеем:

дуга направлена из a3 в a4, 0<3, следовательно присваиваем вершине a4 метку (a3+,min(2,3-0))=(a3+,2)

Переходим к обработке вершины a4.

Для смежной с a4 непомеченной вершины a2 имеем:

дуга направлена из a4 в a2, 0<2, следовательно присваиваем вершине a2 метку (a4+,min(2,2-0))=(a4+,2)

Переходим к обработке вершины a2.

Для смежной с a2 непомеченной вершины s имеем:

дуга направлена из a2 в s, 6<9, следовательно присваиваем вершине s метку (a2+,min(2,9-6))=(a2+,2)

В процессе обработки вершины a2 у нас пометился сток, поэтому переходим к процедуре изменения потока. На рисунке изображены помеченные вершины.

6) Изменение потока

Сток получил метку (a2+,2), следовательно потоки будут изменяться на 2.

Начинаем со стока:

Мы находимся в вершине s с пометкой (a2+,2), следовательно изменяем поток из вершины a2 в вершину s. Новое значение потока 6+2=8 и переходим в вершину a2.

Вершина a2 имеет пометку (a4+,2), следовательно изменяем поток из вершины a4 в вершину a2. Новое значение потока 0+2=2 и переходим в вершину a4.

Вершина a4 имеет пометку (a3+,2), следовательно изменяем поток из вершины a3 в вершину a4. Новое значение потока 0+2=2 и переходим в вершину a3.

Вершина a3 имеет пометку (a1+,2), следовательно изменяем поток из вершины a1 в вершину a3. Новое значение потока 4+2=6 и переходим в вершину a1.

Вершина a1 имеет пометку(i+,3), следовательно изменяем поток из вершины i в вершину a1. Новое значение потока 4+2=6 и переходим в вершину i.

Мы вернулись к истоку => процедура изменения потока закончена. Стираем все метки и заново выполняем процедуру помечивания вершин.

На рисунке изображена сеть после третьего изменения потоков.

7) Помечивание вершин

Исток i получает метку (-,¥).

Для смежной с i непомеченной вершины a1 имеем:

дуга направлена из i в a1, 6<7, следовательно присваиваем вершине a1 метку (i+,min(¥,7-6))=(i+,1)

Для смежной с i непомеченной вершины a2 имеем:

дуга направлена из i в a2, 6=6, следовательно вершине a2 метку не присваиваем

Переходим к обработке вершины a1.

Для смежной с a1 непомеченной вершины a3 имеем:

дуга направлена из a1 в a3, 6=6, следовательно вершине a3 метку не присваиваем

Теперь у нас обработаны все помеченные вершины, но остался непомеченным сток.

Это означает, что полученный поток и есть максимальный. При последнем помечивании мы пометили вершины i и a1. Область разреза между помеченными при последнем помечивании вершинами и непомеченными имеет минимальную пропускную способность.

 


Дата добавления: 2015-07-14; просмотров: 86 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Положение о назначении стипендии Президента РФ для студентов высших учебных заведений, п. 4 (б, г)).| Размещение аудиоролика в холле кинотеатра

mybiblioteka.su - 2015-2024 год. (0.013 сек.)