Устойчивость вершинных покрытий в игре с конечным числом шагов

Задача о вечном вершинном покрытии является вариантом задачи о вершинном покрытии графа и может рассматриваться как динамическая игра двух сторон (Атакующего и Защитника) с бесконечным числом шагов. На каждом шаге имеется размещение охранников по вершинам графа, образующее вершинное покрытие. Атакующий выбирает для атаки одно из рёбер графа, а Защитник должен переместить охранника вдоль атакованного ребра из одной вершины в другую. Кроме того, Защитник может переместить любое подмножество остальных охранников из вершин, в которых они находились до атаки, в одну из незанятых соседних вершин, чтобы получить новое вершинное покрытие.
В статье описана процедура, позволяющая ответить на вопрос, существует ли выигрышная стратегия для Защитника, позволяющая защищать вершинное покрытие в течении заданного числа шагов. Для построения стратегии Защитника задача представляется в виде динамической игры Штакельберга, на каждом шаге которой взаимодействие противоборствующих сторон формализуется как двухуровневая задача математического программирования. Ил. 6, библиогр. 11.