Задача поиска устойчивого множества в графе

Определение. Устойчивым множеством графа называется подмножество вершин , такое что никакие две вершины из не соединены ребром.

Задача об устойчивом множестве состоит в поиске устойчивого множества с максимальной кардинальностью. Введем бинарную переменную , если вершина принадлежит искомому устойчивому множеству, и ‑ в противном случае. Тогда модель ДО для решения задачи об устойчивом множестве имеет вид:

при ограничениях