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

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