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

Версия 22:33, 17 апреля 2023

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

@@ Строка 1: / Строка 1: @@
 <!-- start -->{{png-image-for-hard-problem|{{PAGENAME}}}}
 * Граф <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>.
 ----