The properties of compression of defining pair for deterministic graphs

In this article, we consider an algorithm for compressing a pair that is defining for a deterministic graph and the properties of this algorithm. Deterministic graphs are actively used as a model of many software objects, information processes, digital network topology, etc. The proposed algorithm is associated with the linguistic presentation of deterministic graphs by two sets of words of a special kind (the “pair”): the first set describes the graph cycles, and the second set describes its leaf vertices. The basis of the linguistic representation is the algorithm, which, given a pair, either constructs a deterministic graph for which this pair is the presentation or informs that it is impossible to do so. We have also developed an algorithm for constructing a special pair for any deterministic graph, called a canonical pair, and proved that the canonical pair is a presentation of this graph. In this article, we propose elementary transformations of a pair that is a presentation of a certain deterministic graph (the so-called “correct pair”). As a result of these transformations, the graph, which is a presentation by the original pair, is isomorphic to the graph, which is a presentation by the result of elementary transformations with the original pair. On the basis of these elementary transformations, we develop an algorithm for compressing the correct pair. It is proved that the result of compression is equal to the canonical pair of the graph, which is the presentation by the original pair; this is the main result of this article. The properties of this algorithm are also presented, in particular, it is shown that the smallest pair in terms of power and volume of each component, which is a presentation of an arbitrary deterministic graph, is its canonical pair. Based on the compression algorithm, a solution to the problem of pair characterization for a graph is proposed: the task of determining whether a given pair is a presentation of a given deterministic graph, in the case of correctness of the pair, is reduced to constructing a compression of the given pair, the canonical pair for a given graph, and comparing these pairs. If the above pairs are equal, then the given pair is a presentation of the given deterministic graph, otherwise the given pair is not a presentation of the given deterministic graph. In our opinion, in a computational sense, the proposed method is simpler than constructing a graph based on a given pair and then comparing it with a given graph. Further directions of research on this topic are also outlined. The results will allow the use of new methods and algorithms to solve problems of analyzing graphs with labeled vertices.