3.  А выбирает из <Э{у) ребро (h, г), у которого c(g,г) = г и ^((b,*),*) = г, и переходит по нему в вершину z;

4.  k := z ;

5.  j := 1;

6.в окрестности О (и) есть ребро (и, г), у которого ц{и,г) = г и /i((u,z),z) = r do

7.А переходит по ребру (и, z) в вершину z;

8.b := z;

9.j :=j + l; end do

10.  £_H := ^_H U {(k(t), k(t  –  j))}; Подробно базовый алгоритм описан в [5].

Теорема 1. Выполняя "Базовый алгоритм", А восстановит любой граф GeK с точностью до изоморфизма, за время не большее, чем 0(п³). При этом используется 2 краски и не более, чем ячеек памяти. Нижняя оценка временной и емкостной сложности равны 0(п).

Доказательство теоремы приведено в [5].

При выполнении процедуры ВПЕРЕДИ) и НАЗАД(^) А проходит одно ребро, при выполнении процедура ВОССТ» А проходит одно обратное ребро и не более п – ребер г – пути, т. е. цикл, состоящий из обратного ребра и некоторого конечного отрезка г – пути, соединяющего вершины, инцидентные обратному ребру. При вы­полнении алгоритма А проходит дерево поиска в глубину, состоящее из п — 1 ребер, и т – п+1 обратных ребер. Будем считать, что инициализация алгоритма (строки 1–6 описания алгоритма восстановления), анализ окрестности 0(v) текущей вершины и выбор одной из трех процедур занимают некоторое постоянное число единиц времени. Так же будет считать, что выбор ребра при выполнении процедур и проход по ребру осуществляется за 1 единицу времени. Тогда временная сложность алгоритма определяется суммой следующих величин:

1.  Инициализация выполняется один раз и ее сложность равна O(l);

2.  Процедура ВПЕРЕДИ) выполняется ровно п – 1 раз и общее время ее выпол­нения оценивается как 0(п);

3.  Общее время выполнения процедуры НАЗАД(г>) оценивается как 0(п)

4.  Выполнение процедуры ВОССТ один раз оценивается как <Э(п), а ее вы­полнение для всех обратных ребер как 0(п(т — п + 1)), т.е. как значит, Т*(п) есть величина. Емкостная сложность S(n) алгоритма определяется сложностью списков Vh,Eh, к(1),.., k(t), сложность которых, соответственно, определяется величинами 0{п),0{п²}, 0{п). Следовательно: S{n) = 0{п²}.

5.  Модификации "Базового алгоритма"

"Базовый алгоритм" имеет доста­точно высокий порядок верхней оценки временной сложности и, поскольку число вершин графов неограниченно, А требуется конечная, но бесконечно растущая па­мять. Модификации "Базового алгоритма" дают лучшие оценки временной и ем­костной сложностей.

В настоящей работе рассматриваются следующие модификации "Базового алго­ритма":1) разделить А на два агента: агента исследователя АИ, с конечной памятью, и агента экспериментатора АЭ; 2) восстанавливать обратные ребра, сразу все для одной вершины; 3) восстанавливать обратные ребра, при "зацикливании" А; 4) Раз­делить множества ребер на непересекающиеся классы,которые восстанавливаются различными стратегиями.

Подробно эти методы описаны в [5–7]. Целью настоящего раздела - показать, что "Базовый алгоритм" является основой этих модификаций.

5.1.  Модификация 1

Поскольку при обходе графа и разметки его элементов А не пользуется записанной ранее в память информацией, а только оперирует с ней на определенных этапах обхода и разметки, возможно разделение А на два агента АИ и АЭ. Первый будет перемещаться по графу G, считывать и изменять метки на элементах графа, и передавать сообщения АЭ о своих передвижениях и изменениях меток. Второй будет принимать сообщения, обрабатывать их и на их основании строить граф Я. Принципиально "Базовый алгоритм" не изменяется, изменяется, только то, что АИ будет передавать соответствующее сообщение и не будет строить в своей памяти представление графа Я. Различных видов сообщений, которые передает АИ, будет ограниченное количество, поэтому АИ может быть реализован конечным автоматом. Данная модификация позволяет АЭ строить граф Я либо в процессе приема сообщения от АИ, либо после того, как АИ отправит последнее сообщение. Алгоритм, где применяется данная модификация подробнее описан в [6]. Данная модификация не меняет порядка Г*(и), а только ослабляет ограничения накладываемые, на АИ.

