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

Cite: Утюпин С.Ю.
Устойчивость вершинных покрытий в игре с конечным числом шагов
Международная научная студенческая конференция 2024 17-23 апр. 2024