Решение вопроса изоморфизма неориентированных деревьев методом генерации изоморфных структур

Abstract

Розроблено метод і реалізуючі його програмні засоби оцінки ізоморфності пари неорієнтованих дерев з довільною структурою і ненумерованими вершинами, загальне число яких не перевищує значення 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.