Просмотр исходного текста страницы Hardprob/Minimum Ratio-Cut

<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
* Граф <em>G=(V,E)</em>, пропускная способность на ребрах <em>c: E → N</em>, <em>k</em>
товаров, т.е., <em>k</em> пар <m>(s_i,t_i) ∈  V^2</m>, и запросы <em>d<sub>i</sub></em> для каждой пары.
* Найти разрез, т.е. разбиение <em>V</em> на два непересекающихся набора <em>V<sub>1</sub></em> и <em>V<sub>2</sub></em>.
* Минимизировать емкость разреза деленную на объем запросов через этот разрез:

<m>
\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\} ∩  V_1\vert=1}d_i. 
\end{displaymath}
</m>

----
{{hard-problem-on-lab17|{{PAGENAME}}}}
<!-- * {{has-testdata-and-visualization}} -->
<!-- * {{has-pyomo-model}} -->
<!-- * {{has-npc-reduction}} -->
<!-- * {{add-random-fuzzing-tests}} -->
----
<small>
{{ViggoCode|node94}}
<!-- {{GDCode|}} -->
<!-- * [https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%A8%D1%82%D0%B5%D0%B9%D0%BD%D0%B5%D1%80%D0%B0_%D0%BE_%D0%BC%D0%B8%D0%BD%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%BC_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%B5 Задача в википедии] -->
</small>
<!-- end -->

[[Категория:ClassicHardProblems]]