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

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 4: Строка 4:
 
* Найти систему представителей <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 \cap S_i|=1</m>.
 
* Максимизировать «емкость» системы представителей, т.е.  
 
* Максимизировать «емкость» системы представителей, т.е.  
<m>$\sum_{x,y ∈ T}c(x,y) → \min</m>.
+
<m>$\sum_{x,y ∈ T}c(x,y) → \max</m>.
  
 
----
 
----

Версия 10:50, 11 апреля 2023

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

.


Задача в лаб22 (рид-онли просмотр)