Добавил:

Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Белгородский государственный технологический университет им. В.Г. Шухова

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

Lektsia_po_Diskr

.pdf

Скачиваний:

Добавлен:

11.03.2015

Размер:

1.15 Mб

Скачать

☆

<<< < Предыдущая 1 2 3 4 56 / 76 7 > Следующая >>>

∞

Обозначим через l ij

расстояние между i - той и j - той вершинами.

Пусть назначена i

i - той вершине (I = 0,1,…, n). Рассмотрим все

j - ые вершины, смежные с i - той. Если

j - i > l ij

(1)

то полагаем

j = i + l ij

(2)

И так до тех пор, пока не дойдем до n . Значение n

и будет значением кратчайшего пути.

Обратный ход:

Мы получили

n = k + l

(1*)

Среди расстояний, соединяющих х n

со смежными вершинами, ищем

l k

= n - k .

Затем ищем вершину х k

, у которой k =

+ l k

. Затем переходим в х k

и так далее, пока не доберемся

до х 0 .

Замечание 1:

Изменение значения

происходит только тогда, когда выполняется неравенство (1), то есть j > i + l ij .

Заменяя значение j

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

нет, и, следовательно, каждая вершина получит значение .

Замечание 2:

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

Обоснование алгоритма:

Так как значение при каждом шаге может только уменьшаться, то последовательность значений для каждой вершины в конечном итоге принимает минимальное значение, т.е каждое - это кратчайшее расстояние

данной вершины от х 0 .

Пример:

Рис. 47. Пример взвешенного графа

1)i = 0, j = 1, 2, 3;

J = 1:	1 -	0 = ∞ - 0 = ∞ > l 0 1 ;		1 = 0	+ l 0	1= 5;	заносим в таблицу.
j=2:	2 -	0 = ∞ - 0 = ∞ > l 0	2 ;	2 = 0	+ l 0	2 = 6;	заносим в таблицу.
j=3:	3 -	0 = ∞ - 0 = ∞ > l 0	3 ;	3 = 0 + l 0		3 = 4;	заносим в таблицу.

2)i = 1, j = 0, 2, 4 (0 –уже не рассматриваем).

j = 2:		2 - 1 < 11 2 ,	2 < 1+ l 1 2 ; значит не меняем 2
j = 4:		4 > 1 + l 1 4 ,	4 = 5 + 8 = 13; заносим в таблицу.

3)i = 2, j = 0, 1, 3, 4.

j = 0; не рассматриваем
j = 1:	1 <	2 + l 1 2 ; значит не меняем		1 .
j = 3:	3 <	2 + l 2	3 ; значит не меняем	3
j = 4:	4 >	2 + l 2	4 , 4 =6 +2 = 8; заносим в таблицу.

4)i = 3, j = 0, 2, 5, 6;

			54
j = 0; не рассматриваем
j = 2:	2 < 3 + l 2		3 ; значит не меняем
j = 5: 5		= 4+6 =10; заносим в таблицу.
j = 6:	6	= 3 + l 6	3 , 6 = 4+ 10 =14; заносим в таблицу.

5)i = 4, j = 1,2,5,7;

j = 1:	1 < 4 + l 1 4 ; значит не меняем
j =2:	2 < 4 + l 2	4 ; значит не меняем
j= 5:	5 < 4 + l 4	5 ; значит не меняем
j = 7:	7 = 4 + l 4	7 , 7 = 10; заносим в таблицу.

6)i = 5, j = 3, 4, 6, 7;

j = 3:	3 < 5 + l 3 5 ; значит не меняем
j = 4:	4 < 5 + l 4	5 ; значит не меняем
j = 6:	6 = 5 + 5	6 , 6 =14; заносим в таблицу.
j = 7:	7 < 5 + l 5 7 ; значит не меняем

7)i =6, j = 3, 5, 7;

j = 3:	3 < 6 + l 3	6 ; значит не меняем
j = 5:	5 < 6 + l 5	6 ; значит не меняем
j = 7:	7 < 6 + l 6	7 ; значит не меняем

8)i = 7, j= 4, 5, 6;

j = 4; не рассматриваем j = 5; не рассматриваем

j = 6: 6 < 7 + l 6 7 ; значит не меняем Получили схему:

