Hardprob/Maximum Independent Sequence

Ссылки сюда (2) →

• Граф G=(V,E).
• Найти независимую последовательность в G, т.е. последовательность независимых вершин, v₁, …, v_m, таких, что для любого i < m, если вершина соседствует с , но то оно не будет соседствовать ни с одним v_j для любого j ≤ i.
• Максимизировать «m» — длину этой последовательности.

---

Код в «maximum-independent-sequence.ipynb» на гитлаб или живьем в лабе

---

• Задача в базе NP-полных задач Вигго Кана

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.