Рассмотрена распределенная сеть, топология которой описана неориентированным графом. Сеть может сама изменять свою топологию, используя специальные «команды», подаваемые ее узлами. В работе предложена предельно локальная атомарная трансформация acb изменения конца c ребра ac, «движущегося» вдоль ребра cb от вершины c к вершине b. В результате этой операции ребро ac удаляется, а ребро ab добавляется. Такая трансформация выполняется по «команде» от общей вершины c двух смежных ребер ac и cb. Показано, что из любого дерева можно получить любое другое дерево с тем же множеством вершин, использовав только атомарные трансформации. Если степени вершин дерева ограничены числом d (d3), то трансформация не нарушает этого ограничения. В качестве примера цели такой трансформации рассмотрены задачи максимизации и минимизации индекса Винера дерева с ограниченной степенью вершин без изменения множества его вершин. Индекс Винера – это сумма попарных расстояний между вершинами графа. Максимальный индекс Винера имеет линейное дерево (дерево с двумя листовыми вершинами). Для корневого дерева с минимальным индексом Винера определены его вид и способ вычисления числа вершин в ветвях соседей корня. Предложены два распределенных алгоритма: трансформации дерева в линейное дерево и трансформации линейного дерева в дерево с минимальным индексом Винера. Доказано, что оба алгоритма имеют сложность не выше 2n–2, где n – число вершин дерева. Также рассмотрена трансформация произвольных неориентированных графов, в которых могут быть циклы, кратные ребра и петли, без ограничения на степени вершин. Показано, что любой связный граф с n вершинами может быть преобразован в любой другой связный граф с k вершинами и тем же числом ребер за время не более 2(n+k)–2.
We consider a distributed network whose topology is described by an undirected graph. The network itself can change its topology, using special “commands” provided by its nodes. The work proposes an extremely local atomic transformation acb of a change the end c of the edge ac, “moving” along the edge cb from vertex c to vertex b. As a result of this operation, the edge ac is removed, and the edge ab is added. Such a transformation is performed by a “command” from a common vertex c of two adjacent edges ac and cb. It is shown that from any tree you can get any other tree with the same set of vertices using only atomic transformations. If the degrees of the tree vertices are bounded by the number d (d 3), then the transformation does not violate this restriction. As an example of the purpose of such a transformation, the problems 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 pairwise distances between the vertices of a 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 for calculating the number of vertices in the branches of the neighbors of the root are determined. Two distributed algorithms are proposed: transforming a tree into a linear tree and transforming a linear tree into a tree with a minimum Wiener index. It is proved that both algorithms have complexity no higher than 2n–2, where n is the number of tree vertices. We also consider the transformation of arbitrary undirected graphs, in which there can be cycles, multiple edges and loops, without restricting the degree of the vertices. It is shown that any connected graph with n vertices can be transformed into any other connected graph with k vertices and the same number of edges in no more than 2(n+k)–2.
The authors declare that there are no conflicts of interest present.