Graph reconstruction by automata team.pdf Рассматривается задача [1] восстановления конечного связного неориентированно-го графа G без петель и кратных ребер при помощи агента, который перемещается порёбрам графа G, считывает и изменяет метки на его вершинах и инциденторах. На ос-нове собранной информации агент строит граф H, изоморфный графу G с точностьюдо меток на элементах графов. Требуется найти алгоритм обхода и разметки графа Gдля решения этой задачи.Известен ряд алгоритмов, реализующих восстановление графа при помощи постро-ения на его вершинах неявной нумерации [2] при помощи агента A, они подробно опи-саны в [3,4]. Наиболее простым в реализации является Базовый Алгоритм [3], однакоон имеет кубическую, от числа вершин в графе, верхнюю оценку временной сложно-сти. Предлагается модификация Базового Алгоритма, понижающая эту оценку. Приэтом верхняя оценка временной сложности зависит от количества агентов, которыепроводят восстановление графа.В [4] показано, что верхняя оценка временной сложности зависит от длины мак-симального простого цикла t в графе, цикломатического числа q [5] и количествавершин n исследуемого графа и равна O(n + qt). В процессе восстановления агентразбивает рёбра графа на два множества: древесные и обратные [5], а все пройденныевершины, у которых не все рёбра восстановлены, образуют красный путь [3].Наибольшего времени требуют обратные ребра, для восстановления которых агентвыполняет проход по вершинам красного пути, длина которого соизмерима с длинойнаибольшего простого цикла. Для сокращения этого прохода используются агенты Aj,i = 1, . . . , j. Они двигаются вдоль красного пути, сохраняя между собой равное рас-стояние. Для этого они обмениваются сообщениями A с Aj, Aj с Ai - 1 для i = 2 , . . . , j.Для каждого агента Aj, i = 1,... , j, фиксируется длина красного пути от его начала(конца) до вершины, в которой находится этот агент.При восстановлении обратного ребра агенту A требуется проходить не весь красныйпуть (в прямом или обратном направлении), а до первого агента Aj , для которогоизвестна длина пути от него до начала (конца) красного пути. Это позволит вычислитьдлину красного пути до вершины, которой инцидентно восстанавливаемое обратноеребро, и её неявный номер. После этого агент вернётся обратно в конец красного путипо пройденной его части и восстановленному обратному ребру.Таким образом, обратное ребро будет однозначно восстановлено. При этом агентвыполнит проход по вершинам красного пути (в прямом и обратном направлении),длина которого не превышает наибольшего расстояния между агентами Aj и Aj - 1,i = 2 , . . . , j. Поскольку это расстояние поддерживается агентами Aj - 1 одинаковым, тоагент сделает не более чем O ( t / j ) шагов.Очевидна справедливость следующих утверждений.Утверждение 1. При восстановлении графа коллективом агентов A, Aj,i = 1 , . . . , j, которые выполняют Базовый Алгоритм и находятся на равном расстояниидруг от друга, верхняя оценка временной сложности модификации базового алгоритмаравна O(n + qt/j).Если агенты Aj не поддерживают между собой равного расстояния, а это рас-стояние вычисляется при помощи некоторой функции f (t,i), то для восстановленияобратных рёбер агент использует не более чем O(qf (t,i)) шагов.Утверждение 2. При восстановлении графа коллективом агентов A, Aj,i = 1 , . . . , j, которые выполняют Базовый Алгоритм и находятся на расстоянии f (t, i)друг от друга, верхняя оценка временной сложности модификации базового алгоритмаравна O(n + qf (t, i))

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