Известия Саратовского университета. Новая серия.

Серия Математика. Механика. Информатика

ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)

Для цитирования:

Сапунов С. В. Об оценке длины слова, различающего две вершины помеченного неорграфа // Известия Саратовского университета. Новая серия. Серия: Математика. Механика. Информатика. 2013. Т. 13, вып. 2, ч. 1. С. 105-111. DOI: 10.18500/1816-9791-2013-13-2-1-105-111, EDN: SJJBAR

Статья опубликована на условиях лицензии Creative Commons Attribution 4.0 International (CC-BY 4.0).
Опубликована онлайн: 
27.02.2013
Полный текст:
скачать
(downloads: 198)
Язык публикации: 
русский
Рубрика: 
Информатика
УДК: 
519.7
DOI: 
10.18500/1816-9791-2013-13-2-1-105-111
EDN: 
SJJBAR

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

Авторы: 
Сапунов Сергей Валерьевич, Институт прикладной математики и механики НАН Украины, г. Донецк
Аннотация: 

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

Ключевые слова: 
графы с помеченными вершинами
языки в алфавите меток вершин
различение вершин графа
Список источников: 
  1. Глушков В. М., Цейтлин Г. Е., Ющенко Е. Л. Ал- гебра. Языки. Программирование. Киев : Наук. думка, 1989. 378 с.
  2. Капитонова Ю. В., Летичевский А. А. Математи- ческая теория проектирования вычислительных систем. М. : Наука, 1988. 298 с.
  3. Килибарда Г., Кудрявцев В. Б., Ушчумлич Ш. Неза- висимые системы автоматов в лабиринтах // Дискрет- ная математика. 2003. Т. 15, вып. 2. С. 3–39.
  4. Dudek G., Jenkin M. Computational Principles of Mobile Robotics. Cambridge University Press, 2000. 280 p.
  5. Сапунов С. В. Эквивалентность помеченных гра- фов // Труды ИПММ НАНУ. 2002. Т. 7. С. 162–167.
  6. Хопкрофт Д. Э., Мотвани Р., Ульман Д. Д. Вве- дение в теорию автоматов, языков и вычислений. М. : Издат. дом «Вильямс». 2002. 528 с.
  7. Грунский И. С., Сапунов С. В. Восстановление графа операционной среды мобильного робота путем размет- ки вершин, пригодной для дальнейшей навигации // Искусственный интеллект. 2012. № 4. С. 420–428. 8. Грунский И. С., Сапунов С. В. Идентификация вер- шин помеченных граф
Поступила в редакцию: 
29.08.2012
Принята к публикации: 
16.01.2013
Опубликована: 
27.02.2013
Краткое содержание:
скачать
(downloads: 101)
  • 1181 просмотр