Пошук академічних текстів

Інформація × Реєстраційний номер 2124U009267, Матеріали видань та локальних репозитаріїв Категорія Опубліковано, Стаття Назва роботи МЕТОД ПОБУДОВИ МІНІМАЛЬНОГО КІСТЯКОВОГО ДЕРЕВА НА ДОВІЛЬНІЙ ПІДМНОЖИНІ ВЕРШИН ЗВАЖЕНОГО НЕОРІЄНТОВАНОГО ГРАФА Автор Бацамут В. М.Годлевський С. О.Бабков Ю. П.Морквін Д. А.Batsamut V. M.Hodlevsky S. O.Babkov Yu. P.Morkvin D. A. Дата публікації 02-04-2024 Постачальник інформації Журнал "Радіоелектроніка, інформатика, управління" (Національний університет "Запорізька політехніка") Першоджерело https://ric.zp.edu.ua/article/view/301007 Видання National University "Zaporizhzhia Polytechnic" Опис Актуальність. Актуальність статті обумовлюється потребою у подальшому розвитку моделей оптимального відновлення зв’язності мережних об’єктів, що зазнали фрагментації внаслідок надзвичайних ситуацій різного характеру походження. Запропонований у статті метод усуває проблемну ситуацію, що полягає у необхідності мінімізації обсягу відновлювальних робіт (загальних фінансових витрат) при оперативному відновленні зв’язності обраної підмножини елементів мережевого об’єкту після його фрагментації. Мета роботи полягає у розробленні методу побудови мінімального кістякового дерева на довільній підмножині вершин зваженого неорієнтованого графу для мінімізації обсягу відновлювальних робіт і/або загальних фінансових витрат при оперативному відновленні зв’язності елементів, які мають вищий рівень важливості в структурі фрагментованого мережного об’єкту. Метод. Розроблений метод заснований на ідеї пошуку в структурі модельного неорієнтованого графа локальних мінімумів з використанням вершин графу, що не входять до переліку базових вершин, які потрібно об’єднати мінімальним кістяковим деревом. Під час пошуку локальних мінімумів використовується поняття рівностороннього трикутника та радіальної структури в такому трикутнику. При цьому розрізняються чотири типи підструктур, які забезпечують локальні мінімуми: перші, ті що мають одну спільну базову вершину; другі, ті що мають дві спільні базові вершини; треті, ті що мають три спільні базові вершини; четверті, ті що не мають спільних базових вершин – знаходяться в різних частинах модельного графа. Ті вершини, що не входять до переліку базових, але через які забезпечуються локальні мінімуми, додаються до складу базових. Інші вершини (небазові) разом з інцидентними їм ребрами видаляються з структури модельного графа. Далі, на отриманій таким чином структурі, одним із відомих методів побудови кістякових дерев, будується мінімальне кістякове дерево, яке поєднує набір базових вершин. Результати. 1) Розроблено метод побудови мінімального кістякового дерева на довільній підмножині вершин зваженого неорієнтованого графа. 2) Запропонована сукупність критеріїв для визначення локальних мінімумів в структурі модельного графа. 3) Виконано верифікацію методу на тестових задачах. Висновки. Проведені теоретичні дослідження та низка експериментів підтверджують працездатність розробленого методу. Рішення, що виробляються із використанням розробленого методу, є точними, що дозволяє рекомендувати його до практичного використання при визначенні стратегій відновлення зв’язності фрагментованих мережевих об’єктів. Додано в НРАТ 2026-02-26 Закрити