4430
правок
Разбиение схемы: сбалансированный подход с минимальным разрезом на базе сетевого потока: различия между версиями
Материал из WEGA
Разбиение схемы: сбалансированный подход с минимальным разрезом на базе сетевого потока (посмотреть исходный код)
Версия от 12:14, 17 апреля 2017
, 17 апреля 2017→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 63: | Строка 63: | ||
== Основные результаты == | == Основные результаты == | ||
Сбалансированное биразбиение с минимальным сетевым разрезом на базе оптимального сетевого потока | '''Сбалансированное биразбиение с минимальным сетевым разрезом на базе оптимального сетевого потока''' | ||
Задача нахождения минимального сетевого разреза в N = (V, E) сводится к задаче нахождения разреза минимальной пропускной способности, которая решается при помощи техники вычисления максимального потока и минимального разреза. [[Транспортная сеть]] N' = (V', E') строится из N = (V, E) следующим образом (см. рис. 4 и 5): | |||
1. V' содержит все вершины из V. | |||
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'. | |||
4. Положить s источником N', а t – стоком N'. | |||
6. Для вершины v | 5. Присвоить единичную [[пропускная способность|пропускную способность]] всем мостовым ребрам и бесконечную пропускную способность – всем остальным ребрам в E'. | ||
6. Для вершины <math>v \in V\ \;</math>, соответствующей вершине в V, w(v) обозначает вес v в N. Для вершины <math>u \in V' \;</math>, отщепленной от сетки, w(u) = 0. | |||
