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

• Date: 2020
• Main Author: Ivaneshkin, A.I.
• Format: Article
• Language: English
• Published: V.M. Glushkov Institute of Cybernetics of NAS of Ukraine 2020
• Subjects: граф; дерево; неорієнтоване дерево; ізоморфізм
• Online Access: https://jais.net.ua/index.php/files/article/view/477
• Journal Title: Problems of Control and Informatics

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.