Abonnement à la biblothèque: Guest
Journal of Automation and Information Sciences

Publication de 12  numéros par an

ISSN Imprimer: 1064-2315

ISSN En ligne: 2163-9337

SJR: 0.173 SNIP: 0.588 CiteScore™:: 2

Indexed in

The Solution of the Question of the Isomorphism of Non-Oriented Trees by the Method of Generating Isomorphic Structures

Volume 52, Numéro 8, 2020, pp. 68-79
DOI: 10.1615/JAutomatInfScien.v52.i8.60
Get accessGet access

RÉSUMÉ

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.

RÉFÉRENCES
  1. Emelichev V.A., Melnikov O.I., Sarvanov V.I., Tyshkevich R.I., Lectures on graph theory [in Russian], Nauka, Moscow, 1990.

  2. Evstigneev V.A., Kasianov V.N., Graph theory: algorithms for processing trees [in Russian], Nauka, Novosibirsk, 1994.

  3. Prosolupov E.V., A course of lectures on discrete mathematics, Part 3, Theory of algorithms and graph theory [in Russian], Izdatelstvo S.-Peterb. un-ta, St. Petersburg, 2014.

  4. Bollobas B., Modern graph theory, Springer, 2013.

  5. Gross J.L., Yellen J., Zhang P., Handbook of graph theory, CRC Press, 2014.

  6. McKay B.D., Practical graph isomorphism, J. Symbolic Computation, 2014, 60, 94-112.

CITÉ PAR
  1. Ivaneshkin A. I., Universal Information Software Technology for Non-Oriented Mixed Forests, Cybernetics and Systems Analysis, 58, 3, 2022. Crossref

Portail numérique Bibliothèque numérique eBooks Revues Références et comptes rendus Collections Prix et politiques d'abonnement Begell House Contactez-nous Language English 中文 Русский Português German French Spain