Известия Саратовского университета. Новая серия.
ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)


различение вершин графа

Об оценке длины слова, различающего две вершины помеченного неорграфа

Рассматривается задача различения вершин помеченного неорграфа по ассоциированным с ними языкам в алфавите меток. Показано, что верхняя оценка длины слова, различающего две вершины графа, равна половине от числа его вершин.