Hardprob/Minimum K-Cut — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Массовая правка: замена <m>G=\left(V,E\right)</m> на <em>G=(V,E)</em>) |
StasFomin (обсуждение | вклад) |
||
| (не показано 5 промежуточных версий этого же участника) | |||
| Строка 1: | Строка 1: | ||
| − | <!-- start --> | + | <!-- start -->{{png-image-for-hard-problem|{{PAGENAME}}}} |
| − | * Граф <em>G=(V,E)</em>, веса на ребрах < | + | * Граф <em>G=(V,E)</em>, веса на ребрах <em>w: E → N</em>, целое <m>k∈ [2..\vert V\vert]</m>. |
| − | * Найти разбиение <em>V</em> на <em>k</em> непересекающихся множеств <m>F=\{C_1,C_2, | + | * Найти разбиение <em>V</em> на <em>k</em> непересекающихся множеств <m>F=\{C_1,C_2,…,C_k\}</m>. |
* Минимизировать сумму весов между ребрами, которые между этими множествами <m>\begin{displaymath} | * Минимизировать сумму весов между ребрами, которые между этими множествами <m>\begin{displaymath} | ||
\displaystyle\sum_{i=1}^{k-1}\displaystyle\sum_{j=i+1}^k | \displaystyle\sum_{i=1}^{k-1}\displaystyle\sum_{j=i+1}^k | ||
| − | \displaystyle\sum_{ | + | \displaystyle\sum_{v_1∈ C_i\atop v_2∈ C_j} w(\{v_1,v_2\}). |
\end{displaymath}</m> | \end{displaymath}</m> | ||
| − | |||
| − | |||
---- | ---- | ||
{{hard-problem-on-lab17|{{PAGENAME}}}} | {{hard-problem-on-lab17|{{PAGENAME}}}} | ||
| − | + | * {{has-testdata-and-visualization}} | |
| − | + | * {{has-pyomo-model}} {{vim|819413641}} | |
<!-- * {{has-npc-reduction}} --> | <!-- * {{has-npc-reduction}} --> | ||
<!-- * {{add-random-fuzzing-tests}} --> | <!-- * {{add-random-fuzzing-tests}} --> | ||
Текущая версия на 08:14, 20 апреля 2023
- Граф G=(V,E), веса на ребрах w: E → N, целое .
- Найти разбиение V на k непересекающихся множеств .
- Минимизировать сумму весов между ребрами, которые между этими множествами
Задача в лаб22 (рид-онли просмотр)
-
— есть тестовые данные и визуализация. -
— есть Pyomo-формулировка для ЦЛП. 📺 видео 📺
