ВОССТАНОВЛЕНИЕ ГРАФА КОЛЛЕКТИВОМ АВТОМАТОВ

Колебательные процессы в технике имеют большое значение. Электромагнитные колебания лежат в основе всех современных электронных средств передачи и обработки информации.

Рассматривается задача [1] восстановления конечного связного неориентированного графа G без петель и кратных ребер при помощи агента, который перемещается по ребрам графа G, считывает и изменяет метки на его вершинах и инциденторах. На основе собранной информации агент строит граф H, изоморфный графу G с точнотсью до меток на элементах графов. Требуется найти алгоритм обхода и разметки графа G для решения этой задачи.

Известен ряд алгоритмов, реализующих восстановление графа при помощи построения на его вершинах неявной нумерации [2] при помощи агента А, они подробно описаны в [3,4]. Наиболее простым в реализации является Базовый Алгоритм [3], однако он имеет кубическую, от числа вершин в графе, верхнюю оценку временной сложности. Предлагается модификация Базового Алгоритма, понижающая эту оценку. При этом верхняя оценка временной сложности зависит от количества агентов, которые проводят восстановление графа.

В [4] показано, что верхняя оценка временной сложности зависит от длины максимального просто цикла t в графе, цикломатического числа q [5] и количества вершин n исследуемого графа и равна O(n+qt). В процессе восстановления агент разбивает ребра графа на два множества: древесные и обратные [5], а все пройденные вершины, у которых не все ребра восстановлены, образуют красный путь [3].

Наибольшего времени требуют обратные ребра, для восстановления которых агент выполняет проход по вершинам красного пути, длина которого соизмерима с длиной наибольшего простого цикла. Для сокращения этого прохода используются агенты А_i, i=1,...,j. Они двигаются вдоль красного пути, сохраняя между собой равное расстояние. Для каждого агента A_i, i=1,...,j, фиксируется длина красного пути от его начала (конца) до вершины, в которой находится этот агент.

При восстановлении обратного ребра агенту А требуется проходить не весь красный путь (в прямом или обратном направлении), а до первого агента A_i, для которого известна длина пути до вершины, которой инцидентно восстанавливаемое обратное ребро, и ее неявный номер. После этого агент вернется обратно в конец красного пути по пройденной его части и восстановленному обратному ребру.

Таким образом, обратное ребро будет однозначно восстановлено. При этом агент выполнит проход по вершинам красного пути (в прямом и обратном направлении), длина которого не превышает наибольшего расстояния между агентами А_i и А_i-1, i=2,...,j. Поскольку это расстояние поддерживается агентами А_i-1 одинаковым, то агент сделает не более чем O(t/j) шагов.

Очевидна справедливость следующих утверждений.

Утверждение 1. При восстановлении графа коллективом агентов A, А_i, i=1,..,j, которые выполняют Базовый Алгоритм и находятся на равном расстоянии друг от друга, верхняя оценка временной сложности модификации базового алгоритма равна O(n+qt/j).

Если агенты А_i не поддерживают между собой равного расстояния, а это расстояние вычисляется при помощи некоторой функции f(t,i), то для восстановления обратных ребер агент использует не более чем O(qf(t,i)) шагов.

Утверждение 2. При восстановлении графа коллективом агентов A, А_i, i=1,..,j, которые выполняют Базовый Алгоритм и находятся на расстоянии f(t,i) друг от друга, врхняя оценка временной сложности модификации базового алгоритма равна O(n+qf(t,i)).

Список использованной литературы

1. Dudek G. and Jenkin M. Computational principles of mobile robotic. Cambridge Univ. Press, 2000. 280 h.
2. Татаринов Е.А. М-нумерация, как метод распознавания графов // Збірник наукових праць «Питання прикладної математики та математичного моделювання». 2010. С. 260-272
3. Грунский И.С., Татаринов Е.А. Распознавание конечного графа блуждающим по нему агентом // Вестник Донецкого университета Сер. А. Естественные науки. 2009. Вып. 1. С. 492-497
4. Татаринов Е.А. Базовый алгоритм восстановления графа // Труды ИПММ НАН Украины. 2010. Т.21. С. 216-227.
5. Харари Ф. Теория графов. М. : Мир, 1973. 300 с.