Обсуждение:Задача о вершинном покрытии
Последнее сообщение: 15 лет назад от 139.18.181.124 в теме «Untitled»
Эта статья тематически связана с вики-проектом «Математика», цель которого — создание и улучшение статей по темам, связанным с математикой. Вы можете её отредактировать, а также присоединиться к проекту, принять участие в его обсуждении и поработать над требуемыми статьями. |
Untitled править
Некорректно сформулированоное удаляю - надо переделать: Вершинное покрытие для неориентированного графа G = (V,E) это множество его вершин S, такое что, у каждого ребра хотя бы один из концов входит в S. Иными словами, для каждого ребра ab в E, один из a должен b должен быть элементом S. 139.18.181.124 00:33, 13 января 2009 (UTC)Domat
В данной постановке - NP-трудная, а не NP-полная.