Method of graph vertices differentiation and solution of the isomorphism problem in geoinformatics
The urgency of the discussed issue is caused by the fact, that known approaches for the structures similarity estimation are limited by using a set of indirect properties. Effective similarity estimation algorithms on the basis of direct properties are necessary. Such algorithms can be applied for d...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | Russian |
| Published: |
Tomsk Polytechnic University
2019-05-01
|
| Series: | Известия Томского политехнического университета: Инжиниринг георесурсов |
| Subjects: | |
| Online Access: | http://izvestiya-tpu.ru/archive/article/view/1663 |
| Summary: | The urgency of the discussed issue is caused by the fact, that known approaches for the structures similarity estimation are limited by using a set of indirect properties. Effective similarity estimation algorithms on the basis of direct properties are necessary. Such algorithms can be applied for data compression in geographic information systems and systems of ecological monitoring if they are represented on vector map, or for pattern recognition and many other applications. Research of application of direct properties for similarity estimation on the basis of the combination of compared graphs and selecting equal parts as isomorphic subgraphs are almost absent. The problem of determining the partial isomorphism without exhaustive search permutations of similarity is considered unsolvable. Therefore researches of finding acceptable algorithms for solving this problem with limited count of permutations are relevant. The main aim of the study is to develop a method for determining the graphs structure similarity by selecting the highest common parts, i.e. highest partial isomorphism. The methods used in the study are based on the applied graph theory, theory of optimization and efficient algorithms development, modeling structures using automata models for vertices differentiation. The results. Introduced basic concepts and formulated provisions of the concept of the graphs structure similarity estimation based on a combination of vertices and selection of equal subgraphs ? partial isomorphism. Ideas of the vertices differentiation method are suggested to be used for reducing algorithm complexity. The method of the interdependent vertices differentiation is developed, which allows to form the similarity substitution and partial isomorphism. The algorithm of searching the similarity substitutions, relative to pair of vertices, and the algorithm of selection of substitution with highest partial isomorphism are developed. The algorithm of searching similarity substitution on the basis of the interdependent vertices differentiation is shown at the example of two graphs similarity estimation. |
|---|---|
| ISSN: | 2500-1019 2413-1830 |