Роботу присвячено дослідженню представлення графів з розміченими вершинами множинами слів у алфавіті міток вершин та пошуку метричних властивостей цього представлення. Графи з розміченими вершинами широко використовуються для описання та моделювання обчислювальних процесів у програмуванні, робототехніці, перевірці моделей тощо. При цьому графи відіграють роль інформаційного середовища для одного або декількох мобільних агентів. Переміщення агентів по графу визначають послідовності міток вершин - слова в алфавіті міток. Граф з розміченими вершинами називається Д-графом, якщо в околі кожної його вершини всі інші вершини мають попарно різні мітки. Для Д-графів у випадку, коли відомі карта графа (тобто множини вершин і ребер та функція розмітки) та ініціальна вершина, з якої агенти починають свої переміщення, існує однозначна відповідність між послідовністю міток вершин, які відвідує агент, і траєкторією переміщень цього агента на графі. У випадку, коли зовнішньому спостерігачу невідома карта досліджуваного Д-графа, переміщення агентів можуть бути організовані в такий спосіб, щоб на основі їх аналізу спостерігач одержав шукану інформацію щодо структури графа (наприклад, карту графа, найкоротші шляхи між вершинами, порівняння досліджуваного графа з графом-еталоном). У даній роботі уточнено представлення Д-графів так званою визначальною парою множин слів. Перша компонента цієї пари описує цикли графа, друга - його висячі вершини. Це представлення є аналогом системи визначальних співвідношень для повністю визначених автоматів. Також розглянуто структуру мінімальної за кількістю слів так званої канонічної визначальної пари та наведено алгоритм її побудови. Для детермінованого графа із заданою кількістю вершин і ребер знайдено точну оцінку кількості слів у першій компоненті його канонічної визначальної пари та мінімальні й максимальні досяжні оцінки кількості слів у другій компоненті канонічної визначальної пари. Результати надають змогу створювати та використовувати нові методи й алгоритми для розв'язання задач аналізу графів з розміченими вершинами.

 Наукова періодика України 

---

Додаткова інформація про автора(ів) публікації:
(cписок формується автоматично, до списку можуть бути включені персоналії з подібними іменами або однофамільці)

• Сапунов Сергій Валерійович (фізико-математичні науки)
• Сенченко Олексій Сергійович (фізико-математичні науки)
• Сенченко Онисим Сильвестрович (1905–) (історичні науки)

  Якщо, ви не знайшли інформацію про автора(ів) публікації, маєте бажання виправити або відобразити більш докладну інформацію про науковців України запрошуємо заповнити "Анкету науковця"