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

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. МАКСИМАЛЬНЫЙ ПОТОК МЕЖДУ КАЖДОЙ ПАРОЙ ВЕРПШН 331

дерево из G, более длинное, чем Т*, что противоречит предположению о максимальности Т*. Таким образом, должно быть равно длине кратчайшего ребра на единственной цепи иа х\ в xj в дереве Т*. Следовательно, древовидный граф Т*, пропускные способности дуг которого равны длинам ребер из G, будет потоково эквивалентен первоначальному графу G. Под потоковой зквивалентностью понимается следующ,ее свойство: если графы G и Т рассматриваются как черные ящики с вершинами выведенными наружр>, то эти два графа будут неразличимы при характе-ризации их с помощью максимальных потоков между парами вершин. Вьппеприведенная конструкция графа Т* является предельно общей и показывает, что для любого графа G всегда существует потоково эквивалентный древовидный граф Т*.

4.2. Конденсация вершин

Предположим, что для графа G = (Х, Г) решена задача о максимальном потоке (от s к t), причем s и f - две случайным образом выбранные вершины. Пусть (Хо, Хо) - минимальный разрез, соответствующий максимальному потоку, и рассмотрим две вершины Xi и х лежащие обе в Хо (или обе лежащие в Хо). Если мы теперь хотим найти fu, максимальный поток из Xj в xj, то все вершины из Хо (или Хо, если х^ и х/ 6 Х^) могут быть сконденсированы в одну вершину Хд коль скоро речь идет только о вычислении потока. Эта конденсация такова, что ребра (Ха, х^), Ха и Хь Х„ заменяются ребрами (Ха, Хд) и любые параллельные ребра между одной и, той же парой вершин (которые могут получиться) заменяются единственным ребром, пропускная способность которого равна сумме пропускных способностей параллельных ребер. На рис. 11.8 (а), (б), (в) иллюстрируется процесс конденсации. Тот факт, что такая конденсация множества Хо возможна, был установлен Гомори и Ху [14, 16], развившими вышеописанный нами метод. В доказательстве показывается, что все вершины Хо должны лежать с одной и той же стороны от минимального разреза {Yqi Yq), отделяющего xj от Xj (т. е. или Хо sY , или Zo S Yo), так что внутренние свойства подграфа (Хо, Г) графа G не влияют на вычисление минимального разреза между

Xi и X}.

4вЗ. Алгоритм построения максимального потока между всеми парами вершин

Алгоритм, описанный в настоящем разделе, порождает дерево Т*, которое потоково эквивалентно неориентированному графу G. Максимальный поток fu между двумя вершинами xj и



< ДГо>


пропускные способ-X > ности ребер


Хо (6)


Хо (в)

Рис. 11.8. (а) Минимальный (от s к t) разрез, (б) Конденсация вершин при вычислении потока от Xi к Xj. (в) Сконденсированный граф.



графа G может быть следующим образом найден по этому дереву:

/i = min [дЦ, quh, qn, . ., gip,], (11.10)

где (xi, xh xk . . ., Xj) - единственная цепь, проходящая по ребрам дерева Т* и ведущая от xi к xj. Каждая вершина х^ из Т* соответствует вершине х^, из G, а qu является пропускной способностью ребра {х'и, xl) из Т*.

Идея алгоритма проста: так как существует дерево Т*, потоково эквивалентное графу G, и так как Т* содержит только п - 1 ребер, то все, что необходимо,- это вычислить пропускные способности п - 1 ребер дерева Т*. Описанный в данном разделе алгоритм вычисляет пропускные способности ребер дерева Т* за ге - 1 этапов. Каждый этап состоит в вычислении потока в графе, получаемом последовательно из ранее построенного графа с помощью конденсации, как об этом говорилось выше в разд. 4.2.

4.3.1. Описание алгоритма. Так как алгоритм порождает дерево Т* постепенно и так как на любом из (ге - 1) этапов действия алгоритма вершины из Т* могут быть на самом деле множествами вершин из G, то мы будем, во избежание недоразумений, называть вершины из G G-вершинами, а вершины из Т* - Т*-верши-нами. Ниже дается достаточно комментариев, чтобы сделать алгоритм понятным.

Шаг 1. Положить = X, N = 1.

На любом этапе Т* является графом, определенным N 7*-вер-шинами Sy, S2, . . ., Sj, и каждая из них соответствует некоторому множеству G-вершин. Вначале граф Т* состоит из единственной вершины Sy.

Шаг 2. Найти множество S* {S, S, ., Sj}, содержащее более чем одну G-вершину. Если такого не существует, то перейти к шагу 6, в противном случае - к шагу 3.

Шаг 3. Если бы S* было удалено из Т*, то дерево распалось бы на некоторое число поддеревьев (связанных компонент). Сконденсировать 7*-вершины в каждом поддереве в одну вершину и образовать сконденсированный граф. Взять любые две вершины Xi и Xj € 5* и найти минимальный разрез (Zq, Х^) в G, отделяющий Xi от Xj, с помощью вычисления максимального потока (от Xi к х,).

Шаг 4. Удалить из Т* Т*-вершину S* вместе с ребрами, ей инцидентными, и заменить ее на две 7*-вершины, составленные из G-вершин множеств 5* П Zo и 5* П Zg, и на ребро между ними с пропускной способностью V (Zo, Zq). Итак, для всех Т*-вершин Si, которые до замены были инцидентны 5* (скажем, с пропускной способностью ребра с?), добавить к Т* ребро {Si, S* П Zo), если Si cz Zo, или же к Т* добавить ребро



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