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

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