Идентификация вершин помеченных графов
Рассматривается задача определения мобильным агентом своего положения в среде моделируемой графом с помеченными вершинами. Агент может перемещаться по дугам графа и наблюдать метки вершин. Введены конечные множества слов в алфавите меток, отличающие одну вершину графа от всех других его вершин, назв...
Saved in:
| Published in: | Труды Института прикладной математики и механики |
|---|---|
| Date: | 2010 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут прикладної математики і механіки НАН України
2010
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/123955 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Идентификация вершин помеченных графов / И.С. Грунский, С.В. Сапунов // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2010. — Т. 21. — С. 86-97. — Бібліогр.: 9 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862716723352829952 |
|---|---|
| author | Грунский, И.С. Сапунов, С.В. |
| author_facet | Грунский, И.С. Сапунов, С.В. |
| citation_txt | Идентификация вершин помеченных графов / И.С. Грунский, С.В. Сапунов // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2010. — Т. 21. — С. 86-97. — Бібліогр.: 9 назв. — рос. |
| collection | DSpace DC |
| container_title | Труды Института прикладной математики и механики |
| 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.
|
| first_indexed | 2025-12-07T18:07:13Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-123955 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1683-4720 |
| language | Russian |
| last_indexed | 2025-12-07T18:07:13Z |
| publishDate | 2010 |
| publisher | Інститут прикладної математики і механіки НАН України |
| 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 |
| spellingShingle | Идентификация вершин помеченных графов Грунский, И.С. Сапунов, С.В. |
| title | Идентификация вершин помеченных графов |
| title_alt | Топологічні ідентифікатори вершин позначених графів Topological identifiers of vertices of vertex labeled graphs |
| title_full | Идентификация вершин помеченных графов |
| title_fullStr | Идентификация вершин помеченных графов |
| title_full_unstemmed | Идентификация вершин помеченных графов |
| title_short | Идентификация вершин помеченных графов |
| title_sort | идентификация вершин помеченных графов |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/123955 |
| 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 |