5.2.  Модификация 2

При стратегии восстановления всех обратных ребер, ин­цидентных вершине и, за одно выполнение процедуры ВОССТ(f) изменится толь­ко процедура ВОССТ(f). В ней А будет метить исследуемую вершину и камнем I (признак того, что для данной вершины восстанавливаются обратные ребра), а за­тем отходить от нее по г - пути к его началу, для поиска белых ребер, смежных с вершиной и, у которой fi(u) = I. При этом подсчитывается количество переходов до каждого момента, когда А видит вершину fi(u) = I . Затем на основании неявной М - нумерации происходит восстановление всех обратных ребер вершины и и по г - пути АИ возвращается в его конец. При этом процедура ВОССТ(f) вызывается только один раз для каждой вершины графа, вне зависимости от количества обратных ребер, смежных с ней. Тогда вызов процедуры ВОССТ» будет произво­диться не  – п+1 раз (количество обратных ребер), аn раз (для каждой вершины один раз). В этом случае Г*(и) будет величиной 0{п²) , однако А потребуется один дополнительный камень I.

5.3.  Модификация 3

Обратные ребра можно восстанавливать как при первом их появлении, а так же при "зацикливании" А. При этом не произойдет изменения ни Т*(п), ни S(n) и А потребоваться то же самое количество камней, однако это повлияет на то, в какой момент времени будет вызываться процедура ВОССТ(f) , т.е. обратные ребра будут восстановлены в графе Я.

5.4.   Модификация 4

Множество вершин графа G разобьем на два множе­ства: ординарные и неординарные вершины. Вершина v G Vg ординарная, если deg(v) < D , где D – заранее известная константа. В противном случае вершина неординарная. Для того, чтобы А на графе G мог разбить множество вершин на два непересекающихся класса, необходимо выполнения условия: для всех (u,v) G Eg, либо v, либо и  – ординарная вершина. В этом случае множество ребер разбивает­ся на три непересекающиеся множества: древесные, обратные и неординарные, т.е. те, которые смежны с неординарной вершиной. Обратные и древесные ребра для ординарных вершин восстанавливаются, так же как и в "Базовом методе" или его модификации 1 – 3. Обратных ребер у ординарной вершины не более, чем D, А может их подсчитать и при выполнении процедуры ВОССТ(f) подсчитывать коли­чество восстановленных ребер и прекратить отход по вершинам г - пути, когда он восстановит все обратные ребра вершины, не доходя до начала г – пути. Неорди­нарные ребра восстанавливаются так: неординарное ребро, по которому А попал в неординарную вершину и пометил ее камнем г из множества камней {1, ..,р}, восста­навливается при первом прохождении. В момент пометки вершины камнем г, в гра­фе Н с камнем г ассоциируется следующая по порядку вершина, и, таким образом, ей присваивается неявный номер. Все остальные неординарные ребра неординарной вершины, помеченной г камнем, восстанавливаются, когда А попадает в вершину г – пути, из которой видно неординарную вершину, помеченную камнем г, в этом слу­чае для неординарного ребра неявные номера смежных с ним вершин вычисляются без дополнительных переходов. Алгоритм, реализующий данную модификацию, по­дробно описан в [6]. Поскольку А строит представление графа в виде списка ребер графа , то в случае, если р  – заранее известная константа, количество ребер будет величиной 0(п) и тогда S(n) будет величиной 0(п), что на порядок лучше, чем в общем случае.

6. Частные случаи классов графов и операции над ними

