Распознавание графа при помощи построения на нем М – нумерации
Рассматривается задача восстановления таблицы конечного неориентированного графа при помощи агента (робота, автомата), который перемещается по неизвестному графу из вершины в вершину [1, 2, 3].
Известен ряд алгоритмов решения этой задачи [1, 2, 3]. В настоящей работе предложен метод решен данной задачи, накладывающий минимальные ограничения на распознаваемый граф и агента, исследующего его.
1. Постановка задачи.
Рассматриваются конечные, связные, без петель и кратных ребер графы. В некоторую вершину такого графа помещается агент (автомат, робот). Граф Агенту не известен. Инциденторы графа можно помечать, специальными метками. Предполагается что изначально все вершины и инциденторы (точки присоединения ребер к вершинам) графа не помечены, то есть имеют метку w.
Задача распознавания состоит в том, что бы построить граф H изоморфный G. Для этого используют агента, который может перемещаться из одной вершины графа в другую по ребру соединяющему их. Так же агент может изменять метки на вершинах и инциденторах, используя для этого специальные краски и камни. Краска – метка имеющаяся у агента в неограниченном количестве, а камни – метки имеющиеся у агента в единственном экземпляре. Он может обозревать и анализировать 1 – окрестность вершины в которой находиться в данный момент, то есть видеть метку вершины и инциденторов всех смежных с ней ребер. Агент обладает конечной, но бесконечно наращиваемой памятью, в которой будет хранить список смежности восстанавливаемого графа.
2. Алгоритм «Распознавание графа».
Средства необходимые агенту для выполнения алгоритма «Распознавание»: конечная, но бесконечно наращиваемая память; две краски r и b, r – для пометки инцидентора ребра, по которому агент впервые попал в вершину, b – для пометки ребра, как уже пройденного, и вершины, как уже полностью исследованной; один камень L для пометки исследуемой вершины. Алгоритм «Распознавание» основан на методе «обход графа в глубину» и построении при этом на нем М – нумерации. Нумерацией называется инъективное отображение множества вершин графа на множество натуральных чисел. М – нумерацией вершин графа называется нумерация вершин, соответствующая порядку их обхода при обходе в глубину [4].
Вход Алгоритма: неизвестный нам граф G, у которого изначально все вершины помечены w, у агента вся область памяти не заполнена.
Выход Алгоритма: все вершины и инциденторы графа G помечены меткой b, в памяти агента содержится таблица смежности графа H изоморфного G.
Идея Алгоритма: идти в глубину графа G, создавая при этом новые вершины в памяти и соединяя их соответственно с предшествующими. При этом на графе G создается не явная М – нумерация, которую агент сохраняет и в восстанавливаемом графе. При отсутствии возможности идти в глубину агент исследует вершину. Для этого он ставит на вершину камень L и отступает по ребрам, инциденторы которых помечены r. При этом благодаря М – нумерации в восстанавливаемом графе и знанию количества переходов по ребрам, инциденторы которых помечены r, до тех пор пока не будет найдена вершина, из которой видно метку L, через ранее не пройденное ребро, однозначно определяется вершина которая смежна с исследуемой через ранее не пройденное ребро.
3. Временная сложность выполнения алгоритма распознавания.
Предполагается, что за один шаг агент может выполнить следующие действия : обозреть и проанализировать метки 1 – окресносности вершины в которой он находиться, перейти по ребру соединяющему две вершины – из одной в другую, выполнить некоторые действия с данными находящимися в памяти, изменить метку на вершине или инциденторе. Для каждой вершины агент выполняет следующие действия (все или почти все) :
– впервые приходит в нее при проходе в глубину, требуется один шаг;
– уходит из уже исследованной вершины при откате при поиске в глубину, требуется 1 шаг;
– отход по ранее пройденным ребрам, инциденторы которых помечены меткой r, при поиске вершины смежной через ранее не пройденное ребро (локальный откат), требуется не более чем n шагов;
– для каждого ребра вершины будет выполняться локальный откат, требует локальных откатов не более чем валентность вершины, требуется не более чем n локальных откатов.
Таким образом, время выполнения алгоритма «Распознавание графа» не превысит величины n(1+1+ n2) , которая является величиной O(n3) .
4. Частные виды графов.
Были найдены частные случаи классов графов, для которых верхняя оценка временной асимптотической сложности алгоритма «Распознавание графа» есть O(f(n)), где f(n) функция, растущая медленнее, чем n3 или является линейной функцией. Эти частные случаи позволяют показать, что предложенный в данной работе алгоритм во многих случаях имеет асимптотическую временную сложность не хуже чем алгоритм предложенный в работе [1]. Однако алгоритм «Распознавание графа» требует заранее известное фиксированное число различных красок и камней в отличие от алгоритма, предложенного в работе [1].
Примерами данных графов являются: деревья, кольцо, колесо с ограниченной степенью центральной вершины. Графы образованные следующим образом: в некотором дереве все вершины заменяем на дерево или кольцо, а ребра заменяем на вершины сочленения; в некотором кольце все вершины заменяем на дерево или кольцо, а ребра заменяем на вершины сочленения.
5. Выводы
В работе предложен новый полиномиальный от числа вершин графа метод восстановления, который требует две краски и один камень. На основе этого метода был построен полиномиальный алгоритм «Распознавание графа». Найдены нижняя и верхняя оценка времени выполнения этого алгоритма – линейная и кубическая функции от числа вершин в распознаваемом графе. Найдены частные случаи классов графов, которые допускают линейную сложность выполнения алгоритма «Распознавания графа».
СПИСОК ЛИТЕРАТУРЫ
1. Грунский И.С. О распознавании графов конечным автоматом / И.С. Грунский, М.Ю. Тихончев // Вестник Донецкого университета. Серия А. Естественные науки – 2001. – №2. – С. 351–356.
2. Albers S.,Henzinger M.R. Explorig unknown environments // Proc. Of the 25 Annual ACM Symposium of the Theory of Computing may 1997. – p. 416–425.
3. Емеличев В.А. и др. Лекции по теории графов – М: Наука. Физматлит., 1990. – 384 с.
4. Евстигнеев В.А. Применение теории графов в программировании. / Под ред. А. П. Ершова. – М.: Наука. Главная редакция физико – математической литературы, 1985 – 352 с.
Надійшла до редакції 2008 р.