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

Yulia Terentyeva

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.

Full Text:

PDF (Russian)

References


B. Melnikov, V. Meshchanin, and Y. Terentyeva, “Implementation of optimality criteria in the design of communication networks, ”Journal of Physics: Conference Series, International Scientific Conference ICMSIT–2020: Metrological Support of Innovative Technological, ICMSIT-2020 (paper 3095), http://conf.domnit.ru/en/conferences/icmsit-2020-en/

Bulynin A.G., Melnikov B.F., Meshchanin, V.Y. and Terentyeva. Y.Y. Optimization problems arising in the design of high-dimensional communication networks, and some heuristic methods for their solution // Informatization and Communication, no. 1, pp. 34–40, 2020, https://elibrary.ru/item.asp?id=42839357 (in Russian).

B. Melnikov, “Discrete optimization problems – some new heuristic

approaches,” Proceedings – Eighth International Conference on High-

Performance Computing in Asia-Pacific Region, HPC Asia 2005, Beijing, 2005. pp. 73–80. doi: 10.1109/HPCASIA.2005.34

J. Kruskal “On the shortest spanning subtree of a graph and the traveling salesman problem,” Proceedings of the American Mathematical Society, vol. 7, no. 1, pp. 48–50, 1956, doi: 10.1090/S0002-9939-1956-0078686-7

T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to

Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN

-262-03293-7

R. Prim “Shortest connection networks and some generalizations,” Bell

System Technical Journal, vol. 36, no. 6, pp. 1389–1401, 1957, doi:

1002/j.1538-7305.1957.tb01515.x

Emelichev V, Melnikov О. Lectures on graph theory. -Мoscow.: - Science.-1990,-P.384. (in Russian)

Yashkardin V. IEEE 754 - binary floating point arithmetic standard // SoftElectro. - 2009.


Refbacks

  • There are currently no refbacks.


Abava  Absolutech Convergent 2020

ISSN: 2307-8162