РАСПОЗНАВАНИЕ ГРАФА МОЗАИЧНОЙ СТРУКТУРЫ, СОСТОЯЩЕГО ИЗ СВЯЗНЫХ КОМПОНЕНТОВ И МОСТОВ, КОЛЛЕКТИВОМ АГЕНТОВ
Електронний архів E-archive DonNTU – (Electronic archive Donetsk National Technical University)
Переглянути архів Інформація| Поле | Співвідношення | |
| Title |
РАСПОЗНАВАНИЕ ГРАФА МОЗАИЧНОЙ СТРУКТУРЫ, СОСТОЯЩЕГО ИЗ СВЯЗНЫХ КОМПОНЕНТОВ И МОСТОВ, КОЛЛЕКТИВОМ АГЕНТОВ
Recognition of a Mosaic-structured Graph, Consisting of the Linked Components and Bridges, by the Collective of Agents Розпізнавання графа мозаїчної структури, що складається зі зв’язаних компонентів та мо- стів, колективом агентів |
|
| Creator |
Шатохина, Н.К.
Шатохин, П.А. Shatokhina, N.K. Shatokhin, P.A. Шатохіна, Н.К. Шатохін, П.О. |
|
| Subject |
мозаїка
лабіринт комутативна група агент алгоритм puzzle maze commutative group agent algorithm мозаика лабиринт коммутативная группа агент алгоритм |
|
| Description |
The paper considers a problem of recovering a graph structure of a special type on the basis of the information obtained by traversing its borders. We study the graphs of mosaic structure consisting of several strongly connected components and bridges. The mosaic structure of the graph is constructed from equilateral triangles, without multiple edges and holes. Restoration of the structure of the graph is produced by two agents. The first agent - researcher (AR) has to perform the movements on the graph, to fix its directions of the motion and to give the extracted information to the second agent - experimenter (AE). The second agent (AE) recreates the structure of the graph in a symbolic form, based on the information received. Each movement of the AR can be characterized by a certain direction of the movement (free vector). The special symbolic notations are introduced for different directions of the motion, so the AR movement on the border of the graph uniquely generates a string of characters. Investigation of the properties of the system of movements along the mosaics of such kind gives a possibility to define a commutative group on a set of free vectors. On this basis, an algorithm for determining such substrings, which describe the strongly connected components of the graph, is built. These substrings are determined from the characters string, which is transmitted from the AR to the AE. Basic structures for the mosaics are defined. Rules are given for the identification of such structures. These rules are used by the AE for the recreation of the original graph. The algorithm of AR may consist of two stages. At the first stage, if the AR has been placed on some internal node of the graph, then it first has to reach the boundary of the graph. The first step may be omitted if the node of its initial placement will be a boundary node. At the second stage the AR passes the graph along its border and delivers the string of the directions to the AE. Algorithm of the AE is composed of a main and a subordinate algorithms. The basic algorithm, by scanning the string of directions, selects such fragments, which correspond to strongly connected subgraphs and bridges. It handles them with the help of the subordinate algorithm. It is shown that the algorithms allow recognizing the graph structure up to isomorphism. Capacitive and time complexities of the algorithms are given. Рассмотрена задача описания структуры графа специального вида без дыр, состоящего из не- скольких связных компонентов и мостов, на основе информации, полученной при обходе его по границе. Описан алгоритм решения задачи, приведены оценки его временной и емкостной сложности. |
|
| Date |
2013-09-16T12:13:17Z
2013-09-16T12:13:17Z 2013 |
|
| Type |
Article
|
|
| Identifier |
Наукові праці Донецького національного технічного університету. Серія: Обчислювальна техніка та автоматизація. Випуск 1 (24). - Донецьк, ДонНТУ, 2013. С - 176-183
2075-4272 УДК 519.7 http://ea.donntu.edu.ua/handle/123456789/22594 |
|
| Publisher |
Донецький національний технічний університет
|
|