Обсуждение:NP-полнота задачи о независимом множестве

Материал из Викиконспекты
Перейти к: навигация, поиск

<<Задача о независимом множестве(IND) решает вопрос о том, содержит ли граф G подграф H размером k, никакая пара вершин в котором не соединена ребром.>> -- несколько раз соврал, читай еще.

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Обсуждение:NP-полнота_задачи_о_независимом_множестве&oldid=180»