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

Cite: Береснев В.Л. , Мельников А.А. , Утюпин С.Ю.
Устойчивость вершинных покрытий в игре с конечным числом шагов
Дискретный анализ и исследование операций. 2024. Т.31. №2. С.28–45. DOI: 10.33048/daio.2024.31.797 РИНЦ

Translated: Beresnev V.L. , Melnikov A.A. , Utyupin S.Y.
Stability of Vertex Covers in a Game with Finitely Many Steps
Journal of Applied and Industrial Mathematics. 2024. V.18. N2. P.206-215. DOI: 10.1134/s1990478924020030 Scopus РИНЦ OpenAlex

Dates:

Submitted:	Feb 26, 2024
Accepted:	Mar 21, 2024
Published print:	Aug 8, 2024
Published online:	Aug 8, 2024

Identifiers:

Elibrary:

68484577

Citing: Пока нет цитирований

Altmetrics: