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

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

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

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