ВИРІШЕННЯ ПИТАННЯ ІЗОМОРФІЗМУ НЕОРІЄНТОВАНИХ ДЕРЕВ МЕТОДОМ ГЕНЕРАЦІЇ ІЗОМОРФНИХ СТРУКТУР

ВИРІШЕННЯ ПИТАННЯ ІЗОМОРФІЗМУ НЕОРІЄНТОВАНИХ ДЕРЕВ МЕТОДОМ ГЕНЕРАЦІЇ ІЗОМОРФНИХ СТРУКТУР

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 (sim...

Повний опис

Збережено в:
Бібліографічні деталі
Дата:2020
Автор: Ivaneshkin, A.I.
Формат: Стаття
Мова:English
Опубліковано: V.M. Glushkov Institute of Cybernetics of NAS of Ukraine 2020
Теми:
граф
дерево
неорієнтоване дерево
ізоморфізм
Онлайн доступ:https://jais.net.ua/index.php/files/article/view/477
Теги: Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:Problems of Control and Informatics

Репозитарії

Problems of Control and Informatics
id oai:ojs2.jais.net.ua:article-477
record_format ojs
institution Problems of Control and Informatics
baseUrl_str
datestamp_date 2025-03-14T15:38:44Z
collection OJS
language English
topic граф
дерево
неорієнтоване дерево
ізоморфізм
spellingShingle граф
дерево
неорієнтоване дерево
ізоморфізм
Ivaneshkin, A.I.
ВИРІШЕННЯ ПИТАННЯ ІЗОМОРФІЗМУ НЕОРІЄНТОВАНИХ ДЕРЕВ МЕТОДОМ ГЕНЕРАЦІЇ ІЗОМОРФНИХ СТРУКТУР
topic_facet граф
дерево
неорієнтоване дерево
ізоморфізм
graph
tree
undirected tree
isomorphism
format Article
author Ivaneshkin, A.I.
author_facet Ivaneshkin, A.I.
author_sort Ivaneshkin, A.I.
title ВИРІШЕННЯ ПИТАННЯ ІЗОМОРФІЗМУ НЕОРІЄНТОВАНИХ ДЕРЕВ МЕТОДОМ ГЕНЕРАЦІЇ ІЗОМОРФНИХ СТРУКТУР
title_short ВИРІШЕННЯ ПИТАННЯ ІЗОМОРФІЗМУ НЕОРІЄНТОВАНИХ ДЕРЕВ МЕТОДОМ ГЕНЕРАЦІЇ ІЗОМОРФНИХ СТРУКТУР
title_full ВИРІШЕННЯ ПИТАННЯ ІЗОМОРФІЗМУ НЕОРІЄНТОВАНИХ ДЕРЕВ МЕТОДОМ ГЕНЕРАЦІЇ ІЗОМОРФНИХ СТРУКТУР
title_fullStr ВИРІШЕННЯ ПИТАННЯ ІЗОМОРФІЗМУ НЕОРІЄНТОВАНИХ ДЕРЕВ МЕТОДОМ ГЕНЕРАЦІЇ ІЗОМОРФНИХ СТРУКТУР
title_full_unstemmed ВИРІШЕННЯ ПИТАННЯ ІЗОМОРФІЗМУ НЕОРІЄНТОВАНИХ ДЕРЕВ МЕТОДОМ ГЕНЕРАЦІЇ ІЗОМОРФНИХ СТРУКТУР
title_sort вирішення питання ізоморфізму неорієнтованих дерев методом генерації ізоморфних структур
title_alt THE SOLUTION OF THE QUESTION OF THE ISOMORPHISM OF NON-ORIENTED TREES BY THE METHOD OF GENERATING ISOMORPHIC STRUCTURES
description 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.
publisher V.M. Glushkov Institute of Cybernetics of NAS of Ukraine
publishDate 2020
url https://jais.net.ua/index.php/files/article/view/477
work_keys_str_mv AT ivaneshkinai thesolutionofthequestionoftheisomorphismofnonorientedtreesbythemethodofgeneratingisomorphicstructures
AT ivaneshkinai viríšennâpitannâízomorfízmuneoríêntovanihderevmetodomgeneracííízomorfnihstruktur
AT ivaneshkinai solutionofthequestionoftheisomorphismofnonorientedtreesbythemethodofgeneratingisomorphicstructures
first_indexed 2025-10-30T02:49:15Z
last_indexed 2025-10-30T02:49:15Z
_version_ 1847373390361395200
spelling oai:ojs2.jais.net.ua:article-4772025-03-14T15:38:44Z THE SOLUTION OF THE QUESTION OF THE ISOMORPHISM OF NON-ORIENTED TREES BY THE METHOD OF GENERATING ISOMORPHIC STRUCTURES ВИРІШЕННЯ ПИТАННЯ ІЗОМОРФІЗМУ НЕОРІЄНТОВАНИХ ДЕРЕВ МЕТОДОМ ГЕНЕРАЦІЇ ІЗОМОРФНИХ СТРУКТУР Ivaneshkin, A.I. граф дерево неорієнтоване дерево ізоморфізм graph tree undirected tree isomorphism 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. Розроблено метод і реалізуючі його програмні засоби оцінки ізоморфності пари неорієнтованих дерев з довільною структурою і ненумерованими вершинами, загальне число яких не перевищує значення 65536. Зв'язок користувача із засобами здійснюється на візуально-ментальному (аналогічно грі «LEGO») рівні спілкування, що мінімізує його участь в процесі виконання завдання. Основою розробки є створений метод ізоморфної реконфігурації, який для кожної обраної в якості нового кореня вершини дозволяє отримати чотири різні варіанти структур, ізоморфних початковій структурі дерева. Для практичного застосування засоби не вимагають використання матриць суміжності або будь-яких інших засобів формалізованого опису (подання) структури дерев, а також їх подальшого застосування при виконанні над останньою різного роду операцій перетворення. Вони також виключають необхідність освоєння і використання в роботі стандартизованих мов опису графів, спеціалізованих програм побудови їх структури, візуалізації тощо. За бажанням користувача, два варіанти матриці суміжності можна сформувати програмою в кінці роботи і записати в файли з розширеннями * .cam, умовно, класичний (classic) варіант і *.tam, умовно, усічений (truncated) варіант, що включає елементи лише верхньої частини матриці. Всі дані N-вершинного дерева (без урахування додаткових параметрів), що потрібні для вирішення завдання, зберігаються в файлі бінарного типу, загального обсягу 4N символів char-типу. Метод сприяє зменшенню загальних витрат ресурсів і часу виконання завдання і відповідне доопрацювання нині існуючої версії засобів зробить можливою роботу зі структурами дерев, що мають практично необмежену кількість вершин і довільну орієнтацію ребер. V.M. Glushkov Institute of Cybernetics of NAS of Ukraine 2020-08-20 Article Article application/pdf https://jais.net.ua/index.php/files/article/view/477 10.1615/JAutomatInfScien.v52.i8.60 Міжнародний науково-технічний журнал "Проблеми керування та інформатики"; Том 65 № 4 (2020): Міжнародний науково-технічний журнал "Проблеми керування та інформатики"; 34-46 International Scientific Technical Journal "Problems of Control and Informatics; Том 65 № 4 (2020): International Scientific Technical Journal "PROBLEMS OF CONTROL AND INFORMATICS"; 34-46 International Scientific Technical Journal "Problems of Control and Informatics"; Vol. 65 No. 4 (2020): International Scientific Technical Journal "PROBLEMS OF CONTROL AND INFORMATICS"; 34-46 2786-6505 2786-6491 en https://jais.net.ua/index.php/files/article/view/477/547 Copyright (c) 2020 A.I. Ivaneshkin https://creativecommons.org/licenses/by-nc-nd/4.0

Схожі ресурси