Graph recognition by moving agent.pdf Основной проблемой компьютерной науки является проблема взаимодействияуправляющей и управляемой систем (управляющего автомата, агента и его операционнойсреды) [1]. Взаимодействие этих систем зачастую представляется как процессперемещения агента по помеченному графу (лабиринту) среды [2]. Определился рядподходов к моделированию операционных сред, одним из которых является топологический[3]. В этом случае агенту недоступна метрическая или алгоритмическая информацияо среде и доступна только информация о связях между различными областямисреды.Постановка задачи. Рассматривается конечный граф G - неориентированный,связный, без петель и кратных ребер, где V - множество его вершин и E - множестворебер. Вершины и инциденторы графа G можно метить специальными краскамии/или камнями, где инцидентор - «точка прикосновения» вершины v и ребра (v,u).Изначально предполагается, что все вершины и инциденторы не помечены.Требуется построить такое множество C = {ci}, где ci = {Vi, Ei} и V С V , Ei С E ,инайти такое отображение A , чтобы, используя их, можно было построить граф H, изоморфныйграфу G , и тем самым распознать граф G с точностью до изоморфизма. Подотображением будем понимать установление взаимно однозначного соответствия междувершинами и ребрами каждого конкретного ci и вершинами и ребрами графа H.Для проведения проверок и выполнения отображения используется агент, которыйпередвигается по неизвестному графу G из вершины в вершину по ребру, соединяющемуих. Агент воспринимает некоторую локальную информацию о 1-окрестности vи использует краски и/или камни из множества {b, r, L} для пометки вершин и ин-циденторов графа G . Он обладает конечной, но бесконечно наращиваемой памятью,в которую будут отображаться проверки и строиться таблица графа H .В данной работе предполагается, что ci - это M -пути и, возможно, одно обратноеребро. Обратное ребро - ребро, соединяющее две вершины M -пути. M -путь [4]- это простой путь в графе, в котором каждая следующая вершина имеет большийM -номер, чем предыдущая. M -нумерацией вершин графа называется нумерация, соответствующаяпорядку их обхода при поиске в глубину [4]. Правило построения проверокci следующее: отбирается M -путь, из конечной вершины которого можно попастьтолько в ранее пройденную вершину. Агент обладает красками r, b и камнем L.Краска r используется для пометки древесных ребер, а b - для пометки уже исследованныхвершин и инциденторов. Камень L используется при исследовании обратногоребра. Агент, блуждая по графу, создает неявную M -нумерацию в графе G, которуюотображает в граф H, создавая в нем явную M -нумерацию. Явная M -нумерацияпозволяет корректно отобразить проверки и обратные ребра. Агент обозревает метки1-окрестности вершины, в которой он находится: метку на вершине и метку наближних и дальних инциденторах ребер из 1-окрестности. Процесс выполнения алгоритмаразбит на следующие этапы: 1) построение множества проверок; 2) выполнениепроверки, построенной по правилу; 3) отображение конкретной проверки в граф H ;4) отображение в граф H обратного ребра из проверки, если таковое есть.Разработаны полиномиальные алгоритмы «Покрытие» и «Отображение» для выполненияшагов 1-2 и 3-4 соответственно. Алгоритмы могут выполняться как последовательно,так и параллельно. В работе рассматривается параллельное их выполнение.Теорема 1. Алгоритмы «Покрытие» и «Отображение» распознают граф G с точностьюдо изоморфизма. Они требуют две различные метки, их временная сложностьограничена снизу линейной функцией от числа вершин n графа G, а сверху - кубическойфункцией. Емкостная сложность равна O(n2).Предложенный алгоритм охватывает более широкий класс графов, чем предложенныйв работе [5], хотя верхняя оценка временной сложности на порядок хуже.

Скачать электронную версию публикации