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

Cite: Утюпин С.Ю.
Устойчивость вершинных покрытий в задаче о вечном вершинном покрытии
Дискретный анализ и исследование операций. 2026. Т.33. №2. С.115-135. DOI: 10.33048/daio.2026.33.863

Dates:

Submitted:	Apr 8, 2026
Accepted:	May 22, 2026
Published print:	Oct 1, 2026
Published online:	Oct 1, 2026

Identifiers: No identifiers

Altmetrics: