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

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

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

Повний опис

Збережено в:
Бібліографічні деталі
Видавець:Інститут прикладної математики і механіки НАН України
Дата:2010
Автори: Грунский, И.С., Сапунов, С.В.
Формат: Стаття
Мова:Russian
Опубліковано: Інститут прикладної математики і механіки НАН України 2010
Назва видання:Труды Института прикладной математики и механики
Онлайн доступ:http://dspace.nbuv.gov.ua/handle/123456789/123955
Теги: Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
Цитувати:Идентификация вершин помеченных графов / И.С. Грунский, С.В. Сапунов // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2010. — Т. 21. — С. 86-97. — Бібліогр.: 9 назв. — рос.

Репозиторії

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id irk-123456789-123955
record_format dspace
spelling irk-123456789-1239552017-09-16T03:03:35Z Идентификация вершин помеченных графов Грунский, И.С. Сапунов, С.В. Рассматривается задача определения мобильным агентом своего положения в среде моделируемой графом с помеченными вершинами. Агент может перемещаться по дугам графа и наблюдать метки вершин. Введены конечные множества слов в алфавите меток, отличающие одну вершину графа от всех других его вершин, названные ее идентификаторами. Найдены условия существования, оценки сложности идентификаторов и разработаны методы их построения. Разработаны полиномиальные методы построения и проведения экспериментов по определению начальной вершины графа, основанные на построении идентификаторов всех его вершин. Розглянуто задачу визначення мобільним агентом свого положення в середовищі, яке моделюється за допомогою графа з позначеними вершинами. Агент може пересуватися дугами графа та спостерігати позначки вершин. Введено визначення ідентифікаторів вершин, тобто скінченні множини слів в алфавіті позначок, які відрізняють одну вершину графа від усіх інших його вершин. Знайдено умови існування, оцінки складності ідентифікаторів та розроблено методи їх побудови. Розроблено поліноміальні методи побудови і проведення експериментів по визначенню початкової вершини графа, які грунтуються на побудові ідентифікаторів усіх його вершин. 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. 2010 Article Идентификация вершин помеченных графов / И.С. Грунский, С.В. Сапунов // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2010. — Т. 21. — С. 86-97. — Бібліогр.: 9 назв. — рос. 1683-4720 http://dspace.nbuv.gov.ua/handle/123456789/123955 519.7 ru Труды Института прикладной математики и механики Інститут прикладної математики і механіки НАН України
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
language Russian
description Рассматривается задача определения мобильным агентом своего положения в среде моделируемой графом с помеченными вершинами. Агент может перемещаться по дугам графа и наблюдать метки вершин. Введены конечные множества слов в алфавите меток, отличающие одну вершину графа от всех других его вершин, названные ее идентификаторами. Найдены условия существования, оценки сложности идентификаторов и разработаны методы их построения. Разработаны полиномиальные методы построения и проведения экспериментов по определению начальной вершины графа, основанные на построении идентификаторов всех его вершин.
format Article
author Грунский, И.С.
Сапунов, С.В.
spellingShingle Грунский, И.С.
Сапунов, С.В.
Идентификация вершин помеченных графов
Труды Института прикладной математики и механики
author_facet Грунский, И.С.
Сапунов, С.В.
author_sort Грунский, И.С.
title Идентификация вершин помеченных графов
title_short Идентификация вершин помеченных графов
title_full Идентификация вершин помеченных графов
title_fullStr Идентификация вершин помеченных графов
title_full_unstemmed Идентификация вершин помеченных графов
title_sort идентификация вершин помеченных графов
publisher Інститут прикладної математики і механіки НАН України
publishDate 2010
url http://dspace.nbuv.gov.ua/handle/123456789/123955
citation_txt Идентификация вершин помеченных графов / И.С. Грунский, С.В. Сапунов // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2010. — Т. 21. — С. 86-97. — Бібліогр.: 9 назв. — рос.
series Труды Института прикладной математики и механики
work_keys_str_mv AT grunskijis identifikaciâveršinpomečennyhgrafov
AT sapunovsv identifikaciâveršinpomečennyhgrafov
first_indexed 2023-10-18T20:45:21Z
last_indexed 2023-10-18T20:45:21Z
_version_ 1796151025353097216

Схожі ресурси