1. Електронний архів ДонНТУ м.Покровськ
  2. Наукові видання ДонНТУ
  3. Наукові періодичні видання
  4. Серія: Обчислювальна техніка та автоматизація
  5. Випуск 1 (24)'2013
Будь ласка, використовуйте цей ідентифікатор, щоб цитувати або посилатися на цей матеріал: https://ea.donntu.edu.ua/jspui/handle/123456789/22594
Повний запис метаданих
Поле DCЗначенняМова
dc.contributor.authorШатохина, Н.К.-
dc.contributor.authorШатохин, П.А.-
dc.contributor.authorShatokhina, N.K.-
dc.contributor.authorShatokhin, P.A.-
dc.contributor.authorШатохіна, Н.К.-
dc.contributor.authorШатохін, П.О.-
dc.date.accessioned2013-09-16T12:13:17Z-
dc.date.available2013-09-16T12:13:17Z-
dc.date.issued2013-
dc.identifier.citationНаукові праці Донецького національного технічного університету. Серія: Обчислювальна техніка та автоматизація. Випуск 1 (24). - Донецьк, ДонНТУ, 2013. С - 176-183en_US
dc.identifier.issn2075-4272-
dc.identifier.otherУДК 519.7-
dc.identifier.urihttp://ea.donntu.edu.ua/handle/123456789/22594-
dc.descriptionThe 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.en_US
dc.description.abstractРассмотрена задача описания структуры графа специального вида без дыр, состоящего из не- скольких связных компонентов и мостов, на основе информации, полученной при обходе его по границе. Описан алгоритм решения задачи, приведены оценки его временной и емкостной сложности.en_US
dc.publisherДонецький національний технічний університетen_US
dc.subjectмозаїкаen_US
dc.subjectлабіринтen_US
dc.subjectкомутативна групаen_US
dc.subjectагентen_US
dc.subjectалгоритмen_US
dc.subjectpuzzleen_US
dc.subjectmazeen_US
dc.subjectcommutative groupen_US
dc.subjectagenten_US
dc.subjectalgorithmen_US
dc.subjectмозаикаen_US
dc.subjectлабиринтen_US
dc.subjectкоммутативная группаen_US
dc.subjectагентen_US
dc.subjectалгоритмen_US
dc.titleРАСПОЗНАВАНИЕ ГРАФА МОЗАИЧНОЙ СТРУКТУРЫ, СОСТОЯЩЕГО ИЗ СВЯЗНЫХ КОМПОНЕНТОВ И МОСТОВ, КОЛЛЕКТИВОМ АГЕНТОВen_US
dc.title.alternativeRecognition of a Mosaic-structured Graph, Consisting of the Linked Components and Bridges, by the Collective of Agentsen_US
dc.title.alternativeРозпізнавання графа мозаїчної структури, що складається зі зв’язаних компонентів та мо- стів, колективом агентівen_US
dc.typeArticleen_US
Розташовується у зібраннях:Випуск 1 (24)'2013

Файли цього матеріалу:
Файл Опис РозмірФормат 
шатохина.pdf431,44 kBAdobe PDFПереглянути/Відкрити
Показати базовий опис матеріалу Перегляд статистики


Усі матеріали в архіві електронних ресурсів захищені авторським правом, всі права збережені.