В данном раз­деле будут рассмотрены некоторые классы графов и операции над ними, такие, что при выполнении на них "Базового алгоритма" или его модификаций 1–4 возможно будет понизить верхнюю оценку временной или емкостной сложности, либо она не будет ухудшена.

6.1. Классы графов

Рассмотрим следующие классы графов.

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

Пусть К^р£ – класс графов, содержащих р неординарных вершин, а степень ор­динарных не превышает D. Отдельного внимания заслуживает случай, когда р = О, обозначим его K_D. Лемма 1. Верхняя оценка емкостной сложности восстановления графа G G K_D "Базовым алгоритмом" или его модификациями 1–4 является величиной 0(п).

Доказательство. А строит граф Я в виде списка ребер. Поскольку т < Dn, то для хранения потребуется 2т ячеек памяти и не более, чем п – ячеек для хранения списка вершин г – пути. Таким образом, S(n) будет величиной 0(п).

Замечание 1.Утверждение леммы справедливо и для графа G G K^p_D, при усло­вии, что р заранее известная константа. Поскольку количество неординарных ребер не превосходит рп, то S(n) будет величиной порядка 0(п+рп) = О in).

Лемма 2. Верхняя оценка временной сложности "Базового алгоритма" на гра­фе G G K_D является величиной 0(п²).

Доказательство. Поскольку граф G G K_D , то в нем будет не более, чем Dn обратных ребер, для каждого из которых будет выполнять процедуру ВОССТ» , которая выполняется не более, чем за п шагов. Тогда Т*(п) будет величиной 0(п²).

6.2. Операции над графами

Рассмотрим операции над графами, при приме­нении которых верхняя оценка результирующего графа не ухудшается.

6.2.1. Операция отождествления

Отождествление двух вершин гл и v₂ гра­фов i и G₂ из класса К, порождают граф G , в котором вершины V и V2 объеди­няются в вершину сочленения и. Частный случай отождествления, когда один из графов G1 или G2 состоит из двух вершин, соединенных ребром. Такое отождествле­ние фактически является добавлением к графу висячей вершины. Отождествление будет правильным, если: 1) не будут отождествляться ординарная и неординарная вершины; 2) не будет нарушаться ординарность получаемой вершины сочленения; 3) нарушение ординарности увеличит D на константу. Далее будем рассматривать только правильные отождествления.

Лемма. Граф G, полученный отождествлением двух графов G_x и G₂, восста­навливается за время не большее, чемTj*(n) + Т₂*(п), где Tj*(n) и Т₂*(п) - верхние оценки временной сложности восстановления G и G2, соответственно.

Доказательство. Рассмотрим все возможные варианты начала выполнения агентом А алгоритма восстановления G. Пусть и\ вершина сочленения G\ и Со­Существует три различных начальных положения А : 1) А попал в вершинуmщ; 2) А попал в вершину ы G V(Gi)\{ui}; 3) А попал в вершину v₂ G V(G₂)\{ui}. Рассмотрим эти случаи.

добавляет вершину и\ в г – путь. После этого он либо попадет в вершину vi/ G V(Gi)\{m}, либо в вершину v₂f G F(G₂)\{ui}. Предположим, что он попал в V\l (v₂f). Поскольку вершина и\ добавлена в г – путь, то А может попасть из вершин содержащихся в V(G\)\{ui} (V(G₂)\{u\}) в вершины, содержащиеся в V(G2)\{ui} (V(Gi)\{ui}), только после того, как он посетит их все, восстановит инцидентные им ребра и вернется в щ. А восстановит подграф G, который совпадает с графом Gi (G₂). Затем он вернется в щ и перейдет в вершину v₂l (v1l) и продолжит обход графа. Таким образом, А восстановит подграф G, который совпадает с графом G₂ (Gi). Тогда Г*(и) = Т*(п) + Т*(п).

2.  А добавит вершину V\ в г – путь. В этом случае существует два различных варианта дальнейшего выполнения алгоритма.

