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

Authors

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

Abstract

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

Author Biographies

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

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

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

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

References

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

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

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

Downloads

Published

2023-07-18

Issue

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

Section

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