Вас вітає Інтернет конференція!
Вітаємо на нашому сайті
АЛГОРИТМ ПРИМА ПОБУДОВИ МІНІМАЛЬНОГО КІСТЯКОВОГО ДЕРЕВА ДЛЯ ЗВАЖЕНОГО ЗВ’ЯЗНОГО НЕОРІЄНТОВАНОГО ГРАФА
02.11.2021 23:07
[1. Інформаційні системи і технології]
Автор: Долинний Д.І., студент, кафедра прикладної математики, Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського»
Постановка задачі.
Нехай G = (V, E) – зважений зв’язний неорієнтований граф. Потрібно побудувати мінімальне кістякове дерево G.
Опис алгоритму.
Вхідні дані: зважений зв’язний неорієнтований граф G = (V, E).
Вихідні дані: множина дуг, що складає мінімальне кістякове дерево для даного графа.
Вибирається ініціальний вузол. Жадним способом обирається суміжний з мінімальною вагою. Дуга між ініціальним та приєднаним вузлом додається до вихідної множини.
Кістякове дерево утворюється як послідовність розширюваних піддерев. Щоразу для додавання обирається оптимальна дуга, котра не входить до вихідної множини.
Відбувається |V| – 1 ітерацій приєднання. Для кожної з них ініціальним вважається щойно приєднаний. У результаті жадним способом збудовано мінімальне кістякове дерева для відповідного зваженого зв’язного неорієнтованого графа.
Часова складність залежить від вибору структур даних для виконання алгоритму: матриця вагів, черга з пріоритетами як невпорядкований масив: O(|V|^2); списки суміжності, неспадна піраміда : O(|E|log|V|).
Алгоритм Прима побудови мінімального кістякового дерева для зваженого зв’язного неорієнтованого графа демонструє використання жадібного методу як ефективного способу теоретичної інформатики для вирішення задачі із заданої предметної області.
Література:
1. Ткачук В.М. Алгоритми i структура даних: Навчальний посiбник / В.М.Ткачук. – Iвано-Франкiвськ : Видавництво Прикарпатського нацiонального унiверситету iменi Василя Стефаника, 2016.-286 с.
2. Кузьменко І. М. Теорія графів. — Київ: КПІ ім. Ігоря Сікорського, 2020. — 71 с.
3. Коротєєва Т. О. Алгоритми та структури даних : навч. посібник / Т. О. Коротєєва. – Львів : Видавництво Львівської політехніки, 2014. – 280 с.
________________
Науковий керівник: Федотов Вячеслав Віталійович, старший викладач кафедри загальної фізики фізико-математичного факультету Національного технічного університету України "Київський політехнічний інституту імені Ігоря Сікорського"
Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License
Знайшли помилку? Виділіть помилковий текст мишкою і натисніть Ctrl + Enter
Інші наукові праці даної секції
-
АНДРОЇД-ДОДАТОК ДЛЯ ОПТИМІЗАЦІЇ ТУРИСТИЧНИХ УРБАНІСТИЧНИХ МАРШРУТІВ
13.11.2021 10:33 -
ДОСЛІДЖЕННЯ СУЧАСНИХ ПРОВАЙДЕРІВ ХМАРНИХ ТЕХНОЛОГІЙ ТА ПУБЛІКАЦІЯ ВЕБ-ДОДАТКУ У ХМАРІ
13.11.2021 10:24 -
СТРУКТУРНИЙ СИНТЕЗ БАЗИ ЗНАНЬ СИСТЕМИ ПІДТРИМКИ ПРИЙНЯТТЯ РІШЕНЬ НА ОСНОВІ НЕЙРОННОЇ МЕРЕЖІ
13.11.2021 10:03 -
АКТУАЛЬНІСТЬ ОБРОБКИ ТА АНАЛІЗУ ВЕЛИКИХ ДАНИХ
13.11.2021 09:59 -
СУЧАСНІ МЕТОДИ ТА ЗАСОБИ ЗАБЕЗПЕЧЕННЯМ БЕЗПЕКИ ІНФОРМАЦІЙНО-ТЕЛЕКОМУНІКАЦІЙНИХ МЕРЕЖ ТА БЕЗПЕКИ НАСЕЛЕННЯ
13.11.2021 09:54
Конференції
Конференції 2024
Конференції 2023
Конференції 2022
Конференції 2021