2.1.   А из г>1 начинает выполнение алгоритма и выполняет его для подграфа G, который совпадает с G. Затем он попадает в вершину Ui, а из нее в вершину v₂l £ V(G₂)\{u\} и продолжает выполнять алгоритм, для подграфа G, который совпадает с G_x. Следовательно, Г*(n) = Т*(п) + Т*(п).

2.2.  А из г>1 начинает восстановление и выполняет его для подграфа G, который совпадает с G, подграфом G. Затем он попадает в вершину U, а из нее в вершину v₂f G V(G₂)\{u\} и продолжает восстанавливать подграф G, который совпадает с G₂. После перехода в вершину щ А добавит ее в г – путь, и из подграфа G, который совпадает с G₂, А уйдет только после того, как полностью его восстановит. После чего А вернется в вершину U\ и продолжит восстановление графа, для оставшейся части G = Gi\G_xl . В силу выше сказанного Г*(и) = 2\*(п) + Т₂*(п). Следовательно, в этом случае утверждение теоремы для G выполняется.

3.  Этот случай полностью аналогичен случаю 2. Воспользуемся рассуждениями из пункта 2., рассматривая вместо графа G₂ граф G_x, а вместо графа G_x граф G₂.

Из пунктов 1 -3 следует справедливость леммы.

Лемма 4. Граф G, полученный добавлением в граф С_ъ из некоторого класса, висячей вершины имеет порядок сложности выполнения "Базового алгоритма" и его модификаций 1 – 4, такой же, что и G_x.

Доказательство. В добавленную висячую вершину можно будет попасть только по добавленному вместе с ней ребру. Значит, добавленное ребро может быть толь­ко древесным и для него А выполнит 2 шага. Таким образом, Т*(п) изменится на величину О(2), что не изменит порядок ее сложности.

Замечание 2. Если в граф последовательно добавить к висячих вершин, то Т*(п) изменится на величину О(2k), что не изменит порядок ее сложности.

6.2.2. Введение вершины "Штейнера". Введение в граф "вершины Штей-нера" [8] - добавление вершины между двумя соединенными ребром вершинами с последующим удалением соединяющего ребра и соединением ребрами добавленной вершины и исходных.

Лемма 5. Граф G, полученный добавлением в граф G₁, из некоторого клас­са,вершины "Штейнера" имеет порядок сложности выполнения "Базового алго­ритма" и его модификаций 1–- 4, такой же, что и G_x.

Доказательство. Предположим, что между вершинами vi и v₂ была добавле­на вершина и, ребро (v_hv₂) было удалено из графа G_x, а ребра – (у_ъи) и (v₂,u) добавлены.

Рассмотрим, как изменится Г*(и), в зависимости от того, было ли ребро (v_bv₂) древесным или обратным при выполнении А восстановления графа G.

1.Если ребро (vi,v₂) было древесным, то (v_bu) и (v₂,u) в графе G так же будут древесными, поскольку А в вершину и может попасть из вершины V1, а выйти из нее, только в вершину v₂, и наоборот. Значит, А потребуется выполнить еще дополнительно 4 шага, в этом случае к Т*(п) прибавится величина 0(4), что не изменит порядка ее сложности.

2.  Если ребро (vi,v₂) было обратным, то рассмотрим, появятся ли в графе до­полнительные циклы, которые приведут к ухудшению Т*(п). Поскольку при выпол­нении этой операции удаляется одно ребро и добавляется два новых, то m =1 +1 и п = п + 1, тогда х = m – п + 1 = mi + 1 – (щ + 1) + 1 = mi – щ + 1 = xi. Зна­чит, дополнительных циклов не появится, и верхняя оценка временной сложности не ухудшится.

6.2.3. Классы графов, порожденные операциями над графами.

Рассмот­рим классы графов, порожденные специфическим отождествлением нескольких гра­фов из некоторого класса.

