Алгоритми знаходження мінімального покривного дерева в графах

Автор(и)

  • А.Р. Клименко Донецький національний університет імені Василя Стуса
  • В. М. Гончар Донецький національний університет імені Василя Стуса

Анотація

Мінімальне покривне (кістякове) дерево – це ациклічний зв’язний підграф, який містить усі вершини графа, на якому будується. Сума ваг ребер цього підграфа – мінімальна. Найбільш поширеними методами знаходження мінімального покривного дерева є: алгоритм Прима та алгоритм Крускала. Розглянемо нижче кожен із зазначених алгоритмів.

Біографії авторів

А.Р. Клименко , Донецький національний університет імені Василя Стуса

студентка 1 курсу спеціальності 122 «Комп’ютерні науки»

В. М. Гончар , Донецький національний університет імені Василя Стуса

асистент кафедри інформаційних технологій

Посилання

Мінімальне покривне дерево та алгоритми обчислення, URL: http://surl.li/hcizc

Алгоритм Прима, URL: https://www.mathros.net.ua/algorytm-pryma.html

Алгоритм Крускала, URL:https://www.mathros.net.ua/algorytm-kruskala.html

##submission.downloads##

Опубліковано

2023-07-18

Номер

Збірник тез доповідей - 2023 рік

Розділ

Секція 2 Алгоритмізація та розробка програмного забезпечення