0	1	2	3	4	5	6	7
0	∞	∞	∞	∞	∞	∞	∞
0	5	6	4	13
				8	10	14	10
Итого	5	6	4	8	10	14	10

Обратный ход:

Начиная с последней вершины, проверяем все ей смежные на выполнение условия: l k n = n - k .

Получим кратчайший путь х 7 х 4 х 2 х 0 .

6.8. Задача о максимальном потоке

Предварительно рассмотрим простую задачу.

Пусть трубопровод состоит из трех труб различного сечения с пропускными способностями 10 л/мин, 5

л/мин, 7 л/мин.

Вполне очевидно, что пропускная способность системы равна 5 л/мин, т.е. совпадает с наименьшей пропускной способностью труб.

10 л/мин 5 л/мин 7 л/мин

Рис. 48. Трубопровод

Пусть имеется некоторый взвешенный орграф G(V, E). Выделим в этом графе некоторые две вершины s, t, которые назовем источником и стоком.

Будем рассматривать веса как пропускную способность дуги q ij . Количество фактически проходящих еди-

ниц по дуге обозначим через z ij . z ij - поток, проходящий через дугу i j. Ясно, что q ij z ij .

Пусть к источнику S прибывает поток Р. Для того, чтобы сеть функционировала нормально, должно быть Р s

= Р t , Р i - Р i =0. Требуется организовать перемещение так, чтобы величина Р была максимальной.

Разделим множество вершин на подмножества Х 1 и Х 2 . Рассмотрим дугу (V i V j ) и отнесем вершину V i к Х

1 , а V j к Х 2 . Таким образом, для данного разбиения (Х 1 , Х 2 ) концы дуг принадлежат разным подмножествам.

Такое разбиение называется разрезом, отделяющим вершину V i от V j . Совокупность потоков, протекающих

через Х 1 Х, называется потоком разреза.

6.8.1. Теорема Форда – Фолкерсона

Теорема. Максимальный поток сети равен минимальному потоку разреза.

Доказательство:

Так как максимальный поток обязательно пройдет по дуге минимального разреза, то это будет означать, что

он совпадает с минимальным потоком разреза. Это будет выполняться, если выполняется условия: Р s = Р t , т.е.

Р s - Рt = 0.

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

Будем последовательно строить разрезы, и назначать каждой вершине некоторое число – метку r по следующему правилу.

r j = min(r i , q - z ij ), если z ij ≤ q ij и дуга исходит из вершины V i , и r j = z ij , при z ij >0, если дуга

заходит в V i .

Для определенности в метку будем включать указатель вершины, из которой мы пришли в вершину V j , то

есть метка будет выглядеть: +V i ,r i , если V i вершина исхода; и -V i , r i , если V i вершина захода. Будем строить разрезы.

Включаем в разрез источник ─ вершину V1 , присвоив ей метку r s = ∞, и положив все потоки z ij = 0.

Просматриваем все смежные вершины, идущие в прямом направлении Γ+ . Если им не присвоены метки, то присваиваем их

r j =min(r i ,q ij -z ij )

(1)

Тем самым включаем эти вершины в подмножество Х1.

Просматриваем все смежные вершины, идущие в обратном направлении Γ- . Если им не присвоены метки, то присваиваем их

r j = z ij >0

(2).

Тем самым включаем эти вершины в подмножество Х1.

Проделаем это со следующей вершиной и со следующей, пока не дойдем до вершины t.

1). При этом, может оказаться, что вершина t попадает во множество Х 1 . Это будет означать, что полученные

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

Для дуг, идущих в прямом направлении найдем b1 = min(q - z ij ).

Для дуг, идущих в обратном направлении найдем b2 = min z ij > 0 .

Найдем b = min(b1 , b2). Используя метки, строим цепь, связывающую сток с источником. Такие цепи называются аугментальными. Для дуг, идущих в прямом направлении, к имеющимся потокам прибавим величину b, и вычтем b из потоков в обратном направлении.

После этого стираем все метки и строим новые разрезы с новыми потоками.

2). Вершина t не попала в Х1. Это значит, что для дуг в прямом направлении имеем q = z ij , а для дуг в

обратном направлении

z ij .= 0. Иначе говоря, величина потока равна значению разреза, который и будет минимальным.

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

