О высоте идентификаторов вершин помеченных графов
Рассматривается задача различения вершин помеченного графа по ассоциированным с ними языкам в алфавите меток. Показано, что верхняя оценка длины слова, различающего две вершины графа, детерминированного по разметке окрестностей вершин, равна половине числа его вершин. Показано также, что в языке...
Збережено в:
| Опубліковано в: : | Искусственный интеллект |
|---|---|
| Дата: | 2013 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут проблем штучного інтелекту МОН України та НАН України
2013
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/85116 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | О высоте идентификаторов вершин помеченных графов / С.В. Сапунов, В.Ю. Пилипенко // Искусственный интеллект. — 2013. — № 3. — С. 444–454. — Бібліогр.: 8 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-85116 |
|---|---|
| record_format |
dspace |
| spelling |
Сапунов, С.В. Пилипенко, В.Ю. 2015-07-19T15:12:25Z 2015-07-19T15:12:25Z 2013 О высоте идентификаторов вершин помеченных графов / С.В. Сапунов, В.Ю. Пилипенко // Искусственный интеллект. — 2013. — № 3. — С. 444–454. — Бібліогр.: 8 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/85116 519.7 Рассматривается задача различения вершин помеченного графа по ассоциированным с ними языкам в алфавите меток. Показано, что верхняя оценка длины слова, различающего две вершины графа, детерминированного по разметке окрестностей вершин, равна половине числа его вершин. Показано также, что в языке каждой из любых двух различных вершин есть слово, отличающее одну вершину от другой, и его длина меньше числа вершин графа. Найдены оценки высоты конечных множеств слов, отличающих одну вершину графа от всех других его вершин (т.н. идентификаторов). Розглядається задача розрізнення вершин позначеного графа за асоційованими з ними мовами в алфавіті позначок. Визначено, що верхня оцінка довжини слова, що розрізнює дві вершини графа, детермінованого за розміткою околів вершин, дорівнює половині від кількості його вершин. Визначено також, що у мові кожної з двох різних вершин є слово, яке відрізняє одну вершину від іншої, і його довжина менша, ніж кількість вершин у графі. Знайдено оцінки висоти скінчених множин слів, що відрізняють одну вершину графа від інших його вершин (т.з. ідентифікаторів). The problem of vertex distinguishing on vertex labeled graphs is considered. Two vertices are called distinguishable if associated languages over the alphabet of labels are different. A linear upper bound of vertex distinguishing word length equal to half of the number of all vertices is obtained. It is shown that at both languages of two different vertices there are distinguishing words and their lengths are less then number of all vertices. Upper bounds of height of finite sets of words over the vertex labels alphabet distinguishing a given vertex from other (i.e. identifiers) are obtained. ru Інститут проблем штучного інтелекту МОН України та НАН України Искусственный интеллект Интеллектуальные робототехнические системы О высоте идентификаторов вершин помеченных графов Про висоту ідентифікаторів вершин графів з позначеними вершинами On height of vertex identifiers 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 |
Сапунов, С.В. Пилипенко, В.Ю. |
| topic |
Интеллектуальные робототехнические системы |
| topic_facet |
Интеллектуальные робототехнические системы |
| publishDate |
2013 |
| language |
Russian |
| container_title |
Искусственный интеллект |
| publisher |
Інститут проблем штучного інтелекту МОН України та НАН України |
| format |
Article |
| title_alt |
Про висоту ідентифікаторів вершин графів з позначеними вершинами On height of vertex identifiers of vertex labeled graphs |
| description |
Рассматривается задача различения вершин помеченного графа по ассоциированным с ними языкам в
алфавите меток. Показано, что верхняя оценка длины слова, различающего две вершины графа,
детерминированного по разметке окрестностей вершин, равна половине числа его вершин. Показано
также, что в языке каждой из любых двух различных вершин есть слово, отличающее одну вершину
от другой, и его длина меньше числа вершин графа. Найдены оценки высоты конечных множеств
слов, отличающих одну вершину графа от всех других его вершин (т.н. идентификаторов).
Розглядається задача розрізнення вершин позначеного графа за асоційованими з ними мовами в алфавіті
позначок. Визначено, що верхня оцінка довжини слова, що розрізнює дві вершини графа, детермінованого за
розміткою околів вершин, дорівнює половині від кількості його вершин. Визначено також, що у мові кожної
з двох різних вершин є слово, яке відрізняє одну вершину від іншої, і його довжина менша, ніж кількість
вершин у графі. Знайдено оцінки висоти скінчених множин слів, що відрізняють одну вершину графа від
інших його вершин (т.з. ідентифікаторів).
The problem of vertex distinguishing on vertex labeled graphs is considered. Two vertices are called distinguishable if
associated languages over the alphabet of labels are different. A linear upper bound of vertex distinguishing word
length equal to half of the number of all vertices is obtained. It is shown that at both languages of two different
vertices there are distinguishing words and their lengths are less then number of all vertices. Upper bounds of height
of finite sets of words over the vertex labels alphabet distinguishing a given vertex from other (i.e. identifiers) are
obtained.
|
| issn |
1561-5359 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/85116 |
| citation_txt |
О высоте идентификаторов вершин помеченных графов / С.В. Сапунов, В.Ю. Пилипенко // Искусственный интеллект. — 2013. — № 3. — С. 444–454. — Бібліогр.: 8 назв. — рос. |
| work_keys_str_mv |
AT sapunovsv ovysoteidentifikatorovveršinpomečennyhgrafov AT pilipenkovû ovysoteidentifikatorovveršinpomečennyhgrafov AT sapunovsv provisotuídentifíkatorívveršingrafívzpoznačenimiveršinami AT pilipenkovû provisotuídentifíkatorívveršingrafívzpoznačenimiveršinami AT sapunovsv onheightofvertexidentifiersofvertexlabeledgraphs AT pilipenkovû onheightofvertexidentifiersofvertexlabeledgraphs |
| first_indexed |
2025-12-07T18:02:15Z |
| last_indexed |
2025-12-07T18:02:15Z |
| _version_ |
1850873516183781376 |