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

  Скачати повний текст