Hardprob/Maximum Domatic Partition
Материал из DISCOPAL
- Граф G=(V,E).
- Найти разбиение V на непересекающиеся наборы V1, V2, …, Vk такие, что каждый Vi доминирующее множество над G.
- Максимизировать размерность разделения, т.е. число этих непересекающихся множеств вершин Vi.
Код в «maximum-domatic-partition.ipynb» на гитлаб или живьем в лабе
- Задача в базе NP-полных задач Вигго Кана
- Код задачи в книге «ГД» → «GT3»
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.