Федеральное агентство по образованию

Государственное образовательное учреждение высшего профессионального образования

«САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ»

КАФЕДРА № 51

ОТЧЕТ ЗАЩИЩЕН С ОЦЕНКОЙ

ПРЕПОДАВАТЕЛЬ

Ст. преп.				П. Л. Волков
должность, уч. степень, звание		подпись, дата		инициалы, фамилия

Отчет по лабораторной работе

Оптимизация потока распределенных вычислительных сетей.

по курсу: Сети связи и системы коммутации

РАБОТУ ВЫПОЛНИЛ

СТУДЕНТ ГР.	2851				А. С. Коренчук
			подпись, дата		инициалы, фамилия

Санкт-Петербург 2012

1. Цель работы.

Изучение алгоритма оптимизации потока на графах и его применение.

2. Вариант задания.

3. Результаты исследования графа сети.

3.1. Построить три NS NT – разделяющих множества.

Назовем VW-разделяющим множеством такое множество дуг графа, которое обладает тем свойством, что каждая простая цепь из вершины V в вершину W содержит как минимум одну дугу из этого множества.

NsNт – разделяющие множества:

1) дуги (N₂, N₃), (N₂, N₅)

2) дуги (N₅, N₀), (N₇, N₀)

3) дуги (N₃, N₄), (N₃, N₆), (N₅, N₀), (N₅, N₆)

3.2. Построить три NS NT – отделяющих множества.

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

NsNт – отделяющие множества:

1) вершины N₃, N₅

2) вершины N₅, N₇

3) вершины N₄, N₅, N₆

3.3. Построить три разреза между вершинами NS и NT.

Назовем разрезом такое разделяющее множество, никакое собственное подмножество которого не является разделяющим. В силу минимальности этого VW-разделяющего множества оно может содержать только одну дугу каждой простой цепи из V в W.

Разрезы между вершинами Ns и Nт:

1) разрез (N₂, N₃), (N₂, N₅)

2) разрез (N₅, N₀), (N₇, N₀)

3) разрез (N₃, N₄), (N₆, N₁), (N₆, N₇), (N₅, N₀).

3.4. Указать пропускные способности построенных разрезов.

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

1) Пропускная способность разреза (N₂, N₃), (N₂, N₅): b = b₂₃+b₂₅ = 4+55 = 59

2) Пропускная способность разреза (N₅, N₀), (N₇, N₀): b = b₅₀+b₇₀ = 23+97 = 120

3) Пропускная способность разреза (N₃, N₄), (N₆, N₁), (N₆, N₇), (N₅, N₀):

b = b₃₄+b₆₁+b₆₇+b₅₀ = 12+1+8+23 = 44

3.5. Определить диаметр.

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

Диаметром графа является маршрут N₂, N₅, N₀, N₁ (или другие кратчайшие маршруты, соединяющие вершину графа с номер n с вершиной с номером n-1, например 3-ю и 2-ю, 4-ю и 3-ю).

4. Описание алгоритма Форда-Фалкерсона.

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

Алгоритм состоит в систематическом поиске всех возможных путей из NS в NT, увеличивающих поток (процесс расстановки пометок), и в соответствующем увеличении потока (изменение потока).

ШАГ 1. Процесс расстановки пометок.

На шаге 1 каждый узел находится в одном из трех состояний:

– "не помечен",

– "помечен и не просмотрен",

– "помечен и просмотрен".

Вначале все узлы не помечены. Пометка произвольного узла N_j всегда состоит из двух частей (i знак, E(j)). Первая часть – индекс узла N_i, который указывает, что нужно изменить поток из N_i в N_j и знак изменения этого потока (+ увеличение, - уменьшение). Вторая часть пометки – число, указывающее на величину изменения этого потока.

Источнику N_s приписываем пометку (S+, ∞) (узел N_s готов отправить в сеть поток неограниченной величины). Теперь узел N_s "помечен и не просмотрен". А все остальные узлы "не помечены".

Выберем любой помеченный и не просмотренный узел N_j. Пусть он имеет пометку (i+, E(j)) или (i–, E(j)). Два узла будем называть соседними, если они соединены дугой. Из всех узлов, соседних с N_j, выделим те узлы N_k, которые не помечены и для которых x_jk< b_jk (поток из узла N_j в узел N_k меньше пропускной способности). Припишем каждому узлу N_k пометку (j+, E(k)), где E(k)=min { E(j), b_jk – x_jk }. Такие узлы N_k теперь "помечены и не просмотрены".

После этого всем соседним с N_j узлам N_k, которые не помечены и для которых x_kj > 0, приписываем пометку (j–, E(k)), где E(k)=min { E(j), x_kj }. Такие узлы N_k теперь также "помечены и не просмотрены".

Сейчас все узлы, соседние с N_j, помечены или не могут быть помечены. Узел N_j считается помеченным и просмотренным, его можно больше не рассматривать на этом шаге.

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

ШАГ 2. Изменение потока.

Предположим, что сток N_T имеет пометку (k+, E(T)). Тогда заменим x_kT на (x_kT +E(T)). Если же он имеет пометку (k–, E(T)), то x_kT заменим на (x_kT - E(T)). Затем в любом из этих случаев переходим к узлу N_k. Если узел N_k имеет пометку (j+, E(k)), то x_jk заменим на (x_jk + E(T)), и перейдем к узлу N_j. Если узел N_k имеет пометку (j–,E(k)), то x_jk заменим на (x_jk – E(T)) и перейдем к узлу N_j. Дойдя таким образом до узла N_S стираем все старые пометки узлов и вновь переходим к шагу 1.

5. Нахождение максимального потока в сети.

Шаг 1.

1.1) Узлу N_S приписываем пометку (S+, ∞);

1.2) Узел N_S имеет два соседних узла: N₁, N₇, N₃ и N₅.

Узлы N₁ и N₇ не могут быть помечены, т.к. b_S1-x_S1=0 и x_1S= 0, b_S7-x_S7=0 и x_7S= 0;

Для узла N₃: x_S3<b_S3, он может быть помечен, b_S3-x_S3=4-1=3, приписываем пометку (S+, 3), т.к. 3<∞;

Для узла N₅: x_S5<b_S5, он может быть помечен, b_S5-x_S5=55-0=55, приписываем пометку (S+, 55), т.к. 55<∞;

Узел N_S помечен и просмотрен, узлы N₃, N₅ помечены и не просмотрены, узлы N₁, N₇ не могут быть помечены;

1.3) Узел N₃ имеет три соседних узла: N_T, N₄ и N₆.

Узел N_T не может быть помечен, т.к. b_3T-x_3T=0 и x_T3= 0;

Узел N₆ не может быть помечен, т.к. b₃₆-x₃₆=1-1=0;

Для узла N₄: x₃₄<b₃₄, он может быть помечен, b₃₄-x₃₄=12-0=12, приписываем пометку (3+, 3), т.к. 3<12;

Узел N₃ помечен и просмотрен, узел N₄ – помечен, а узлы N₆, N_T – не могут быть помечены;

1.4) Узел N₅ имеет три соседних узла: N₄, N₆ и N_T.

Узел N₄ помечен;

Для узла N₆: x₅₆<b₅₆, он может быть помечен, b₅₆-x₅₆=102-0=102, приписываем пометку (5+, 55), т.к. 55<102;

Для узла N_T: x_5T<b_5T, он может быть помечен, b_5T-x_5T=23-0=23, приписываем пометку (5+, 23), т.к. 23<55;

Узел N₅ помечен и просмотрен, узлы N₆, N_T – помечены и не просмотрены;