Пусть Т^к - класс квази - деревьев. Будем говорить, что граф G G Т^к, если он образован последовательным отождествлением графов Gj <EK,j = 0,.., к где к G N, и щ,.., Wfc_i – вершины сочленения, если, отождествив Gj, j = 0, ..,к с вершинами, а вершины uq, ..,Uk-i с ребрами, мы получим граф вида дерево.

Лемма 6. Граф G, полученный последовательным отождествлением графов Gj G К, j = 0,..,к, восстанавливается за время не большее, чем E^kj=iTj*(n), где Т*(п) – верхняя оценки временной сложности восстановления Gj.

Доказательство. Для графа, полученного последовательным сочленением Gj G К, j = 0,.., к где к G N, и щ, ..,Uk-i – полученные вершины сочленения, можно провести такие же рассуждения, на этапе построения, как и для Gi и G₂ из леммы 4, для полученного после j-ого сочленения графа и следующего для сочленения графа G_j+i. Значит, утверждение верно. 
Пусть S^k – класс квази колец. Будем говорить, что граф G G S^k, где к G N, если он образован сочленением Gj-i с Gj, j = 1, ..,к, и G₀ с G_k, где Gj е К, j = 0, ..,к, Uo,..,Uk - вершины сочленения, если, отождествив Gj, j = 0,.., к с вершинами, а вершины Uq, ..,Uk с ребрами, мы получим граф вида – цепочка вершин соединенных по кругу.

Лемма 7.Пусть G еК. Разобьем множество его вершин на два не пересекаю­щихся подмножества V₂(G) и V₃(G), где множество V₂(G) = {v G V(G) : deg(v) < 2}, а множество V₃(G) = {v G V(G) : deg{v) > 3}, V{G) = V₂{G) U V₃(G). Тогда T*(n) есть величина 0(Y,_vev₃(G) deg(v)n).

Доказательство. Для доказательства рассмотрим два подмножества множества вершин графа G, и выясним, в каких случаях они порождают откаты при восста­новлении обратных ребер.

Рассмотрим множество вершин V₃(G). Каждая вершина из V₃{G) не может по­родить откатов более, чем ее степень. Действительно, откаты возникают при восстановлении обратных ребер вершины. При этом, если v G V₃(G) вызывает "зацикли­вание то она порождает откат. Если эта вершина из множества V₃{G) не вызывает "зацикливания" то она будет смежна с вершиной, которая вызовет "зацикливание" и откат. Значит, каждая вершина v G V₃{G) может вызвать откат не более, чем deg(v) раз. Тогда будет не более, чем V₃(G)\deg(v) откатов.

Рассмотрим множество вершин V₂{G). Они порождают откаты в двух случаях.

Вершина из V₂(G) является вершиной, из которой А начинает выполнение "Ба­зового алгоритма". В этом случае, А восстановит только ребра из ее окрестности. Это ребро, по которому А совершил проход в глубину графа. И одно не пройден­ное ребро, по которому он может попасть в начальную вершину. Значит, вершина, которой оно инцидентно, вызовет "зацикливание" и откат. Таким образом, вершина из V2(G), будучи начальной, может вызвать откат. Так как эта вершина может со­держаться либо на последовательности вершин, которые соединяют две вершины из множества V₃(G), в этом случае откат, вызываемый этой вершиной, уже учтен при подсчете откатов, порождаемых вершинами из множества Vs(G), либо на цепочке вершин, которая примыкает к вершине из множества Vs(G), в этом случае откат, порождаемый вершиной из множества V₂(G), учтен при подсчете откатов для вер­шин из множества Vs(G). Значит, вершины из множества V₂(G) могут породить не более одиного отката и не повлияют на Т*(п).

Вершина из V₂(G) не является вершиной начальной для выполнения алгорит­ма, но смежна с вершиной из множества V%{G). Откаты, порождаемые этой верши­ной, были учтены при подсчете количества откатов для ребер вершин из множества V₃(G). Таким образом, согласно известной нам верхней оценке временной сложности "Базового алгоритма" 2п – 1 + (ш - п + 1)п. Слагаемое (k–n + 1)п соответству­ет откатам. Тогда сложность можно переписать с учетом количества откатов, а их T,vev₃(G) de9(v) штук. Следовательно, Т(п) < 2п – 1 + T,_vev₃(G) deg(v)n, а при до­статочно больших п, Т*(п) есть величина 0(J2_V£V(G) deg(v)ri).

