О высоте идентификаторов вершин помеченных графов

• Published in: Искусственный интеллект
• Date: 2013
• Main Authors: Сапунов, С.В., Пилипенко, В.Ю.
• Format: Article
• Language: Russian
• Published: Інститут проблем штучного інтелекту МОН України та НАН України 2013
• Subjects: Интеллектуальные робототехнические системы
• Online Access: https://nasplib.isofts.kiev.ua/handle/123456789/85116
• Journal Title: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Cite this: О высоте идентификаторов вершин помеченных графов / С.В. Сапунов, В.Ю. Пилипенко // Искусственный интеллект. — 2013. — № 3. — С. 444–454. — Бібліогр.: 8 назв. — рос.

Рассматривается задача различения вершин помеченного графа по ассоциированным с ними языкам в алфавите меток. Показано, что верхняя оценка длины слова, различающего две вершины графа, детерминированного по разметке окрестностей вершин, равна половине числа его вершин. Показано также, что в языке каждой из любых двух различных вершин есть слово, отличающее одну вершину от другой, и его длина меньше числа вершин графа. Найдены оценки высоты конечных множеств слов, отличающих одну вершину графа от всех других его вершин (т.н. идентификаторов). Розглядається задача розрізнення вершин позначеного графа за асоційованими з ними мовами в алфавіті позначок. Визначено, що верхня оцінка довжини слова, що розрізнює дві вершини графа, детермінованого за розміткою околів вершин, дорівнює половині від кількості його вершин. Визначено також, що у мові кожної з двох різних вершин є слово, яке відрізняє одну вершину від іншої, і його довжина менша, ніж кількість вершин у графі. Знайдено оцінки висоти скінчених множин слів, що відрізняють одну вершину графа від інших його вершин (т.з. ідентифікаторів). 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.