АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Сеть. Потоки на сетях. Задача нахождения патока максимальной мощности. Алгоритм Форда-Фалкерсона

Читайте также:
  1. VI. Общая задача чистого разума
  2. XII. ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ
  3. Адресация и маршрутизация в компьютерных сетях. DNS-имя
  4. Адресация и маршрутизация в компьютерных сетях. МАС-адрес.
  5. Алгоритм
  6. Алгоритм
  7. Алгоритм
  8. Алгоритм
  9. Алгоритм 65 «Кровотечение в послеродовом периоде»
  10. Алгоритм 72 «Ожоги и травмы глаза, века, конъюнктивы»
  11. Алгоритм MD4
  12. Алгоритм RC6

Сеть – конечный граф без циклов и петель, ориентированный в одном общем направлении от вершины S(исток графа) к вершине T(сток графа). Будем представлять, что по ребрам ij из S в T направляется некоторое вещество(груз, информация и проч), максимальное количество вещества, которое может пропустить ij называется его прорускной способностью; если вершины не соединены, то пропускная способность 0. Поток по ребру ij-

Если из I в j направляется поток Fij, то величина потока обратная ровна -Fij.

b
S
t

 

 


a

 

 

Свойства потоков по ребрам:

1.Поток по каждому ребру не превышает его пропускной способности.

2.Количество вещества, притекающего в вершину равно количеству вещества, вытекающего из нее.

Общее количество вещества, исходящего из истока S совпадает с общим количеством вещества, поступающего в сток T.

Пусть Х некоторое подмножество вершин(S принадл Х, Т не принадл Х). Пара (Х,Х*), где Х* = v/X – разрез, отделяющие S под Т. Пропускной способностью разреза С(Х,Х*) называется сумма прорускных способностей дуг, составляющих этот разрез.

Дуги, которые идут от S к T(прямые) составляют разрез. Дуги от T к S(обратные) в разрез не входят.

Х=(S,a)

X*=(t,b)

C(X,X*)=

Постановка задачи

Задана сеть с фиксированными пропускными способностями дуг. Найти среди всех потоков поток максимальной мощности.

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

b
S
t
d
Мощность макс потока, пропущенного в сети, равна минимальной пропускной способности разреза.
a

 

 


5,2 2,2

1,0

4,3 4,4

4,4 1,1

5,3

 

 

V0=9

S(S+; ∞)

a(S+; 3)

b(S+;1)-------- d(b-;1)

t(d+;2)

S --> b <-- d --> t

V1=V0+e=9+1

S(S+; ∞) -----X=(S, a) R(X,X*)=10/10 c(X,X*)=2+4+4=10

a(S+; 3) -----X*=(t, b, d)

 

Шаг 0. В процессе работы алгоритма каждая вершина относиться к одному из 3-х множеств: не помеченные вершины, помеченные не просмотренные, просмотренные(окрашенные).

Шаг 1. Пометим вершину S меткой (S+; бесконечность), остальные не помечены.

Шаг 2. Пусть V некоторая помеченная, но не просмотренная вершина. Рассмотрим все соседние с ней не помеченные вершины. Для каждой из таких вершин U возможны следующие ситуации:



а) существует прямая дуга (V,U), f(V,U)<c(V,U), тогда U вершина получает пометку U(V+;()())

б) существует обратная дуга (U,V), f(u,v) > 0. Тогда U получает пометку u(v-;f(u,v))

в) существует прямая дуга (V,U) или существует обратная и поток равен 0, тогда вершина U не помечается.

Когда все соседние с V вершины проанализированы, V переходит в множество просмотренных вершин.

Шаг 3. Повторяем шаг 2 до тех пор пока не возникнет одна из следующих ситуаций:

а) все вершины графа разбиты на 2 подмножества(просмотренные и непомеченные(включая Т). Тогда в сети построен макс поток мощности V и мин разрез Х,Х*,

б) если вершина Т получила пометку, то в сети существует увеличивающий путь из S вT, который можно определить идя из Т обратно к S. Для найденного пути определяют величину е(эпсилон) увеличения мощности потока. На прямых дугах пути ST изменяем F на +е на обратных на –е. Мощность равна V предыдущая +е.

 


1 | 2 | 3 | 4 | 5 | 6 | 7 |


Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.005 сек.)