Главная Бухгалтерия в кармане Учет расходов Экономия на кадровиках Налог на прибыль Как увеличить активы Основные средства
Главная ->  Гамильтоновы циклы 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 [ 105 ] 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141


4.23) ( + 6.1)

Рис. 11.2в. Потоки и пометки после 3-й итерации. - насыщенные дуги.

(+х„4) Ю

(-л5. 10) 10

/ 4

Рис. 11.2г. Потоки и пометки после 4-й итерации. - насыщенные дуги.



(+ДГ а))


Рис. 11.2д. Потоки и пометки после 5-й итерации. - насыщенные дуги.


i*XtA) (*44) Минимальный разрез

Рис. 11.2е, Потоки и пометки после 6-й итерации, - насыщенные дуги.



Пометка для Xg будет i+x, min [6,25 - 0] = (+5,6),

теперь верпшна х^ помечена и просмотрена.

Пометкой для х, будет {+Хв, min [6,7 - 0]) = (4-а; 6),

теперь верпшна х^ помечена и просмотрена.

Пометкой для х^ будет {+х^, min [6,15 - 4]) = (+7,6).

Шаги 4 и 5.

Новые потоки увеличились следующим образом:

7,9 = 4 + 6 = 10; е,7 = 0 + 6 = 6; кв = 0 + 6 = 6; 3.5 = 4 + 6 = 10; 2.3 = 4 + 6 = 10; ..2 = 4 + 6 = 10;

все остальные значения потока не изменились.

Новый вид потока и пометки вершин до стирания показаны на рис. 11.26.

Продолжая дальше, получаем после каждого прохода алгоритма потоки и пометки, изображенные последовательно на рисунках 11.2в-11.2д. Алгоритм заканчивает работу, когда вершина не может быть помечена; заключительные пометки показаны на рис. 11.2е.

Поток на рис. 11.2е является поэтому максимальным потоком со значением 29, а соответствующий минимальный разрез показан пунктиром на рис. 11.2е.

2.3. Инкрементальные графы

Процесс нахождения в графе G = (X, А) аугментальной цепи потока, когда поток по дугам задается вектором 5, можно рассматривать как процесс нахождения цепи (от s к f) в инкрементальном графе С* () = (Zi*, А^), определяемом следующим образом:

Х^ = Х, A = A,\jAi,

где

А^,={{х^,хШч<Чц} причем пропускная способность дуги {з^, xf) 6 А^ равна qfj =

А^={{х^, хШи>%

причем пропускная способность дуги (xf, xf) А' равна gj =

Процедура расстановки пометок в алгоритме, описанном в разд. 2.1, является теперь не чем иным, как методом построения

21 Н. Кристофидес



1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 [ 105 ] 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141

© 2024 Constanta-Kazan.ru
Тел: 8(843)265-47-53, 8(843)265-47-52, Факс: 8(843)211-02-95