Method of creating a minimal spanning tree on an arbitrary subset of vertices of a weighted undirected graph

Abstract

EN: Context. The relevance of the article is determined by the need for further development of models for optimal restoration of the connectivity of network objects that have undergone fragmentation due to emergency situations of various origins. The method proposed in this article solves the problematic situation of minimizing the amount of restoration work (total financial costs) when promptly restoring the connectivity of a selected subset of elements of a network object after its fragmentation. The purpose of the study is to develop a method for creating a minimal spanning tree on an arbitrary subset of vertices of a weighted undirected graph to minimize the amount of restoration work and/or total financial costs when promptly restoring the connectivity of elements that have a higher level of importance in the structure of a fragmented network object. Method. The developed method is based on the idea of searching for local minima in the structure of a model undirected graph using graph vertices that are not included in the list of base vertices to be united by a minimal spanning tree. When searching for local minima, the concept of an equilateral triangle and a radial structure in such a triangle is used. In this case, there are four types of substructures that provide local minima: first, those with one common base vertex; second, those with two common base vertices; third, those with three common base vertices; fourth, those without common base vertices, located in different parts of the model graph. Those vertices that are not included in the list of basic ones, but through which local minima are ensured, are added to the basic ones. Other vertices (non-basic) along with their incident edges are removed from the structure of the model graph. Then, using one of the well-known methods of forming spanning trees, a minimal spanning tree is formed on the structure obtained in this way, which combines the set of base vertices. Results. 1) A method for creating a minimal spanning tree on an arbitrary subset of vertices of a weighted undirected graph has been developed. 2) A set of criteria for determining local minima in the structure of the model graph is proposed. 3) The method has been verified on test problems. Conclusions. The theoretical studies and several experiments confirm the efficiency of the developed method. The solutions developed using the developed method are accurate, which makes it possible to recommend it for practical use in determining strategies for restoring the connectivity of fragmented network objects. UK: Актуальність. Актуальність статті обумовлюється потребою у подальшому розвитку моделей оптимального відновлення зв’язності мережних об’єктів, що зазнали фрагментації внаслідок надзвичайних ситуацій різного характеру походження. Запропонований у статті метод усуває проблемну ситуацію, що полягає у необхідності мінімізації обсягу відновлювальних робіт (загальних фінансових витрат) при оперативному відновленні зв’язності обраної підмножини елементів мережевого об’єкту після його фрагментації. Мета роботи полягає у розробленні методу побудови мінімального кістякового дерева на довільній підмножині вершин зваженого неорієнтованого графу для мінімізації обсягу відновлювальних робіт і/або загальних фінансових витрат при оперативному відновленні зв’язності елементів, які мають вищий рівень важливості в структурі фрагментованого мережного об’єкту. Метод. Розроблений метод заснований на ідеї пошуку в структурі модельного неорієнтованого графа локальних мінімумів з використанням вершин графу, що не входять до переліку базових вершин, які потрібно об’єднати мінімальним кістяковим деревом. Під час пошуку локальних мінімумів використовується поняття рівностороннього трикутника та радіальної структури в такому трикутнику. При цьому розрізняються чотири типи підструктур, які забезпечують локальні мінімуми: перші, ті що мають одну спільну базову вершину; другі, ті що мають дві спільні базові вершини; треті, ті що мають три спільні базові вершини; четверті, ті що не мають спільних базових вершин – знаходяться в різних частинах модельного графа. Ті вершини, що не входять до переліку базових, але через які забезпечуються локальні мінімуми, додаються до складу базових. Інші вершини (небазові) разом з інцидентними їм ребрами видаляються з структури модельного графа. Далі, на отриманій таким чином структурі, одним із відомих методів побудови кістякових дерев, будується мінімальне кістякове дерево, яке поєднує набір базових вершин. Результати. 1) Розроблено метод побудови мінімального кістякового дерева на довільній підмножині вершин зваженого неорієнтованого графа. 2) Запропонована сукупність критеріїв для визначення локальних мінімумів в структурі модельного графа. 3) Виконано верифікацію методу на тестових задачах. Висновки. Проведені теоретичні дослідження та низка експериментів підтверджують працездатність розробленого методу. Рішення, що виробляються із використанням розробленого методу, є точними, що дозволяє рекомендувати його до практичного використання при визначенні стратегій відновлення зв’язності фрагментованих мережевих об’єктів.