АЛГОРИТМ ПРИМА ПОБУДОВИ МІНІМАЛЬНОГО КІСТЯКОВОГО ДЕРЕВА ДЛЯ ЗВАЖЕНОГО ЗВ’ЯЗНОГО НЕОРІЄНТОВАНОГО ГРАФА - Scientific conference
Main page
UA RU EN

Congratulation from Internet Conference!

Hello

Рік заснування видання - 2011

АЛГОРИТМ ПРИМА ПОБУДОВИ МІНІМАЛЬНОГО КІСТЯКОВОГО ДЕРЕВА ДЛЯ ЗВАЖЕНОГО ЗВ’ЯЗНОГО НЕОРІЄНТОВАНОГО ГРАФА

02.11.2021 23:07

[1. Information systems and technologies]

Author: Долинний Д.І., студент, кафедра прикладної математики, Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського»


Постановка задачі.

Нехай 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 Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License
допомога Знайшли помилку? Виділіть помилковий текст мишкою і натисніть Ctrl + Enter

Another articles in this section

Сonferences

Conference 2024

Conference 2023

Conference 2022

Conference 2021



Міжнародна інтернет-конференція з економіки, інформаційних систем і технологій, психології та педагогіки

Наукова спільнота - інтернет конференції

:: LEX-LINE :: Юридична лінія

Інформаційне суспільство: технологічні, економічні та технічні аспекти становлення