![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Определение. Устойчивым множеством графа называется подмножество вершин
, такое что никакие две вершины из
не соединены ребром.
Задача об устойчивом множестве состоит в поиске устойчивого множества с максимальной кардинальностью. Введем бинарную переменную , если вершина
принадлежит искомому устойчивому множеству, и
‑ в противном случае. Тогда модель ДО для решения задачи об устойчивом множестве имеет вид:
при ограничениях
Дата публикования: 2015-01-23; Прочитано: 183 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!