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

Текущая версия на 12:24, 22 сентября 2023

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

@@ Строка 1: / Строка 1: @@
-<!-- start -->
+<!-- start -->{{png-image-for-hard-problem|{{PAGENAME}}}}
-* Граф <m>G=\left(V,E\right)</m>.
+* Граф <em>G=(V,E)</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|819175567}}
+<!-- * {{has-npc-reduction}} -->
+<!-- * {{add-random-fuzzing-tests}} -->
 ----
 <small>