|
|
eaDonNTU, Donetsk >
Научные труды ДонНТУ >
Серія: Обчислювальна техніка та автоматизація >
Випуск 1 (24)'2013 >
Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот ресурс:
http://ea.donntu.ru/handle/123456789/22594
|
| Название: | РАСПОЗНАВАНИЕ ГРАФА МОЗАИЧНОЙ СТРУКТУРЫ, СОСТОЯЩЕГО ИЗ СВЯЗНЫХ КОМПОНЕНТОВ И МОСТОВ, КОЛЛЕКТИВОМ АГЕНТОВ |
| Другие названия: | Recognition of a Mosaic-structured Graph, Consisting of the Linked Components and Bridges, by the Collective of Agents
Розпізнавання графа мозаїчної структури, що складається зі зв’язаних компонентів та мо- стів, колективом агентів |
| Авторы: | Шатохина, Н.К.
Шатохин, П.А.
Shatokhina, N.K.
Shatokhin, P.A.
Шатохіна, Н.К.
Шатохін, П.О. |
| Ключевые слова: | мозаїка
лабіринт
комутативна група
агент
алгоритм
puzzle
maze
commutative group
agent
algorithm
мозаика
лабиринт
коммутативная группа
агент
алгоритм |
| Дата публикации: | 2013 |
| Издатель: | Донецький національний технічний університет |
| Библиографическое описание: | Наукові праці Донецького національного технічного університету. Серія: Обчислювальна техніка та автоматизація. Випуск 1 (24). - Донецьк, ДонНТУ, 2013. С - 176-183 |
| Аннотация: | Рассмотрена задача описания структуры графа специального вида без дыр, состоящего из не-
скольких связных компонентов и мостов, на основе информации, полученной при обходе его по границе. Описан алгоритм решения задачи, приведены оценки его временной и емкостной
сложности. |
| Описание: | 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. |
| URI: | http://ea.donntu.edu.ua/handle/123456789/22594 |
| ISSN: | 2075-4272 |
| Располагается в коллекциях: | Випуск 1 (24)'2013
|
Все ресурсы в архиве электронных ресурсов защищены авторским правом, все права сохранены.
|
