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

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

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

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
Veröffentlicht in:Труды Института прикладной математики и механики
Datum:2010
Hauptverfasser: Грунский, И.С., Сапунов, С.В.
Format: Artikel
Sprache:Russian
Veröffentlicht: Інститут прикладної математики і механіки НАН України 2010
Online Zugang:https://nasplib.isofts.kiev.ua/handle/123456789/123955
Tags: Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:Идентификация вершин помеченных графов / И.С. Грунский, С.В. Сапунов // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2010. — Т. 21. — С. 86-97. — Бібліогр.: 9 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id nasplib_isofts_kiev_ua-123456789-123955
record_format dspace
spelling Грунский, И.С.
Сапунов, С.В.
2017-09-15T16:55:20Z
2017-09-15T16:55:20Z
2010
Идентификация вершин помеченных графов / И.С. Грунский, С.В. Сапунов // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2010. — Т. 21. — С. 86-97. — Бібліогр.: 9 назв. — рос.
1683-4720
https://nasplib.isofts.kiev.ua/handle/123456789/123955
519.7
Рассматривается задача определения мобильным агентом своего положения в среде моделируемой графом с помеченными вершинами. Агент может перемещаться по дугам графа и наблюдать метки вершин. Введены конечные множества слов в алфавите меток, отличающие одну вершину графа от всех других его вершин, названные ее идентификаторами. Найдены условия существования, оценки сложности идентификаторов и разработаны методы их построения. Разработаны полиномиальные методы построения и проведения экспериментов по определению начальной вершины графа, основанные на построении идентификаторов всех его вершин.
Розглянуто задачу визначення мобільним агентом свого положення в середовищі, яке моделюється за допомогою графа з позначеними вершинами. Агент може пересуватися дугами графа та спостерігати позначки вершин. Введено визначення ідентифікаторів вершин, тобто скінченні множини слів в алфавіті позначок, які відрізняють одну вершину графа від усіх інших його вершин. Знайдено умови існування, оцінки складності ідентифікаторів та розроблено методи їх побудови. Розроблено поліноміальні методи побудови і проведення експериментів по визначенню початкової вершини графа, які грунтуються на побудові ідентифікаторів усіх його вершин.
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.
ru
Інститут прикладної математики і механіки НАН України
Труды Института прикладной математики и механики
Идентификация вершин помеченных графов
Топологічні ідентифікатори вершин позначених графів
Topological identifiers of vertices of vertex labeled graphs
Article
published earlier
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
title Идентификация вершин помеченных графов
spellingShingle Идентификация вершин помеченных графов
Грунский, И.С.
Сапунов, С.В.
title_short Идентификация вершин помеченных графов
title_full Идентификация вершин помеченных графов
title_fullStr Идентификация вершин помеченных графов
title_full_unstemmed Идентификация вершин помеченных графов
title_sort идентификация вершин помеченных графов
author Грунский, И.С.
Сапунов, С.В.
author_facet Грунский, И.С.
Сапунов, С.В.
publishDate 2010
language Russian
container_title Труды Института прикладной математики и механики
publisher Інститут прикладної математики і механіки НАН України
format Article
title_alt Топологічні ідентифікатори вершин позначених графів
Topological identifiers of vertices of vertex labeled graphs
description Рассматривается задача определения мобильным агентом своего положения в среде моделируемой графом с помеченными вершинами. Агент может перемещаться по дугам графа и наблюдать метки вершин. Введены конечные множества слов в алфавите меток, отличающие одну вершину графа от всех других его вершин, названные ее идентификаторами. Найдены условия существования, оценки сложности идентификаторов и разработаны методы их построения. Разработаны полиномиальные методы построения и проведения экспериментов по определению начальной вершины графа, основанные на построении идентификаторов всех его вершин. Розглянуто задачу визначення мобільним агентом свого положення в середовищі, яке моделюється за допомогою графа з позначеними вершинами. Агент може пересуватися дугами графа та спостерігати позначки вершин. Введено визначення ідентифікаторів вершин, тобто скінченні множини слів в алфавіті позначок, які відрізняють одну вершину графа від усіх інших його вершин. Знайдено умови існування, оцінки складності ідентифікаторів та розроблено методи їх побудови. Розроблено поліноміальні методи побудови і проведення експериментів по визначенню початкової вершини графа, які грунтуються на побудові ідентифікаторів усіх його вершин. 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.
issn 1683-4720
url https://nasplib.isofts.kiev.ua/handle/123456789/123955
citation_txt Идентификация вершин помеченных графов / И.С. Грунский, С.В. Сапунов // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2010. — Т. 21. — С. 86-97. — Бібліогр.: 9 назв. — рос.
work_keys_str_mv AT grunskiiis identifikaciâveršinpomečennyhgrafov
AT sapunovsv identifikaciâveršinpomečennyhgrafov
AT grunskiiis topologíčníídentifíkatoriveršinpoznačenihgrafív
AT sapunovsv topologíčníídentifíkatoriveršinpoznačenihgrafív
AT grunskiiis topologicalidentifiersofverticesofvertexlabeledgraphs
AT sapunovsv topologicalidentifiersofverticesofvertexlabeledgraphs
first_indexed 2025-12-07T18:07:13Z
last_indexed 2025-12-07T18:07:13Z
_version_ 1850873828910039040

Ähnliche Einträge