Search academic texts

Information × Registration Number 2124U009267, Article popup.category Опубліковано, Стаття Title METHOD OF CREATING A MINIMAL SPANNING TREE ON AN ARBITRARY SUBSET OF VERTICES OF A WEIGHTED UNDIRECTED GRAPH popup.author Бацамут В. М.Годлевський С. О.Бабков Ю. П.Морквін Д. А.Batsamut V. M.Hodlevsky S. O.Babkov Yu. P.Morkvin D. A. popup.publication 02-04-2024 popup.source_user Журнал "Радіоелектроніка, інформатика, управління" (Національний університет "Запорізька політехніка") popup.source https://ric.zp.edu.ua/article/view/301007 popup.publisher National University "Zaporizhzhia Polytechnic" Description Актуальність. Актуальність статті обумовлюється потребою у подальшому розвитку моделей оптимального відновлення зв’язності мережних об’єктів, що зазнали фрагментації внаслідок надзвичайних ситуацій різного характеру походження. Запропонований у статті метод усуває проблемну ситуацію, що полягає у необхідності мінімізації обсягу відновлювальних робіт (загальних фінансових витрат) при оперативному відновленні зв’язності обраної підмножини елементів мережевого об’єкту після його фрагментації. Мета роботи полягає у розробленні методу побудови мінімального кістякового дерева на довільній підмножині вершин зваженого неорієнтованого графу для мінімізації обсягу відновлювальних робіт і/або загальних фінансових витрат при оперативному відновленні зв’язності елементів, які мають вищий рівень важливості в структурі фрагментованого мережного об’єкту. Метод. Розроблений метод заснований на ідеї пошуку в структурі модельного неорієнтованого графа локальних мінімумів з використанням вершин графу, що не входять до переліку базових вершин, які потрібно об’єднати мінімальним кістяковим деревом. Під час пошуку локальних мінімумів використовується поняття рівностороннього трикутника та радіальної структури в такому трикутнику. При цьому розрізняються чотири типи підструктур, які забезпечують локальні мінімуми: перші, ті що мають одну спільну базову вершину; другі, ті що мають дві спільні базові вершини; треті, ті що мають три спільні базові вершини; четверті, ті що не мають спільних базових вершин – знаходяться в різних частинах модельного графа. Ті вершини, що не входять до переліку базових, але через які забезпечуються локальні мінімуми, додаються до складу базових. Інші вершини (небазові) разом з інцидентними їм ребрами видаляються з структури модельного графа. Далі, на отриманій таким чином структурі, одним із відомих методів побудови кістякових дерев, будується мінімальне кістякове дерево, яке поєднує набір базових вершин. Результати. 1) Розроблено метод побудови мінімального кістякового дерева на довільній підмножині вершин зваженого неорієнтованого графа. 2) Запропонована сукупність критеріїв для визначення локальних мінімумів в структурі модельного графа. 3) Виконано верифікацію методу на тестових задачах. Висновки. Проведені теоретичні дослідження та низка експериментів підтверджують працездатність розробленого методу. Рішення, що виробляються із використанням розробленого методу, є точними, що дозволяє рекомендувати його до практичного використання при визначенні стратегій відновлення зв’язності фрагментованих мережевих об’єктів. popup.nrat_date 2026-02-26 Close