We consider a distributed network, the topology of which is described by a undirected tree without multiple edges and loops. The network itself can change its topology using special “commands” supplied by its nodes. The paper proposed an extremely local atomic transformation: the addition of an edge connecting the different ends of two adjacent edges, and the simultaneous removal of one of these edges. This transformation is performed by “command” from the common vertex of two adjacent edges. It is shown that any other tree can be obtained from any tree using only atomic transformations. If the degrees of the tree vertices are limited by the number d (d ≥ 3), then the transformation does not violate this restriction. As an example of the goal of such a transformation, the tasks of maximizing and minimizing the Wiener index of a tree with a limited degree of vertices without changing the set of its vertices are considered. The Wiener index is the sum of the pairwise distances between the vertices of the graph. The maximum Wiener index has a linear tree (a tree with two leaf vertices). For a root tree with a minimum Wiener index, its type and method of calculating the number of vertices in the branches of the neighbors of the root is determined. Two distributed algorithms are proposed: the transformation of a tree into a linear tree and the transformation of a linear tree into a tree with a minimum Wiener index. It is proved that both algorithms have complexity not higher than 2n - 2, where n is the number of tree vertices.

distributed network, transformation of graphs, Wiener index

Burdonov Igor Borisovich,  ,  orcid.org/0000-0001-9539-7853,  ISP RAS