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

Abstract

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

Розглядається задача розрізнення вершин позначеного графа за асоційованими з ними мовами в алфавіті позначок. Визначено, що верхня оцінка довжини слова, що розрізнює дві вершини графа, детермінованого за розміткою околів вершин, дорівнює половині від кількості його вершин. Визначено також, що у мові кожної з двох різних вершин є слово, яке відрізняє одну вершину від іншої, і його довжина менша, ніж кількість вершин у графі. Знайдено оцінки висоти скінчених множин слів, що відрізняють одну вершину графа від інших його вершин (т.з. ідентифікаторів).

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.