АЛГОРИТМ ПРИМА ПОБУДОВИ МІНІМАЛЬНОГО КІСТЯКОВОГО ДЕРЕВА ДЛЯ ЗВАЖЕНОГО ЗВ’ЯЗНОГО НЕОРІЄНТОВАНОГО ГРАФА - Наукові конференції
Головна
UA RU EN

Вас вітає Інтернет конференція!

Вітаємо на нашому сайті

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

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

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

Інші наукові праці даної секції

Конференції

Конференції 2024

Конференції 2023

Конференції 2022

Конференції 2021



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

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

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

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