Разбиение схемы: сбалансированный подход с минимальным разрезом на базе сетевого потока: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 70: | Строка 70: | ||
== Основные результаты == | == Основные результаты == | ||
''' | '''Биразбиение с минимальным сетевым разрезом на базе оптимального сетевого потока''' | ||
Задача нахождения минимального сетевого разреза в N = (V, E) сводится к задаче нахождения разреза минимальной пропускной способности, которая решается при помощи техники вычисления максимального потока и минимального разреза. [[Транспортная сеть]] N' = (V', E') строится из N = (V, E) следующим образом (см. рис. 4 и 5): | Задача нахождения минимального сетевого разреза в N = (V, E) сводится к задаче нахождения разреза минимальной пропускной способности, которая решается при помощи техники вычисления максимального потока и минимального разреза. [[Транспортная сеть]] N' = (V', E') строится из N = (V, E) следующим образом (см. рис. 4 и 5): | ||
| Строка 78: | Строка 78: | ||
2. Для каждой сетки <math>n = (v; v_1, ..., v_l) \;</math> в N добавить две вершины <math>n_1 \;</math> и <math>n_2 \;</math> в V' и ''мостовое ребро'' <math>bridge(n) = (n_1, n_2) \;</math> в E'. | 2. Для каждой сетки <math>n = (v; v_1, ..., v_l) \;</math> в N добавить две вершины <math>n_1 \;</math> и <math>n_2 \;</math> в V' и ''мостовое ребро'' <math>bridge(n) = (n_1, n_2) \;</math> в E'. | ||
3. Для каждой вершины <math>u \in {v; v_1, ..., v_l} \;</math>, инцидентной сетке n, добавить два ребра <math>(u, n_1) \;</math> и <math>(n_2, u) \;</math> в E'. | 3. Для каждой вершины <math>u \in \{ v; v_1, ..., v_l \} \;</math>, инцидентной сетке n, добавить два ребра <math>(u, n_1) \;</math> и <math>(n_2, u) \;</math> в E'. | ||
4. Положить s источником N', а t – стоком N'. | 4. Положить s источником N', а t – стоком N'. | ||
| Строка 179: | Строка 179: | ||
| 30,0 | | 30,0 | ||
|- | |- | ||
| | | Среднее | ||
| | | | ||
| | | | ||