Hardprob/Minimum B-Balanced Cut — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Массовая правка: замена \rightarrow на →) |
StasFomin (обсуждение | вклад) (Массовая правка: замена \in на ∈) |
||
| Строка 10: | Строка 10: | ||
* Минимизировать вес разреза, т.е. <m> | * Минимизировать вес разреза, т.е. <m> | ||
\begin{displaymath} | \begin{displaymath} | ||
| − | \displaystyle\sum_{ | + | \displaystyle\sum_{e∈ \delta(C)} c(e) |
\end{displaymath} | \end{displaymath} | ||
| − | </m>, где <m>\delta(C)=\{e=\{v_1,v_2\}: | + | </m>, где <m>\delta(C)=\{e=\{v_1,v_2\}: e∈ E, v_1∈ C, v_2∈ V-C\}</m> |
---- | ---- | ||
Версия 18:00, 17 апреля 2023
- Граф G=(V,E), веса на вершинах , стоимости на ребрах c: E → N, рациональное число b, .
- Найти разрез C, т.е. подмножество вершин , такой, что
, где where w(V') означает сумму весов вершин в V'.
- Минимизировать вес разреза, т.е. , где
Код в «minimum-b-balanced-cut.ipynb» на гитлаб или живьем в лабе
-
— есть тестовые данные и визуализация. -
— есть Pyomo-формулировка для ЦЛП.
