Hardprob/Maximum Edge Subgraph — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) (Массовая правка: замена \times на ×) |
||
| Строка 4: | Строка 4: | ||
Максимизировать общий вес ребер подграфа порожденного <em>V'</em>, <m>\begin{displaymath} | Максимизировать общий вес ребер подграфа порожденного <em>V'</em>, <m>\begin{displaymath} | ||
| − | \sum_{(u,v)\in E\cap(V' | + | \sum_{(u,v)\in E\cap(V'× V')} w(u,v). |
\end{displaymath} | \end{displaymath} | ||
</m> | </m> | ||
Версия 11:36, 17 апреля 2023
- Граф G=(V,E) с весами на ребрах w: E → N, положительное целое k.
- Найти подмножество V'⊆V, заданного размера |V'|=k
Максимизировать общий вес ребер подграфа порожденного V',
Задача в лаб22 (рид-онли просмотр)