Эта публикация цитируется в 8 статьях

Прикладная математика

The fault-tolerant metric dimension of the king's graph

[Отказоустойчивая метрическая размерность графа ходов шахматного короля]

R. V. Voronov

Petrozavodsk State University, 33, Lenina pr., Petrozavodsk, 185910, Russian Federation

Аннотация: В некотором приближении аналогом задачи оптимального размещения точек доступа системы внутреннего позиционирования служит задача определения метрической размерности графа и построения его разрешающего множества. Пусть вершина $w$ неориентированного связного графа $G$ различает вершины $u$ и $v$ графа $G$, если расстояние между вершинами $w$ и $u$ отличается от расстояния между вершинами $w$ и $v$. Подмножество $W$ вершин графа $G$ называется разрешающим, если для каждой пары вершин $u$ и $v$ графа $G$ найдется различающая их вершина $w \in W$. Метрическая размерность графа — это минимальное число вершин в разрешающем подмножестве. Точкам доступа системы внутреннего позиционирования соответствует разрешающее множество вершин графа, а минимально необходимому числу точек доступа — метрическая размерность графа. Разрешающее множество называется отказоустойчивым, если оно остается разрешающим, даже если из него удалить любую его вершину. Отказоустойчивая метрическая размерность графа — это минимальное число вершин в отказоустойчивом разрешающем подмножестве, что в системе внутреннего позиционирования соответствует возможности определения местоположения объекта даже в случае потери информации от одной из точек доступа. Рассмотрен один частный случай графа — сильное произведение двух простых цепей, называемое иначе графом ходов шахматного короля. Установлена верхняя граница для отказоустойчивой метрической размерности графа ходов короля и приведена формула для одного частного случая. Библиогр. 20 назв. Ил. 2.

Ключевые слова: отказоустойчивая метрическая размерность, сильное произведение графов, граф ходов короля, точки доступа системы внутреннего позиционирования.

УДК: 519.8

Поступила: 11 декабря 2016 г.
Принята к печати: 8 июня 2017 г.

Язык публикации: английский

DOI: 10.21638/11701/spbu10.2017.302

Реферативные базы данных:

•