Таким образом, установлено существование минимального разреза. Теорема доказана. Заодно, получен алгоритм нахождения наибольшего потока.

Пример.

Граф задается матрицей смежности (пропускных способностей дуг).

	V1	V2	V3	V4	V5	V6	V7	V8	V9	V1
V1		10	17
V2				13		23
V3				11
V4					5
V5			19				11
V6					14		10	21
V7									8	11
V8							17
V9										23
V10								15
		V		V		V			V
		2	6			8		10
		●
V1 ●			V4

	●				●				●
	V		V	V					V
	3			5	7				9
				Рис. 49. Пример сети с 10 вершинами
Вершина	V	─ источник, вершина V			─ сток. Строим разрезы.
	1			10
Вершине V присваиваем метку r = ∞, положив все потоки z ij = 0.
	1			1
Просматриваем вершину				V1.
Γ+ (V ) = {V		, V }.
1	2	3
Присваиваем вершине V				метку + V , r =		min (r	,q - z		) = =min(∞, 10 -0) =10.
			2	1	2	1	,q	12	12
Присваиваем вершине V				метку + V , r =		min (r	,q	- z	) = =min(∞, 17 -0) =17.
Γ- (V ) – пусто.			3	1	3	1		13	13
Γ- (V ) – пусто.
1	V	помечена и просмотрена.
Вершина	V	помечена и просмотрена.
	1			V .
Просматриваем вершину				V .
Γ+ (V ) = {V		, V }.		2
Γ+ (V ) = {V		, V }.
2	4	6
Присваиваем вершине V				метку + V , r =		min (r , q - z			) = min(10, 13 -0) =10.
			4	2	4	2		24	24
Присваиваем вершине V				метку + V , r =		min (r , q - z ) = min(10, 23 -0) =10.
			6	2	6	2		26	26
Γ- (V2) = {V }. Но V			помечена.
Вершина	1	1
Вершина	V	помечена и просмотрена.
	2			V .
Просматриваем вершину				V .
				3
Γ+ (V3) = {V4}. Но V4			помечена.

Метка V :	+ V , r =		10.
2	1	2
Метка V :	+ V , r =		17.
3	1	3

Метка V :	+ V , r	=	10.
4	2	4
Метка V :	+ V , r	=	10.
6	2	6

													57
Γ- (V ) = {V		, V		. Но V				помечена, а z				= 0..
3	1		5}			1					53
Вершина	V		помечена и просмотрена.
	3							V .
Просматриваем вершину								V .
Γ+ (V ) = {V }.								4
Γ+ (V ) = {V }.
4		5
Присваиваем вершине V								метку + V , r =					min (r , q - z			) = min(10, 5 -0) = 5.		Метка V :		+ V , r		= 5.
							5			4	5		4	45	45				5	4	5
Γ- (V4) = {V2		, V3}. Но V2						помечена, и V3				помечена.
Вершина	V		помечена и просмотрена.
	4							V .
Просматриваем вершину								V .
Γ+ (V ) = {V			, V }.					5
Γ+ (V ) = {V			, V }.
5		7	3
Присваиваем вершине V							7	метку + V , r =					min (r , q - z			) = min(5, 11 -0) = 5.		Метка V :		+ V , r		=	5.
Вершина V помечена.							7			5	7		5	57	57				7		5	7
Вершина V помечена.
	3							и V	помечены.
Γ- (V ) – {V , V }. Но V								и V	помечены.
5	4		6			4		6
Вершина	V		помечена и просмотрена.
	5
Просматриваем вершину								V .
								6
Γ+ (V ) = {V			, V	, V }. Но V					и V	помечены. Присваиваем вершине V метку + V , r = min (r , q													- z	)
6		5		7	8			5	7			10.					8	6	8		6	68		68
= min (10, 21 -0) =10.					Метка V :				+ V , r =			10.
								8	6	8
Γ- (V6) = {V2}. Но V2						помечена.
Вершина	V		помечена и просмотрена.
	6
Просматриваем вершину								V .
Γ+ (V ) = {V9 , V }.								7
Γ+ (V ) = {V9 , V }.
7			10					метку + V , r =					min (r , q - z			) =	min(5, 8 - 0) =5. Метка V : + V , r = 5.
Присваиваем вершине V								метку + V , r =					min (r , q - z			) =	min(5, 8 - 0) =5. Метка V : + V , r = 5.
							9			7	9		7	79	79				9	7	9
Присваиваем вершине V								метку + V , r				= min (r , q			-	z	) = min(5, 11 - 0) = 5. Метка V10:				+ V , r			=
5							10			7		10	7	710		710						7	10
5				V }. Но они
Γ- (V ) = {V , V				V }. Но они					помечены.
7	5		6		8
Вершина	V		помечена и просмотрена.
	7
Все вершины помечены. Получили цепь V10, V7, V5, V4, V2, V1.
Назначим новые потоки, учитывая, что b= 5.
Метка V10:			+ V , r			= 5. Значит, поток z							= 0 + 5 =5.
Метка V :				7	10	5. Значит, поток z						710
Метка V :		+ V , r =				5. Значит, поток z						= 0 + 5 =5.
7			5		7						57
Метка V :		+ V , r			= 5. Значит, поток z							= 0 + 5 =5..
5			4		5						45		= 0 + 5 =5.
Метка V :		+ V , r			=	10. Значит, поток z							= 0 + 5 =5.
4			2		4							24	= 0 + 5 = 5.
Метка V :		+ V , r			=	10. Значит, поток z							= 0 + 5 = 5.
2			1		2							12
Остальные потоки равны 0.
Стираем все метки и начинаем с начала строить разрезы с новыми потоками.
Вершине	V		присваиваем метку r = ∞.
	1							V .	1
Просматриваем вершину								V .
Γ+ (V ) = {V			, V }.					1
Γ+ (V ) = {V			, V }.
1		2	3
Присваиваем вершине V								метку + V , r =					min (r , q - z			) = min(∞, 10 -5) = 5.		Метка V :		+ V , r		= 5.
Присваиваем вершине V							2			1	2		1	12	12	) = min(∞, 17 -0) = 17.			2	1	2		17.
Присваиваем вершине V								метку + V , r =					min (r , q - z			) = min(∞, 17 -0) = 17.		Метка V :		+ V , r =			17.
Γ- (V ) – пусто.							3			1	3		1	13	13				3		1	3
Γ- (V ) – пусто.
1			помечена и просмотрена.
Вершина	V		помечена и просмотрена.
	1							V .
Просматриваем вершину								V .

												58
Γ+ (V ) = {V			, V }.
2		4	6
Присваиваем вершине V							метку + V , r =				min (r , q - z				) =		min(5, 13 -5) = 5.	Метка V :	+ V , r =		5.
						4		2	4		2	24			24	) = min(5, 23 -0) = 5.		4	2	4	5.
Присваиваем вершине V							метку + V , r		=		min (r , q - z					) = min(5, 23 -0) = 5.		Метка V :	+ V , r =		5.
						6		2	6		2		26		26			6	2	6
Γ- (V2) = {V }. Но V						помечена.
Вершина	1				1
Вершина	V	2	помечена и просмотрена.
		2					V .
Просматриваем вершину							V .
Γ+ (V ) = {V }. Но V							3
Γ+ (V ) = {V }. Но V						помечена.
3		4				4
Γ- (V ) = {V		, V		.	Но V		помечена, а z			= 0..
3	1		5}			1			53
Вершина	V	3	помечена и просмотрена.
		3
Просматриваем вершину							V .
Γ+ (V ) = {V }.							4
Γ+ (V ) = {V }.
4		5
Присваиваем вершине V							метку + V , r			= min (r , q					- z ) = min(5, 5 -5) = 0. Значит, этой вершине метку
не присваиваем.						5		4		5		4	45			45
не присваиваем.
Γ- (V4) ={V2		, V3}. Но V2					помечена, и V3			помечена.
Вершина	V	4	помечена и просмотрена.
		4
Т.к. вершина V не помечена, то её пока не просматриваем.
			5
Просматриваем вершину							V .
Γ+ (V ) = {V , V , V }.							6
Γ+ (V ) = {V , V , V }.
6		5	7		8
Присваиваем вершине V							метку + V , r =				min ( r , q - z					) = min(5, 14 - 0) = 5. Метка V :			+ V , r = 5.
						5		6	5			6	65		65			5	6	5
.Присваиваем вершине V							метку + V , r =				min (r , q - z					) = min(5, 10 - 0) = 5 Метка V :			+ V , r	= 5.
						7		6	7		6		67		67	= min(5, 21 - 0) = 5.		7	6	7	5.
Присваиваем вершине V							метку + V , r = min (r , q						- z		)	= min(5, 21 - 0) = 5.		Метка V :	+ V , r =		5.
						8		6	8		6	68		68				8	6	8
Γ- (V6) = {V2}. Но V2						помечена.
Вершина	V	6	помечена и просмотрена.
		6					V .
Просматриваем вершину							V .
							5
Γ+ (V ) = {V , V }. Но V и V помечены.
5		7	3			3	7	помечены.
Γ- (V ) – {V , V }.					Но V		и V	помечены.
5	4		6			4	6
Вершина	V	5	помечена и просмотрена.
		5
Просматриваем вершину							V .
Γ+ (V ) = {V9 , V }.							7
Γ+ (V ) = {V9 , V }.
7			10
Присваиваем вершине V							метку + V , r =				min (r , q		- z ) = min(5, 8 - 0) =5.					Метка V :	+ V , r = 5.
						9		7	9	=	7		79		79			9	7	9
Присваиваем вершине V							метку + V , r			=	min (r , q				- z		)= min(5, 11 - 5) = 5.
						10		7	10			7	710			710
Все вершины помечены.
Получили цепь V10, V7, V6, V2, V1.
Назначим новые потоки, учитывая, что b = 5.
Метка V10:			+ V , r			= 5. Значит, поток z					= 5 + 5 = 10.
Метка V :				7	10					710
Метка V :		+ V , r			=	5. Значит, поток z				= 0 + 5 = 5.
7			6		7				67
Метка V :		+ V , r = 5. Значит, поток z							= 0 + 5 = 5.
6			2		5			26		= 5 + 5 = 10.
Метка V :		+ V , r =				10. Значит, поток z				= 5 + 5 = 10.
2			1		2				12
Потоки имеют вид
			V		5		V			V					V
			2		5		6			8						10
10			●	5			●			●						●
10				5

														59
V ●						●V				5					10
1						4	5
							5
			●						●	5			●					●
			V						V			V						V
			3						5			7						9
								Рис. 50. Распределение потоков после второй итерации
Стираем все метки и начинаем с начала строить разрезы с новыми потоками.
Вершине		V	присваиваем метку r = ∞.
			1					V .		1
Просматриваем вершину								V .
Γ+ (V ) = {V , V }.									1
Γ+ (V ) = {V , V }.
1			2	3
Присваиваем вершине V									метку + V , r =				min (r , q				- z ) = min(∞, 10 - 10) = 0.		значит, вершине V метка
не присваивается.							2			1	2			1	12			12			2
не присваивается.
Присваиваем вершине V									метку + V , r =				min (r , q - z					) = min(∞, 17 - 10) = 1.	Метка V :	+ V , r	= 17.
Γ- (V ) – пусто.							3			1	3			1	13			13	3	1	3
Γ- (V ) – пусто.
1			помечена и просмотрена.
Вершина		V	помечена и просмотрена.
			1
Т.к. вершина V не помечена, то её пока не просматриваем.
			2					V .
Просматриваем вершину								V .
Γ+ (V ) = {V }.									3
Γ+ (V ) = {V }.
3			4
Присваиваем вершине V									метку + V , r			=		min (r4, q			- z ) = min(17, 11 - 0) = 11. Метка V :			+ V , r = 11.
Γ- (V ) = {V			, V				4			3	4	= 0.			34			34	4	3	4
Γ- (V ) = {V			, V		. Но V			помечена, а z				= 0.
3		1	5}				1				53
Вершина		V	помечена и просмотрена.
			3					V .
Просматриваем вершину								V .
Γ+ (V ) = {V }.									4
Γ+ (V ) = {V }.
4			5
Присваиваем вершине V									метку + V , r			=		min (r , q			- z ) = min(11, 5 - 5) = 0. Значит, этой вершине метку
не присваиваем.								5		4		5		4		45		45
не присваиваем.
Γ- (V4) = {V2			, V3}. Но V3					помечена.
Присваиваем вершине V									метку - V , r = z					= 5.
Метка V		:	- V , r = 5.				2			4	2			24
Метка V	2	:	- V , r = 5.
	2		4		2
Вершина		V	помечена и просмотрена.
			4					V .
Просматриваем вершину								V .
Γ+ (V ) = {V , V }.									2
Γ+ (V ) = {V , V }.
2			4	6
Но V помечена.
4
Присваиваем вершине V									метку + V , r = min (r , q						- z			) =
min(5, 23 - 5) = 5.							6			2	6			2	26		26
min(5, 23 - 5) = 5.					Метка V :				+ V , r =		5.
								6	2	6
Γ- (V2) = {V1}. Но V1							помечена.
Вершина		V	помечена и просмотрена.
			2
Т.к. вершина V не помечена, то её пока не просматриваем.
			5					V .
Просматриваем вершину								V .
Γ+ (V ) = {V , V , V }.									6
Γ+ (V ) = {V , V , V }.
6			5	7		8
Присваиваем вершине V									метку + V , r =					min (r , q			- z ) = min(5, 14 - 5) = 5.

									60
Метка V :	+ V , r = 5.
5		6		5
Присваиваем вершине V						метку + V , r =			min (r , q		- z	) = min(5, 10 - 5) = 5. Метка V :		+ V , r		= 5.
					7	6		7	6	67	67	) = min(5, 21 - 0) = 5.	7	6	7		5.
Присваиваем вершине V						метку + V , r		= min (r , q			- z	) = min(5, 21 - 0) = 5.	Метка V :	+ V , r =			5.
					8	6		8	6	68	68		8		6	8
Γ- (V6) = {V2}. Но V2					помечена.
Вершина	V	помечена и просмотрена.
	6					V .
Просматриваем вершину						V .
						5
Γ+ (V ) = {V , V }. Но V и V помечены.
5	7		3		3	7
Γ- (V ) = {V , V }.				Но V		и V помечены.
5	4	6			4	6
Вершина	V	помечена и просмотрена.
	5					V .
Просматриваем вершину						V .
Γ+ (V ) = {V9 , V }.						7
Γ+ (V ) = {V9 , V }.
7			10
Присваиваем вершине V						метку + V , r =			min (r , q		- z	) = min(5, 8 - 0) = 5. Метка V :		+ V , r		= 5.
					9	7		9	7	79	79		9	7	9
Присваиваем вершине V						метку + V , r		= min (r , q			- z ) = min(5,1110) = 1.
					10	7	10		7	710	710
Γ- (V ) = {V , V }. Но V						и V помечены.
7	5	6			4	6
Все вершины помечены.
Получили цепьV10, V7, V6, V2, V4, V3, V1 .
Имеем b1 = 1, b2 =5. Тогда b = min (b1,b2) = 1.
Назначим новые потоки, учитывая, что b = 1.
Метка V10:		+ V , r			= 5. Значит, поток z				= 10 + 1 = 11.
Метка V :			7	10	5. Значит, поток z				710
Метка V :	+ V , r =				5. Значит, поток z			= 5 + 1 = 6.
7		6		7			67
Метка V :	+ V , r			= 5. Значит, поток z				= 5 + 1 = 6.
6		2		5			26
Метка V :	- V , r			=	5. Значит, поток z			= 5 - 1= 4.
2		4	2				24		= 0 + 1 = 1.
Метка V :	+ V , r			= 11. Значит, поток z					= 0 + 1 = 1.
4		3		4				34	= 0 + 1 = 1.
Метка V :	+ V , r			= 17. Значит, поток z					= 0 + 1 = 1.
3		1		3				13
Потоки имеют вид					V
					V
V2						6						V10
V2			6					V				V10
10			6			6		8
10						6
V1		4
		4
1		V4		5					11
1				5		5			11
		1				5
V		1			V		V					V
V					V		V					V
3					5			7				9
					Рис. 51. Распределение потоков после третьей итерации
Стираем все метки и начинаем с начала строить разрезы с новыми потоками.
Вершине	V	присваиваем метку r = ∞.
	1					1
Просматриваем вершину						V .
Γ+ (V ) = {V		, V }.				1
Γ+ (V ) = {V		, V }.
1	2		3
Присваиваем вершине V						метку + V , r =			min(r , q		- z	) = min(∞,10 - 10) = 0.	Значит, вершине V метка
не присваивается.					2	1		2	1	12	12					2
не присваивается.
Присваиваем вершине V						метку + V , r =			min (r , q		- z	) = min(∞, 17 - 1) = 16.	Метка V : + V , r =				16.
					3	1		3	1	13	13		3		1	3

Γ- (V ) – пусто.

																			61
Вершина	V	помечена и просмотрена.
		1
Т.к. вершина V не помечена, то её пока не просматриваем.
		2
Просматриваем вершину									V .
Γ+ (V ) = {V }.									3
Γ+ (V ) = {V }.
3		4
Присваиваем вершине V									метку + V , r =									min (r4, q			- z	) = min(17, 11 - 1) = 10.	Метка V :			+ V , r = 10 .
Γ- (V ) = {V		, V				4						3			4		= 0.			34		34		4			3		4
Γ- (V ) = {V		, V			. Но V				помечена, а z								= 0.
3	1	5}				1									53
Вершина	V	помечена и просмотрена.
		3							V .
Просматриваем вершину									V .
Γ+ (V ) = {V }.									4
Γ+ (V ) = {V }.
4		5
Присваиваем вершине V									метку + V , r =									min (r , q			- z ) = min(11, 5 - 5) = 0. Значит, этой вершине метку
не присваиваем.								5					4			5			4	45		45
не присваиваем.
Γ- (V ) ={V , V }. Но V помечена.
4	2	3				3			метку - V , r =								z = 4.
Присваиваем вершине V									метку - V , r =								z = 4.
Метка V :						2						4			2			24
Метка V :		- V , r = 4.
2		4			2
Вершина	V	помечена и просмотрена.
		4							V .
Просматриваем вершину									V .
Γ+ (V2) = {V4 , V6}.									2
Γ+ (V2) = {V4 , V6}.
Но V помечена.
4									метку + V , r = min (r , q													) =
Присваиваем вершине V									метку + V , r = min (r , q											- z		) =
min(4, 23 - 6) = 4						6				+ V , r		2			6			2	26		26
min(4, 23 - 6) = 4				Метка V :						+ V , r		= 4.
								6		2		6
Γ- (V2) = {V }. Но V						помечена.
Вершина	1					1
Вершина	V	помечена и просмотрена.
		2
Т.к. вершина V не помечена, то её пока не просматриваем.
		5							V .
Просматриваем вершину									V .
Γ+ (V ) = {V , V , V }.									6
Γ+ (V ) = {V , V , V }.
6		5		7		8			метку + V , r =									min (r , q			- z ) = =min(6 14 - 6) = 6.		Метка V		:	+ V			, r			= 6.
Присваиваем вершине V								5	метку + V , r =									min (r , q			- z ) = =min(6 14 - 6) = 6.		Метка V	5	:	+ V		6	, r	5		= 6.
Присваиваем вершине V								5	метку + V				6			5			6	65		65		5				6		5
Присваиваем вершине V							7		метку + V				6	, r		7	= min(r , q			- z		) =
min(6, 10- 6) = 4.							7		+ V , r				6			7		6	67		67
min(6, 10- 6) = 4.			Метка V :						+ V , r			= 4.
						7				6	7
Присваиваем вершине V									метку + V , r = min (r , q											- z		) = min(6, 21 - 0) = 6.	Метка V :			+ V , r =						6.
Γ- (V ) = {V }. Но V						8						6			8			6	68		68		8				6		8
Γ- (V ) = {V }. Но V						помечена.
6	2					2
Вершина	V	помечена и просмотрена.
		6							V .
Просматриваем вершину									V .
									5
Γ+ (V ) = {V , V }. Но V и V помечены.
5		7		3				3		7	помечены.
Γ- (V ) = {V , V }. Но V									и V		помечены.
5	4		6			4				6
Вершина	V	помечена и просмотрена.
		5							V .
Просматриваем вершину									V .
Γ+ (V ) = {V9 , V }.									7
Γ+ (V ) = {V9 , V }.
7				10					метку + V , r =									min (r , q				) = min(4, 8 - 0) = 4. Метка V :							= 4.
Присваиваем вершине V									метку + V , r =									min (r , q			- z	) = min(4, 8 - 0) = 4. Метка V :				+ V , r			= 4.
						9						7			9			7		79		79	9			7		9			метка
Присваиваем вершине V									метку + V , r								= min (r , q				- z ) = min(4, 1111) = 0. Значит, вершине V										метка
не присваивается.						10						7			10			7		710		710							10
не присваивается.
Γ- (V ) = {V		, V8 , V }. Но V								, V8 и V помечены.

								62
Вершина	V	помечена и просмотрена.
		7
Просматриваем вершину					V8.
Γ+ (V ) = {V7} Вершина				V	помечена.
8					7
Γ- (V ) = {V , V }. Но V					помечен, а z		= 0.
8	6	10		6	10 8
Вершина	V	помечена и просмотрена.
		8
Просматриваем вершину					V .
Γ+ (V ) = {V10}.					9
Γ+ (V ) = {V10}.
9
Присваиваем вершине V					метку + V , r	= min (r , q			- z	) = min(4, 23 - 0) = 4. Метка V	: + V , r	= 4.
Все вершины помечены.				10	9	10	9	910	910	10	9	10
Все вершины помечены.
Получили цепь V10, V9 ,V7, V6, V2, V4, V3, V1 .
Имеем b1 = 4, b 2 =4. Тогда b = min (b 1, b 2) = 4.
Назначим новые потоки, учитывая, что b = 4.
Метка V10:		+ V , r	=	4. Значит, поток z			= 0 + 4 = 4.
		9	10				910

Метка V : + V , r = 4. Значит, поток z = 0 + 4 = 4.

9	7		9	5. Значит, поток z		79
Метка V :	+ V , r =			5. Значит, поток z		= 6 + 4 = 10.
7	6		7			67
Метка V :	+ V , r = 5. Значит, поток z					= 6 + 4 = 10.
6	2		5		26
Метка V :	- V , r		=	5. Значит, поток z		= 4 – 4 = 0.
2	4	2			24
Метка V :	+ V , r = 11. Значит, поток z					= 1 + 4 = 5.
4	3		4			34
Метка V :	+ V , r		= 17. Значит поток z			= 1 + 4 = 5.
3	1		3			13
Потоки имеют вид
	V	10		V		V	V
	2	10		6		8	10
10
V
1					10	11	4
				V4	10	11	4
5	5			V4
	V			5
	3			V5			V
				V5	5	4	V
					5	4	9

Рис. 52. Распределение потоков после четвертой итерации

Стираем все метки и начинаем вновь строить разрезы с новыми потоками. Вершине V присваиваем метку r = ∞.

Просматриваем вершину V .

Γ+ (V ) = {V , V }.

Присваиваем вершине V метку + V , r = min (r , q - z ) = min(∞, 10 – 10 ) = 0. Значит, вершине V метка

не присваивается.

Присваиваем вершине V метку + V , r = min (r , q - z ) = min(∞, 17 - 5) = 12.

Метка V : + V , r = 12.

3 1 3

Γ- (V ) – пусто.

Вершина V помечена и просмотрена.

Т.к. вершина V не помечена, то её пока не просматриваем.

Просматриваем вершину V .

Γ+ (V ) = {V }.

3 4

Присваиваем вершине V метку + V , r = min (r4, q - z ) = min(12, 11 - 5) = 6.

<<< < Предыдущая 1 2 3 4 56 / 76 7 > Следующая >>>

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

#
29.09.20196.09 Mб70Lebedinsky_GOK.doc
#
22.03.20162.05 Mб61lec_Основы парал.программирования.pdf
#
22.03.20162.4 Mб58lec_технология OpenMP.pdf
#
11.03.201592.67 Кб52Lektsia_15_Sovremennye_problemy_zemleustroyt.doc
#
22.03.20161.01 Mб205Lektsia_novaya_1.pdf
#
11.03.20151.15 Mб40Lektsia_po_Diskr.pdf
#
11.03.201577.82 Кб38LESSON 15.doc
#
14.11.2018970.24 Кб43Let's Speak English1.doc
#
11.03.2015970.24 Кб304Lets Speak English(Гарагуля).doc
#
09.11.2018970.24 Кб34Let_39_s_Speak_English_Garagulya.doc
#
11.03.2015711.01 Кб72Marketing (1).docx