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

Текущая версия на 22:54, 17 апреля 2023

Непересекающиеся множества S₁, …, S_m, и для любых , чтобы была задана неотрицательная емкость c(x,y).
Найти систему представителей T, т.е. набор T, такой, что для любого i, .
Максимизировать «емкость» системы представителей, т.е.

.

@@ Строка 1: / Строка 1: @@
 <!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
-* Непересекающиеся множества <m>S_1, \ldots, S_m</m>, и для любых <m>i \neq j, x \in S_i, y
+* Непересекающиеся множества <em>S<sub>1</sub>, …, S<sub>m</sub></em>, и для любых <m>i \neq j, x ∈  S_i, y
-\in S_j</m>, чтобы была задана неотрицательная емкость <em>c(x,y)</em>.
+∈  S_j</m>, чтобы была задана неотрицательная емкость <em>c(x,y)</em>.
-* Найти систему представителей <em>T</em>, т.е. набор <em>T</em>, такой, что для любого <em>i</em>, <m>|T \cap S_i|=1</m>.
+* Найти систему представителей <em>T</em>, т.е. набор <em>T</em>, такой, что для любого <em>i</em>, <m>|T ∩  S_i|=1</m>.
 * Максимизировать «емкость» системы представителей, т.е.
 <m>$\sum_{x,y ∈ T}c(x,y)</m>.