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

Версия 16:07, 19 апреля 2023

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

@@ Строка 2: / Строка 2: @@
 * Направленный граф <em>G=(V,A)</em>.
 * Найти разбиение <em>V</em> на непересекающиеся множества <em>V<sub>1</sub></em> и <em>V<sub>2</sub></em>.
-* Максимизировать размер разреза, т.е. число дуг, которые стартуют в <em>V<sub>1</sub></em>, и заказчиваются в <em>V<sub>2</sub></em>.
+* Максимизировать размер разреза, т.е. число дуг, которые стартуют в <em>V<sub>1</sub></em>, и заканчиваются в <em>V<sub>2</sub></em>.
 ----
 {{hard-problem-on-lab17|{{PAGENAME}}}}