Донецький національний технічний університет
Будь ласка, використовуйте цей ідентифікатор, щоб цитувати або посилатися на цей матеріал:
https://ea.donntu.edu.ua/jspui/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 |
Файли цього матеріалу:
| Файл | Опис | Розмір | Формат | |
|---|---|---|---|---|
| шатохина.pdf | 431,44 kB | Adobe PDF | Переглянути/Відкрити |
Усі матеріали в архіві електронних ресурсів захищені авторським правом, всі права збережені.