Hardprob/Minimum Feedback Vertex Set — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Массовая правка: замена {{hard-problem-on-lab17|{{PAGENAME}}}} на {{hard-problem-on-lab17|{{PAGENAME}}}} <!-- * {{has-testdata-and-visualization}} --> <!-- * {{has-pyomo-model}} --> <!-- * {{has-npc-reduction}} --> <!-- * {{add-random-fuzzing-tests}} -->) |
StasFomin (обсуждение | вклад) (Массовая правка: замена <m>\vert V'\vert</m> на <em>|V'|</em>) |
||
| Строка 6: | Строка 6: | ||
содержит по крайней мере одну вершину из каждого направленного цикла в <em>G</em>. | содержит по крайней мере одну вершину из каждого направленного цикла в <em>G</em>. | ||
| − | Минимизировать размерность этого подмножества, < | + | Минимизировать размерность этого подмножества, <em>|V'|</em>. |
---- | ---- | ||
Версия 06:11, 17 апреля 2023
Направленный граф .
Найти множество вершин разрезающее циклы, т.е. подмножество , такое, что V' содержит по крайней мере одну вершину из каждого направленного цикла в G.
Минимизировать размерность этого подмножества, |V'|.
Задача в лаб17 (рид-онли просмотр)
- Задача в базе NP-полных задач Вигго Кана
- Код задачи в книге «ГД» → «GT7»