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

<!-- start -->{{png-image-for-hard-problem|{{PAGENAME}}}}
* Граф <em>G=(V,E)</em>, веса на вершинах <m>w:V \rightarrow N</m>, стоимости на ребрах <m>c:E \rightarrow N</m>, рациональное число <em>b</em>, <m>0 < b \le 1/2</m>.
* Найти разрез <em>C</em>, т.е. подмножество вершин <m>C \subseteq V</m>, такой, что 
<m>
\begin{displaymath}
\min\{w(C),w(V-C)\}\ge b\cdot w(V),
\end{displaymath}
</m>, где where <em>w(V')</em> означает сумму весов вершин в <em>V'</em>.

* Минимизировать вес разреза, т.е. <m>
\begin{displaymath}
\displaystyle\sum_{e\in\delta(C)} c(e)
\end{displaymath}
</m>, где <m>\delta(C)=\{e=\{v_1,v_2\}: e\in E, v_1\in C, v_2\in V-C\}</m>

----
{{hard-problem-on-lab17|{{PAGENAME}}}}
* {{has-testdata-and-visualization}}
* {{has-pyomo-model}}
<!-- * {{has-npc-reduction}} -->
<!-- * {{add-random-fuzzing-tests}} -->
----
<small>
{{ViggoCode|node95}}
<!-- {{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]]