Some theoretical issues related to the description of practical algorithms for constructing spanning trees

Abstract

The article discusses the issue of restoring the connectivity of a communication network in the case of its fragmentation with a certain criterion of optimality. As an optimality criterion, the total length of the edges being completed is taken, the weight of which is given by the metric in space and thereby determines the edge length. Such questions have both purely engineering applications and touch on the classical side of graph theory. Namely, the problem of defragmentation of the communication network, which arose as a result of both internal and external possible destabilizing factors, can be solved by constructing a spanning tree.

The author's programming of practical algorithms for restoring the connectivity of a communication network, which also includes classical algorithms (for example, Kruskal's algorithm for constructing a spanning tree), led to the question of the uniqueness of the solution for restoring network connectivity in the case of the metric version of the problem and provided that it is impossible to form new vertices (communication nodes). Experimentally, we obtained confirmation of the invariance of the starting vertex in the operation of the algorithm. A hypothesis was put forward on sufficient conditions for the uniqueness of a solution to the problem of reconnecting a communication network, as well as a hypothesis on sufficient conditions for the invariance of the starting vertex. A similar problem is reduced to proving the sufficiency of the conditions for the uniqueness of the construction of a minimal spanning tree in the case of a graph with a metric weight function. For the proof, the concepts of a family of a graph and a partition of a graph into families were introduced. This proof forms the substantive part of this article.

The considered property of the sufficiency of the uniqueness of the solution to the problem of restoring the connectivity of a communication network can be useful in designing real communication networks.