Лінгвістичне зображення графів з поміченими вершинами

Сапунов, СВ
1Сенченко, ОС
1Київський національний університет ім. Тараса Шевченка
Dopov. Nac. akad. nauk Ukr. 2019, 11:17-24
https://doi.org/10.15407/dopovidi2019.11.017
Розділ: Інформатика та кібернетика
Мова: Російська
Анотація: 

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

Ключові слова: визначальна пара, графи з поміченими вершинами, зображення графів