Лемма 8. Пусть G G S^k, тогда Т*{n} есть величина Ej=iT/N + O(E_v€G0deg{v)n), где Gj G К j = 0,..,к, где Т*{п)- верхняя оценка временной сложности выполнения "Базового алгоритма" на графе Gj, множество V₃(Gj) определено как и в лемме 8, а G₀ подграф, соответствующий части графа, в ко­торую был помещен А изначально.

Доказательство. Для данного класса графов существенным является начальное положение А . Поэтому, не нарушая общности рассуждений, предположим, что А попадает в вершину v G V(Go)\{uo}. Если же А попал в вершину v G Gj, j^ 0, перенумеруем Gj и щ,Uk так, чтобы j = 0. Легко видеть, что при разъединении графа G по вершине и^ мы получим граф Gt G T^fc, а если удалить из G граф, соответствующий графу G₀, то мы получим граф Gil G T^fc_1.

Рассмотрим случаи: А изначально попадает в вершину, А попадает в вершину v<EV(Go)\{u₀,u_k}.

изначально попал в вершину и_к. Этим А фактически разъединит граф G по вершине и_к. Рассмотрим граф Gl, полученный в результате этого. Для этого графа справедлива лемма 6 и рассуждения, приведенные при ее доказательстве. Таким образом, убрав из рассмотрения вершину и_к, можно утверждать, что Т*(п)есть величина

Однако, необходимо учесть действия, которые выполня­ются с вершиной сочленения. Поскольку она добавлена в г - путь, то действия по восстановлению ребер е1 = (v,k,v), где v G V(Go), могут происходить только в рам­ках подграфа, соответствующего Go и уже учтены в слагаемом Т£(п). Для ребер е₂ = (и_к,и), где и G V(G_k), вершина и_к будет вызывать "зацикливание"и откаты как в пределах подграфа, соответствующего G_k, так и длины, соизмеримой с п, по­скольку для того, чтобы пройти в и_к по ребрам, инциденторы которых помечены г, А придется пройти по вершинам, принадлежащим всем Gj, где j = 0,..,к. Пер­вые откаты учтены в слагаемом Т£(п). Количество же вторых не превысит deg(u_k). Значит, их можно учесть, добавив к сумме величину 0{deg{u_k)n). Тогда, Г*(и) есть величина £*₌₁ T*{n) + 0(deg(u_k)n).

2. Изначально попал в v G V(Go)\{uo,u_k}. В этом случае А выполнит следую­щие действия: восстановит часть или весь подграф, соответствующий G₀, после чего попадет в вершину щ (и_к), а из нее пройдет далее в вершину и G V(G\) (и G V(G_k)), распознает весь или часть подграфа, соответствующего G\ (G2), и так далее, до тех пор, пока он не попадет в вершину и_к (tr), добавив ее в г - путь, и пойдет далее в вершину и G V(G_k) (и G V(G₀) ). Таким образом, А фактически разъединит граф G, убрав из него подграф, соответствующий G₀. Рассмотрим граф Gff, полученный в результате этого. Для него будет справедлива лемма 7. Вершины подграфа, соответ­ствующего Go, могут вызывать "зацикливание" и откаты при восстановлении обрат­ных ребер, как в пределах подграфа G₀, так и длины, соизмеримой с n. Поскольку при "зацикливании" в 1-окрестности вершины могут находиться вершины, в кото­рые можно пройти по ребрам, инциденторы которых помечены г, предварительно пройдя по всем вершинам подграфов Gj, где j = 0,.., к. Таким образом, Г*(p) будет состоять из Т*(n) для Gff и слагаемого, в котором будут учтены откаты для вершин подграфа, соответствующего G₀. Их будет не более _{v V(G0)} deg(v) штук.

