Лекция: Задачи упаковки вершин

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

где если вершина в упаковке и ‑ в противном случае.

Модель упаковки вершин с максимальным весом имеет вид:

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

Модель упаковки вершин с максимальной кардинальностью имеет вид:

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

(кликовое ограничение, то есть из каждой максимальной клики может быть выбрано не более одной вершины)