Complete graph invariant and algorithm of its computation
The relevance of the discussed issue is caused by the fact, that in graph theory, since the mid of the last century, all attempts to find the form of complete invariant and to develop the effective algorithm for it computation have been failed. The proposed solution of the problem will contribute to...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | Russian |
| Published: |
Tomsk Polytechnic University
2019-05-01
|
| Series: | Известия Томского политехнического университета: Инжиниринг георесурсов |
| Subjects: | |
| Online Access: | http://izvestiya.tpu.ru/archive/article/view/1490 |
| Summary: | The relevance of the discussed issue is caused by the fact, that in graph theory, since the mid of the last century, all attempts to find the form of complete invariant and to develop the effective algorithm for it computation have been failed. The proposed solution of the problem will contribute to development of methods of invariant representation and graphs structure analysis. The main aim of the study is to form theoretical basis of independent integration method of codes of structural differences and to develop the effective algorithm for complete invariant computation. The methods of the study are based on graph theory and methods of free and dependent integration of codes of structural differences for obtaining integral descriptors of vertices of abstract graph structures. The results. The author has proposed a new rule of assigning structural differences code to differentiate graph vertices. The rule is simple, it is represented as an independent encoding system and ensures the obtain the integral structure descriptor (ISD), invariant with respect to the vertices original numbering. Based on this method the effective algorithm of complete graph computation was developed. It is shown, that even for the worst cases the computation complexity is limited by polynomial evaluation. Software GraphISD was written on Java language. It was used for experimental researches of algorithm effectiveness. The experiments showed that the proposed complete graph invariant and algorithm of its computation are capable of working effectively with libraries of graph invariants, containing up to 5000 vertices, of distinguishing isomorphic graphs based on comparison of the complete invariants, of forming isomorphism substitutions and initial graph representations. |
|---|---|
| ISSN: | 2500-1019 2413-1830 |