Geum.ru

Программа, методические указания и контрольные задания Для студентов-заочников Казань, 2009 г

Вид материалаПрограмма

Содержание


Варианты контрольного задания
Матрицы пропускных способностей
Подобный материал:
1   2   3

Рис. 4.

Рассмотрим алгоритм Форда-Фалкерсона

Итерация первая

Шаг 1. Зададим начальное значение потока (u) = 0. На дугах орграфа рядом с пропускными способностями в скобках будем помещать очередное значение потока.

Шаг 2. Строим увеличивающую цепь.

Дуги, входящие в цепи, должны быть допустимыми. Так, например, цепь {s х3 х4 x1 x2 t} не является увеличивающей, так как дуга (х4,x1) не является допустимой - ее направление противоположно направлению потока и величина потока по ней равняется 0. Значит, на первой итерации нужно строить цепь, направление дуг которой совпадает с направлением потока. Пусть это будет цепь G1={s x1 x4 t}.

Шаг 3. Дуги (s, x1), (х1 х4), (х4 t), входящие в цепь G1, являются увеличивающими, поэтому (u) = с(u) - (u), u{sx1, x1x4, x4t}. Так как (u) = 0, то (u) = с(u) и  = min u{c(u)} = min{7;5;6} = 5.

Увеличим величину потока в цепи G1 на величину . Результат отобразим на рис. 5.



Рис. 5


В следующих итерациях сразу переходим ко второму шагу.

Итерация вторая

Шаг 2. Построим увеличивающую цепь G2={s х3 х4 t}. Вычислим .

 = min{4-0;4-0;6-5} = l.

Шаг 3. Увеличим поток по цепи G2 на величину =1 (см. рис. 6.) .



Рис. 6

Итерация третья

Шаг 2. Построим увеличивающую цепь G3={s x1 x2 t}. Вычислим .

 = min{7 - 5;3 - 0;5 - 0} = 2 .

Шаг 3. Увеличим поток по цепи G3 на величину =2 (см. рис.7.).




Рис. 7

Итерация четвертая

Шаг 2. Построим увеличивающую цепь G4={s x3 x4 x1 x2 t}. В этой цепи дуга (x4 x1) будет уменьшающей, так как ее направление противоположно направлению потока и допустимой, так как величина потока (x4x1) = 5≠0.

Причем для этой дуги (x4x1)=5 - значение потока. Для остальных дуг, являющихся увеличивающими, (u) вычисляется согласно правилу по формуле (u) = c(u) - (u). Вычислим .

 = min{4-1;4-1;5;3-2;5-2} = 1

Шаг 3. По дуге (x4 x1) уменьшим поток на величину , на всех остальных -увеличим на  (см. рис.8.).



Рис. 8

Итерация пятая

Покажем, что дальнейшее построение увеличивающих цепей невозможно. Любая цепь, для которой конечным звеном является недопустимая дуга (x4t) (для нее (x4t) = c(x4t) = 6), должна быть отброшена. Остаются цепи,проходящие через дугу (x2t). Но любая из этих цепей содержит хотя бы одну из недопустимых дуг (x1x2) (поток равен пропускной способности), (x3x2) (по ней проходит нулевой поток).

Таким образом, невозможно дальнейшее построение увеличивающих цепей и, значит, максимальный поток найден. Его величина s=7 + 2 = 3 + 6 = 9.

Проверить правильность полученного ответа можно, определив величину минимального разреза. Его значение должно совпадать со значением максимального потока.

Из рис. 9 видно, что в минимальный разрез входят дуги (x1x2) и (x4t). Сумма их пропускных способностей с(x1x2) + c(x4t) = 9 = s




Рис. 9

Построим матрицу потока.

Таблица 5
x1
x2
x3
x4
t
Сумма потока, выходящего из вершины

s
7
0
2
0
0
9

x1
0
3
0
4
0
7

x2
0
0
0
0
3
3

x3
0
0
0
2
0
2

x4
0
0
0
0
6
6

Сумма потока, входящего в вершины
7
3
2
6
9




ВАРИАНТЫ КОНТРОЛЬНОГО ЗАДАНИЯ


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

Таблица 6

Последняя цифра шифра
0
1
2
3
4
5
6
7
8
9

Номера выполняемых задач
15
16
17
18
19
20
11
12
13
14


В задачах 11-20 для заданной матрицы пропускных способностей построить транспортную сеть. Определить на ней максимальный поток и найти величину минимального разреза.


Матрицы пропускных способностей












СОДЕРЖАНИЕ
Предисловие
2

1
Общие рекомендации по работе над дисциплиной «Единая транспортная система РТ»
3

2
Программа дисциплины «Единая транспортная система РТ» цикла ГСЭ для студентов заочного факультета КГЭУ
5

3
Методические указания к изучению дисциплины «Единая транспортная система РТ»
7

4
Методические указания к выполнению практического занятия

9

5
Методические указания к выполнению и оформлению контрольной работы

20