О высоте идентификаторов вершин помеченных графов
Рассматривается задача различения вершин помеченного графа по ассоциированным с ними языкам в
 алфавите меток. Показано, что верхняя оценка длины слова, различающего две вершины графа,
 детерминированного по разметке окрестностей вершин, равна половине числа его вершин. Показано&...
Gespeichert in:
| Veröffentlicht in: | Искусственный интеллект |
|---|---|
| Datum: | 2013 |
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут проблем штучного інтелекту МОН України та НАН України
2013
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/85116 |
| 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: | О высоте идентификаторов вершин помеченных
 графов / С.В. Сапунов, В.Ю. Пилипенко // Искусственный интеллект. — 2013. — № 3. — С. 444–454. — Бібліогр.: 8 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862716065501413376 |
|---|---|
| author | Сапунов, С.В. Пилипенко, В.Ю. |
| author_facet | Сапунов, С.В. Пилипенко, В.Ю. |
| citation_txt | О высоте идентификаторов вершин помеченных
 графов / С.В. Сапунов, В.Ю. Пилипенко // Искусственный интеллект. — 2013. — № 3. — С. 444–454. — Бібліогр.: 8 назв. — рос. |
| collection | DSpace DC |
| container_title | Искусственный интеллект |
| 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.
|
| first_indexed | 2025-12-07T18:02:15Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-85116 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1561-5359 |
| language | Russian |
| last_indexed | 2025-12-07T18:02:15Z |
| publishDate | 2013 |
| publisher | Інститут проблем штучного інтелекту МОН України та НАН України |
| 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 |
| spellingShingle | О высоте идентификаторов вершин помеченных графов Сапунов, С.В. Пилипенко, В.Ю. Интеллектуальные робототехнические системы |
| title | О высоте идентификаторов вершин помеченных графов |
| title_alt | Про висоту ідентифікаторів вершин графів з позначеними вершинами On height of vertex identifiers of vertex labeled graphs |
| title_full | О высоте идентификаторов вершин помеченных графов |
| title_fullStr | О высоте идентификаторов вершин помеченных графов |
| title_full_unstemmed | О высоте идентификаторов вершин помеченных графов |
| title_short | О высоте идентификаторов вершин помеченных графов |
| title_sort | о высоте идентификаторов вершин помеченных графов |
| topic | Интеллектуальные робототехнические системы |
| topic_facet | Интеллектуальные робототехнические системы |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/85116 |
| 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 |