Решение вопроса изоморфизма неориентированных деревьев методом генерации изоморфных структур
Розроблено метод і реалізуючі його програмні засоби оцінки ізоморфності пари неорієнтованих дерев з довільною структурою і ненумерованими вершинами, загальне число яких не перевищує значення 65536. Зв'язок користувача із засобами здійснюється на візуально-ментальному (аналогічно грі «LEGO») рів...
Saved in:
| Published in: | Проблемы управления и информатики |
|---|---|
| Date: | 2020 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2020
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/208768 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Решение вопроса изоморфизма неориентированных деревьев методом генерации изоморфных структур / А.И. Иванешкин // Проблемы управления и информатики. — 2020. — № 4. — С. 34-46. — Бібліогр.: 6 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-208768 |
|---|---|
| record_format |
dspace |
| spelling |
Иванешкин, А.И. 2025-11-05T16:40:24Z 2020 Решение вопроса изоморфизма неориентированных деревьев методом генерации изоморфных структур / А.И. Иванешкин // Проблемы управления и информатики. — 2020. — № 4. — С. 34-46. — Бібліогр.: 6 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/208768 519.172.1 10.1615/JAutomatInfScien.v52.i8.60 Розроблено метод і реалізуючі його програмні засоби оцінки ізоморфності пари неорієнтованих дерев з довільною структурою і ненумерованими вершинами, загальне число яких не перевищує значення 65536. Зв'язок користувача із засобами здійснюється на візуально-ментальному (аналогічно грі «LEGO») рівні спілкування, що мінімізує його участь в процесі виконання завдання. Основою розробки є створений метод ізоморфної реконфігурації, який для кожної обраної в якості нового кореня вершини дозволяє отримати чотири різні варіанти структур, ізоморфних початковій структурі дерева. Для практичного застосування засоби не вимагають використання матриць суміжності або будь-яких інших засобів формалізованого опису (подання) структури дерев, а також їх подальшого застосування при виконанні над останньою різного роду операцій перетворення. Вони також виключають необхідність освоєння і використання в роботі стандартизованих мов опису графів, спеціалізованих програм побудови їх структури, візуалізації тощо. За бажанням користувача, два варіанти матриці суміжності можна сформувати програмою в кінці роботи і записати в файли з розширеннями * .cam, умовно, класичний (classic) варіант і *.tam, умовно, усічений (truncated) варіант, що включає елементи лише верхньої частини матриці. Всі дані N-вершинного дерева (без урахування додаткових параметрів), що потрібні для вирішення завдання, зберігаються в файлі бінарного типу, загального обсягу 4N символів char-типу. Метод сприяє зменшенню загальних витрат ресурсів і часу виконання завдання і відповідне доопрацювання нині існуючої версії засобів зробить можливою роботу зі структурами дерев, що мають практично необмежену кількість вершин і довільну орієнтацію ребер. The method and its software implementation tools for assessing the isomorphism of a pair of non-oriented trees with an arbitrary structure and unnumbered nodes, the total number of which does not exceed the value of 65536, are developed. The user communicates with the tools at the visual-mental (similar to the «LEGO» game) communication level, minimizing his participation in the process of solving the problem. The basis of development is the created method of isomorphic reconfiguration, which, for each node selected as a new root, allows to obtain four different variants of structures isomorphic to the original tree structure. For practical use, the tools do not require the use of adjacency matrices or any other means of a formalized description (representation) of the structure of trees and their subsequent application when performing its various transformations. They also eliminate the need for mastering and using standardized graph description languages, specialized programs for constructing their structure, visualization, etc. If the user wishes, two variants of the adjacency matrix can be generated by the program at the end of the work and written to files with the extensions * .cam, conditionally, the classic option and * .tam, conditionally, the truncated option containing elements only of the upper part of the matrix. All the data of the N-node tree required for solving the problem (without taking into account additional parameters) is stored in a binary file type, with a total volume of 4N char-type characters. The method helps to reduce the total cost of resources and time to solve the problem and the corresponding refinement of the current version of the tools will make it possible to work with tree structures that have an almost unlimited number of nodes and arbitrary orientation of the edges. ru Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Методы оптимизации и оптимальное управление Решение вопроса изоморфизма неориентированных деревьев методом генерации изоморфных структур Вирішення питання ізоморфізму неорієнтованих дерев методом генерації ізоморфних структур Тhe solution of the question of the isomorphism of non-oriented trees by the method of generating isomorphic structures Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Решение вопроса изоморфизма неориентированных деревьев методом генерации изоморфных структур |
| spellingShingle |
Решение вопроса изоморфизма неориентированных деревьев методом генерации изоморфных структур Иванешкин, А.И. Методы оптимизации и оптимальное управление |
| title_short |
Решение вопроса изоморфизма неориентированных деревьев методом генерации изоморфных структур |
| title_full |
Решение вопроса изоморфизма неориентированных деревьев методом генерации изоморфных структур |
| title_fullStr |
Решение вопроса изоморфизма неориентированных деревьев методом генерации изоморфных структур |
| title_full_unstemmed |
Решение вопроса изоморфизма неориентированных деревьев методом генерации изоморфных структур |
| title_sort |
решение вопроса изоморфизма неориентированных деревьев методом генерации изоморфных структур |
| author |
Иванешкин, А.И. |
| author_facet |
Иванешкин, А.И. |
| topic |
Методы оптимизации и оптимальное управление |
| topic_facet |
Методы оптимизации и оптимальное управление |
| publishDate |
2020 |
| language |
Russian |
| container_title |
Проблемы управления и информатики |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Вирішення питання ізоморфізму неорієнтованих дерев методом генерації ізоморфних структур Тhe solution of the question of the isomorphism of non-oriented trees by the method of generating isomorphic structures |
| description |
Розроблено метод і реалізуючі його програмні засоби оцінки ізоморфності пари неорієнтованих дерев з довільною структурою і ненумерованими вершинами, загальне число яких не перевищує значення 65536. Зв'язок користувача із засобами здійснюється на візуально-ментальному (аналогічно грі «LEGO») рівні спілкування, що мінімізує його участь в процесі виконання завдання. Основою розробки є створений метод ізоморфної реконфігурації, який для кожної обраної в якості нового кореня вершини дозволяє отримати чотири різні варіанти структур, ізоморфних початковій структурі дерева. Для практичного застосування засоби не вимагають використання матриць суміжності або будь-яких інших засобів формалізованого опису (подання) структури дерев, а також їх подальшого застосування при виконанні над останньою різного роду операцій перетворення. Вони також виключають необхідність освоєння і використання в роботі стандартизованих мов опису графів, спеціалізованих програм побудови їх структури, візуалізації тощо. За бажанням користувача, два варіанти матриці суміжності можна сформувати програмою в кінці роботи і записати в файли з розширеннями * .cam, умовно, класичний (classic) варіант і *.tam, умовно, усічений (truncated) варіант, що включає елементи лише верхньої частини матриці. Всі дані N-вершинного дерева (без урахування додаткових параметрів), що потрібні для вирішення завдання, зберігаються в файлі бінарного типу, загального обсягу 4N символів char-типу. Метод сприяє зменшенню загальних витрат ресурсів і часу виконання завдання і відповідне доопрацювання нині існуючої версії засобів зробить можливою роботу зі структурами дерев, що мають практично необмежену кількість вершин і довільну орієнтацію ребер.
The method and its software implementation tools for assessing the isomorphism of a pair of non-oriented trees with an arbitrary structure and unnumbered nodes, the total number of which does not exceed the value of 65536, are developed. The user communicates with the tools at the visual-mental (similar to the «LEGO» game) communication level, minimizing his participation in the process of solving the problem. The basis of development is the created method of isomorphic reconfiguration, which, for each node selected as a new root, allows to obtain four different variants of structures isomorphic to the original tree structure. For practical use, the tools do not require the use of adjacency matrices or any other means of a formalized description (representation) of the structure of trees and their subsequent application when performing its various transformations. They also eliminate the need for mastering and using standardized graph description languages, specialized programs for constructing their structure, visualization, etc. If the user wishes, two variants of the adjacency matrix can be generated by the program at the end of the work and written to files with the extensions * .cam, conditionally, the classic option and * .tam, conditionally, the truncated option containing elements only of the upper part of the matrix. All the data of the N-node tree required for solving the problem (without taking into account additional parameters) is stored in a binary file type, with a total volume of 4N char-type characters. The method helps to reduce the total cost of resources and time to solve the problem and the corresponding refinement of the current version of the tools will make it possible to work with tree structures that have an almost unlimited number of nodes and arbitrary orientation of the edges.
|
| issn |
0572-2691 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/208768 |
| citation_txt |
Решение вопроса изоморфизма неориентированных деревьев методом генерации изоморфных структур / А.И. Иванешкин // Проблемы управления и информатики. — 2020. — № 4. — С. 34-46. — Бібліогр.: 6 назв. — рос. |
| work_keys_str_mv |
AT ivaneškinai rešenievoprosaizomorfizmaneorientirovannyhderevʹevmetodomgeneraciiizomorfnyhstruktur AT ivaneškinai viríšennâpitannâízomorfízmuneoríêntovanihderevmetodomgeneracííízomorfnihstruktur AT ivaneškinai thesolutionofthequestionoftheisomorphismofnonorientedtreesbythemethodofgeneratingisomorphicstructures |
| first_indexed |
2025-11-30T10:03:07Z |
| last_indexed |
2025-11-30T10:03:07Z |
| _version_ |
1850857137700339712 |