Таким образом, Г*(и) есть величина J2^k_j=iT*(n) + 0(_vV(G) deg(v)n).

Исходя из 1 - 2 можно заключить, что Т* есть величина E₇₌i?¹*(n)+ O(J2vev_:i(G₀) deg(y)ri), поскольку слагаемые в пункте 1. T£(G) и 0(deg(u_k)n) погло­щаются'слагаемым O(£„ev(G₀) deg(v)n) из пункта 2.

В [6] подробно рассматривались дополнительные частные случаи графов и опе­рации над ними для модификации 4 "Базового алгоритма" , из-за громоздкости описания и доказательства в данном разделе они рассматриваться не будут.

7. Выводы

Предложен базовый метод восстановления ранее неизвестного гра­фа с точностью до меток на его элементах графов при помощи передвигающемуся по нему агента. Данный метод использует две краски и имеет временную сложность 0{п) < Т{п) < 0(п³). Базовый метод допускает модификации, которые позволя­ют получить лучшую оценку временной сложности и упрощают агента А, однако, накладывают дополнительные ограничения на восстанавливаемый граф. Найдены операции над графами такие, что результирующий граф имеет верхнюю оценку временной сложности не хуже, чем исходные.

1.Dudek G., Jenkin M. Computational principles of mobile robotic // Cambridge Univ. Press. –2000 – 280 p.

2.Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. – М.: Мир, 1979. – 536 с.

3.Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. – М.: МЦНМО, 2001. – 960 с.

4.Касьянов В. Н., Евстигнеев В. А. Графы в программировании: обработка, визуализация и применение. – СПБ.: БХВ – Петербург, 2003. – 1104 с.

5.Грунский И. С. , Татаринов Е. А. Распознавание конечного графа блуждающим по нему аген­том. // Вестник Донецкого университета. Серия А. Естественные науки – 2009, Вып. 1. – С.492–497.

6.Грунский И. С., Татаринов Е. А. Алгоритм распознавания графов. // Тр. 4 междунар. конф. "Параллельные вычисления и задачи управления" PACO’2008, Москва, Ин-т проблем управ­ления им. В. А. Трапезникова РАН, – 2008 – С.148–1498.

7.Татаринов Е. А. M – нумерация, как метод распознавания графов. //Збiрник наукових праць "Питання прикладної математики математичного моделювання" , Днiпропетровськ – 2010. – С.260-272.

8.Кристофидес Н. Теория графов – алгоритмический подход. – М.: Мир, 1978. – 432 с.

9.Э. Рейнгольд, Ю.Нивергельт, Н.Део Комбинаторные алгоритмы. Теория и практика. – М.: Мир, 1980. – 477 с.E.

A. Tatarinov

Basic algorithm for reconstructing a finite graph.

The problem of reconstructing a graph agent moving through his edges, read and modify marks on the elements of the graph. We propose a basic method of reconstruction. The algorithm requires 2 different colors and cube of the number of vertices number of steps. Found modification of the algorithm, which lowers the upper bound of time complexity. Found the operation on graphs, the resulting graph which has an upper bound for the complexity of the basic algorithm is not worse than the original.

Keywords: graph reconstraction, agent, nod mark, move on graph .

Є. О. Татаринов

Базовий алгоритм вiдновлення скiнченного графа.

Розглядається задача вiдновлення графа агентом, який перемiщується по його ребрах, що прочитує i змiнює мiтки на елементах графа. Запропоновано базовий метод вiдновлення. Алгоритм потребує 2 рiзнi фарби i кубiчного, вiд числа вершин графа, числа крокiв. Знайдено модифiкацiї алгоритму, якi знижують верхню оцiнку часової складностi. Знайдено операцiї над графами, результуючий граф яких має верхню оцiнку складностi виконання базового алгоритму не гiрше, нiж вихiдний.

Ключовi слова: вiдновлення графiв, агент, мiтка вершини, блукання по графу.

                                                                                                                                                                                     Получено 23.11.10