Идентификация вершин помеченных графов

Abstract

Рассматривается задача определения мобильным агентом своего положения в среде моделируемой графом с помеченными вершинами. Агент может перемещаться по дугам графа и наблюдать метки вершин. Введены конечные множества слов в алфавите меток, отличающие одну вершину графа от всех других его вершин, названные ее идентификаторами. Найдены условия существования, оценки сложности идентификаторов и разработаны методы их построения. Разработаны полиномиальные методы построения и проведения экспериментов по определению начальной вершины графа, основанные на построении идентификаторов всех его вершин.

Розглянуто задачу визначення мобільним агентом свого положення в середовищі, яке моделюється за допомогою графа з позначеними вершинами. Агент може пересуватися дугами графа та спостерігати позначки вершин. Введено визначення ідентифікаторів вершин, тобто скінченні множини слів в алфавіті позначок, які відрізняють одну вершину графа від усіх інших його вершин. Знайдено умови існування, оцінки складності ідентифікаторів та розроблено методи їх побудови. Розроблено поліноміальні методи побудови і проведення експериментів по визначенню початкової вершини графа, які грунтуються на побудові ідентифікаторів усіх його вершин.

The self-location problem for mobile agent in the topological environment is considered. Environment is modeled by the vertex labeled graph. The agent can move by graph edges and observe labels of vertices. A finite sets of words over the vertex labels alphabet distinguishing a given vertex from other called vertex identifier is proposed. Existence conditions and complexity estimations for vertex identifiers are discovered and constructions methods are developed. Polynomial constructions and realizations methods for experiments detecting the vertex where the mobile agent start walking based on all vertices’ identifiers construction are proposed.