С. В. Сапунов, “Об оценке длины слова, различающего две вершины помеченного неорграфа”, Изв. Сарат. ун-та. Нов. сер. Сер.: Математика. Механика. Информатика, 2013, том 13, выпуск 2(1),страницы 105

Информатика

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

С. В. Сапунов

Институт прикладной математики и механики НАН Украины, Донецк

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

Ключевые слова: графы с помеченными вершинами, языки в алфавите меток вершин, различение вершин графа.

УДК: 519.7

DOI: 10.18500/1816-9791-2013-13-2-1-105-111