Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

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






Шаг 1(итерация 2). Расстановка пометок.






Приписываем узлу Ns пометку (S+, ∞). Узел Ns имеет 4 соседние непомеченные вершины: N0, N2, N3, N7. Узлы N0 и N3 пометить нельзя, так как Xij = 0. Узел N2 пометить так же нельзя, так как BS2-XS2=0. Пометим узел N7 как (S+, E(7)), где E(7)=min(E(s), BS7-XS7)=1.

Узел N7 имеет 3 соседние непомеченные вершины: N0, N5, N6. Узел N6 пометить нельзя, так как X76=0. Пометим узел N0 как (N7+, E(0)), где E(0)=min(E(7), B70-X70)=1.

Узел N0 имеет 2 соседние непомеченные вершины: N2, N6. Узел N2 пометить нельзя, так как X02=0. Пометим узел N6 как (N0+, E(6)), где E(6)=min(E(0), B06-X06)=1.

Узел N6 имеет 2 соседние непомеченные вершины: Nt, N5. Узел N5 пометить нельзя, так как X65=0. Пометим узел Nt как (N6+, E(t)), где E(t)=min(E(6), B6T-X6T)=1. Так как узел Nt помечен, то переходим к шагу 2.

 

 


 

Шаг 2(итерация 2). Изменение потока.

Максимальный поток увеличен на E(t)=1.

Пометка N7 есть (Ns+, 1), увеличиваем XS7 на 1. XS7=XS7+1=1.

Пометка N0 есть (N7+, 1), увеличиваем X70 на 1. X70=X70+1=1.

Пометка N6 есть (N0+, 1), увеличиваем X06 на 1. X06=X06+1=1.


Пометка Nt есть (N6+, 1), увеличиваем X6T на 1. X6T=X6T+1=1.

Шаг 3.

Так как в графе больше нет реберно-независимых путей, алгоритм завершен.

 

Вывод:

С помощью алгоритма Форда-Фалкерсона между парой вершин S и T найдены 2 реберно-независимые цепи:

- (S-2), (2-3), (3-T).

- (S-7), (7-0), (0-6), (6-T).

 

Анализ результатов исследования заданного графа сети(ST-отделяющееся множество, ST-разделяющееся множество, разрез, пропускная способность и максимальный поток, обоснование выбора диаметра).

ST-разделяющим множеством называется множество A дуг графа, обладающее тем свойством, что любая дуга, принадлежащая всякой простой цепи из S в T, содержится в A.

ST-разделяющее множество A ={(S, 2), (2, 3), (3, T), (S, 7), (7, 5), (5, 3), (7, 0), (0, 6), (6, T), (5, 6), (2, 0}.

 

ST-отделяющим множеством называется множество B вершин графа (не содержащее S и T), обладающее тем свойством, что любая простая цепь из S в T, проходит через вершину из B и все вершины, через которые проходит всякая простая цепь S в T, включены в B.

ST-отделяющее множество B ={0, 2, 3, 5, 6, 7}.

 

Разрезом называется такое разделяющее множество, никакое собственное подмножество которого не является разделяющим.

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

Разрез {{S, N2}, {S, N7}} с пропускной способностью равной 2.

 

Диаметром графа называется максимальная длина кратчайших маршрутов в графе (максимум берется по всем парам вершин).

 

Диаметр

{N0-N1}-1

{N0-N2}-2

{N0-N3}-3

{N0-N4}-2

{N0-N5}-3

{N0-N6}-1

{N0-N7}-2

 

Диаметр = 4

 

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

Если в сети существует цепь, идущая из Ns в Nt, то максимальный поток из Ns в Nt равен минимальной пропускной способности разрезов, разделяющих Ns и Nt.

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


Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.006 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал