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

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

(Si, S* П Хо), если Si с= Хо- Пропускные способности ребер и в том и в другом случае взять равными с?.

Замечание. Как уже было отмечено в разд. 4.2, Гомори и Ху [14] показали, что Si лежит целиком или в Хд, или в Хо, так что возможны только два указанных выше случая.

Шаг 5. Положить 7V = 7V + 1. Вершины из Т* являются теперь множествами G-вершин S, S, . . ., S* f\ Хо, S* [} f]Xo, . . ., Sn, где S* заменена двумя 7*-вершинами S* fl Хо и 5* П 0 объяснялось выше. Перейти к шагу 2.

Шаг 6. Останов. Т* будет теперь требуемым потоково эквивалентным графу G деревом, и его Г*-вершины являются теперь единственными G-вершинами. Пропускные способности ребер из Г* соответствуют значениям (п - 1) независимых разрезов в графе G. Равенство (11.10) можно теперь использовать для вычисления fi} (для любых Xi, Xj 6 X) непосредственно из Т*.

То обстоятельство, что вышеприведенный алгоритм дает оптимальный результат, следует непосредственно из свойств минимальных разрезов и свойств потоково эквивалентного графу G дерева, приведенных выше в разд. 4.1 и 4.2. Формальное доказательство можно найти в книге Ху [16].

4.4. Пример

Рассмотрим неориентированный граф G, изображенный на рис. 11.9. Пропускные способности показаны цифрами, стоящими


Рис. 11.9. Граф из примера 4.4.



У ребер. Нужно найти максимальный поток между каждой парой вершин графа G. Применим вышеописанный алгоритм.

Шаг 1. Si ={xi, Xss, Хз, х^, х^, xJ; N = i. Шаг 2. S* = S.

Шаг 3. Граф не может быть сконденсирован. Берем (произвольно) Xi = Ху ж Xj = Xj. Вычисляя максимальный поток (от х^ к х^), найдем, что минимальным разрезом будет {Х^, Х^, гд& Хо ={xi, 5, Xg} иХ ={2, Хз, xJ, а значение разреза равно 24.

Шаг 4. Дерево Т* и пропускные способности его ребер изображены на рис. 11.10а.

Шаг 5. N = 2 (т. е. Т* имеет теперь, как показано на рис. 11.10а, две вершины: Sy и S.

Шаг 2. Берем S* = S.

Шаг 3. Выбираем (произвольно) Xj = Xj и Х/ = х^. Полученный затем сконденсированный граф изображен на рис. 11.106. Вычисляя для него максимальный поток, порождаем минимальный разрез (Хо, Хд), где Хо ={хз и Хо -{ху, Хь, х^, х^, xJ. Значе-

ние этого разреза равно 23.

Шаг 4. 7*-вершина S ={х2, Хз, х^ заменяется теперь двумя новыми 7*-вершинами {х^ и {х^, х^} и ребром между ними со значением 23. Так KaK ! cz: Хо, то ребро {Sy, S) удаляется и заменяется ребром {Sy, S3), где S3 ={х2, х^}.

Шаг 5. N = 3 (т. е. Т* имеет теперь 3 вершины, как показано на рис. И.Юв).

Шаг 2. Возьмем S* = S3.

Шаг 3. Берем Xi = х^ и Xj = Х3. Сконденсированный граф изображен на рис. 11.10г. Минимальный разрез со значением 30 равен (Хо, Хо), где Хо ={х^ и Хо ={a:s, Хз, Ху, х^, Xj}.

Шаг 4. 7*-вершина S3 ={2, х^) теперь заменяется двумя новыми 7*-вершинами {s} и {х^}, а новое дерево показано на рис. И.Юд.

Продолжая подобным образом и беря S* = Sy, последовательно получаем потоково эквивалентные деревья, изображенные на рисунках И.Юе, ж, з, и. Если использовать рис. 11.10(и), то матрицу максимальных потоков [/jj] первоначального графа можно





Рис. 11.10а, Т* после 1-го этапа.


Рис. 11.106 и г. Сконденсированный граф после 2-го (б) и 3-го (г) этапов,

---(Т^ 1.-4}

©13} Рис. И.Юв. Т* после 2-го этапа.

М { 4)


Рис. 11.10д. Г* после 3-го этапа.



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