Hardprob/Maximum Directed Cut — различия между версиями

Текущая версия на 16:38, 19 апреля 2023

Направленный граф G=(V,A).
Найти разбиение V на непересекающиеся множества V₁ и V₂.
Максимизировать размер разреза, т.е. число дуг, которые стартуют в V₁, и заканчиваются в V₂.

@@ Строка 1: / Строка 1: @@
-<!-- start -->
+<!-- start -->{{png-image-for-hard-problem|{{PAGENAME}}}}
-* Направленный граф <m>G=\left(V,A\right)</m>.
+* Направленный граф <em>G=(V,A)</em>.
-* Найти разбиение <em>V</em> на непересекающиеся множества <m>V_1</m> и <m>V_2</m>.
+* Найти разбиение <em>V</em> на непересекающиеся множества <em>V<sub>1</sub></em> и <em>V<sub>2</sub></em>.
-* Максимизировать размер разреза, т.е. число дуг, которые стартуют в <m>V_1</m>, и заказчиваются в <m>V_2</m>.
+* Максимизировать размер разреза, т.е. число дуг, которые стартуют в <em>V<sub>1</sub></em>, и заканчиваются в <em>V<sub>2</sub></em>.
 ----
 {{hard-problem-on-lab17|{{PAGENAME}}}}
+* {{has-testdata-and-visualization}}
+* {{has-pyomo-model}} {{vim|819189350}}
+<!-- * {{has-npc-reduction}} -->
+<!-- * {{add-random-fuzzing-tests}} -->
 ----
 <small>
+* «Ориентированная» версия [[Hardprob/Maximum Cut]].
 {{ViggoCode|node87}}
 <!-- {{GDCode|ND16}} -->