Hardprob/Minimum Ratio-Cut — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Массовая правка: замена \in на ∈) |
StasFomin (обсуждение | вклад) (Массовая правка: замена \cap на ∩) |
||
| Строка 7: | Строка 7: | ||
<m> | <m> | ||
\begin{displaymath}\sum_{v_1∈ V_1, v_2∈ V_2 \atop (v_1,v_2) ∈ E}c(v_1,v_2)/ | \begin{displaymath}\sum_{v_1∈ V_1, v_2∈ V_2 \atop (v_1,v_2) ∈ E}c(v_1,v_2)/ | ||
| − | \sum_{i:\vert\{s_i,t_i\} | + | \sum_{i:\vert\{s_i,t_i\} ∩ V_1\vert=1}d_i. |
\end{displaymath} | \end{displaymath} | ||
</m> | </m> | ||
Версия 21:49, 17 апреля 2023
- Граф G=(V,E), пропускная способность на ребрах c: E → N, k
товаров, т.е., k пар , и запросы для каждой пары.
- Найти разрез, т.е. разбиение V на два непересекающихся набора и .
- Минимизировать емкость разреза деленную на объем запросов через этот разрез:
Задача в лаб17 (рид-онли просмотр)