Просмотр исходного текста страницы Hardprob/Maximum Balanced Connected Partition

<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->

Связный граф <em>G=(V,E)</em> с неотрицательными весами на вершинах <em>w: V → N</em>.

Найти разбиение вершин <em>V</em> на непустые непересекающиеся множества <em>(V<sub>1</sub>, V<sub>2</sub>)</em>, такие,
что подграфы порожденные <em>V<sub>1</sub></em> и <em>V<sub>2</sub></em> являются связными.

Минимизировать дисбаланс разбиения, т.е. 
<m>\min\{w(V_1), w(V_2)\}</m>, где <m>w(V')=\sum_{v∈  V'} w(v)</m>

Максимизировать размер этого разбиения.

----
{{hard-problem-on-lab17|{{PAGENAME}}}}
<!-- * {{has-testdata-and-visualization}} -->
<!-- * {{has-pyomo-model}} -->
<!-- * {{has-npc-reduction}} -->
<!-- * {{add-random-fuzzing-tests}} -->
----
<small>

{{ViggoCode|node27}}
<!-- {{GDCode|}} -->
<!-- * [    Задача в википедии] -->
</small>
<!-- end -->

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