Задача о вершинном покрытии: различия между версиями
| [отпатрулированная версия] | [непроверенная версия] |
Содержимое удалено Содержимое добавлено
MerlIwBot (обсуждение | вклад) м робот удалил: de:Knotenüberdeckungen, Cliquen und stabile Mengen (strong connection between (3) de:Knotenüberdeckungen, Cliquen und stabile Mengen and ru:Задача о клике) изменил: en:Vertex cover |
|||
Строка 18:
: Вопрос: Существует ли вершинное покрытие <math>S</math> для <math>G</math> размера <math>k</math>?
Задача о вершинном покрытии сходна с [[Задача о независимом наборе|задачей о независимом наборе]]. Множество вершин <math>S</math> является вершинным покрытием [[тогда и только тогда]], когда его дополнение <math> \bar S = V \setminus S</math> является
Это следует из того, что граф с <math>n</math> вершинами имеет вершинное покрытие размера <math>k</math> тогда и только тогда, когда данный граф имеет незавимимый набор размера <math>n-k</math>. В этом смысле обе проблемы равнозначны.
| |||