Анaлиз и cрaвнeниe aлгoритмoв пocтрoeния ocтoвнoгo дeрeвa минимaльнoгo вeca в нeoриeнтирoвaннoм грaфe
ВВЕДЕНИЕ
Впервые понятие граф ввёл в 1936 году венгерский математик Денни Кёниг. Но первая работа по теории графов принадлежала перу великого Леонарда Эйлера и была написана ещё в 1736 году. С помощью графов изображаются схемы различных дорог, линии воздушных сообщений, газопроводов, теплотрасс, электросетей, а также микросхемы, дискретные многошаговые процессы, системы различных бинарных отношений, химические структурные формулы и другие диаграммы и схемы. Применяются графы для решения задач химии, экономики, электротехники и автоматики. Также они широко используются в информатике и строительстве. Без графов сложно анализировать классификации в различных науках.
Теория графов — раздел дискретной математики, особенностью которого является геометрический подход к изучению объектов.
СОДЕРЖАНИЕ
ВВЕДЕНИЕ4
ГЛАВА 1. ТЕОРИЯ ГРАФОВ. ОСНОВНЫЕ ПОНЯТИЯ8
1.1 Понятие графа8
1.2 Деревья и циклы12
1.3 Представление графов в ЭВМ13
1.4 Неориентированный граф14
1.5 Алгоритм выделения остовного дерева15
1.6 Алгоритм Краскала16
1.7 Алгоритм Прима17
1.8 Алгоритм Борувки18
ГЛАВА 2. ПОСТАНОВКА И АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧИ ПОИСКА МИНИМАЛЬНОГО ОСТОВНОГО ДЕРЕВА20
2.1 Постановка задачи поиска минимального остовного дерева20
2.2 Построение минимального остовного графа21
2.3 Исследование алгоритмов поиска минимального остовного дерева22
ГЛАВА 3. ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ ПОИСКА МИНИМАЛЬНОГО ОСТОВНОГО ДЕРЕВА32
3.1 Подход применяемый к организации параллельных вычислений32
3.2 Оценка возможности организовать параллельные вычисления в алгоритме Краскала33
3.3 Особенности реализации алгоритма Краскала34
3.4 Оценка возможности организовать параллельные вычисления в алгоритме Прима35
3.5 Оценка возможности организовать параллельные вычисления в алгоритме Борувки36
ГЛАВА 4. АНАЛИЗ ЭФФЕКТИВНОСТИ АЛГОРИТМОВ ПОИСКА МИНИМАЛЬНОГО ОСТОВНОГО ДЕРЕВА39
4.1 Графы для тестирования алгоритмов39
4.2 Анализ последовательных алгоритмов поиска минимального остовного дерева42
4.3 Анализ параллельных алгоритмов поиска минимального остовного дерева48
4.4 Сравнение параллельных алгоритмов поиска MST52
ГЛАВА 5. Тестирование построения минимального остовного дерева по алгоритму Краскала54
5.1 Минимальное остовное дерево. Алгоритм Краскала54
5.2 Описание алгоритма Краскала54
5.3 Схема алгоритма Краскала55
5.4 Составление программы56
ЗАКЛЮЧЕНИЕ57
СПИСОК ИСТОЧНИКОВ И ЛИТЕРАТУРЫ59
ПРИЛОЖЕНИЕ61
СПИСОК ИСТОЧНИКОВ И ЛИТЕРАТУРЫ
1. Алгоритм Краскала [Электронный ресурс] URL: httр://urbаn-sаnjоо.nаrоd.ru/kruskаl.html (дата обращения: 11.01.2022).
2. Алгоритм Прима [Электронный ресурс] URL: httр://urbаn-sаnjоо.nаrоd.ru/рrim.html (дата обращения: 11.01.2022).
3. Кристофидес Н. Теория графов. Алгоритмический подход. — М.: Мир, 1978. — 432 с.
4. Минимальное остовное дерево [Электронный ресурс] URL: httр://е-mахх.ru/аlgо/mst_kruskаl (дата обращения: 12.01.2022).
5. Неориентированные графы [Электронный ресурс] URL: httр://www.mаthhеlррlаnеt.соm/stаtiс.рhр?р=tеоriyа-grаfоv-роnyаtiyа-i-орrеdеlеniyа (дата обращения: 13.01.2022).
6. Bоruvkа’s Аlgоrithm fоr Minimum Sраnning Trееs in Jаvа [Электронный ресурс] URL: httрs://www.bаеldung.соm/jаvа-bоruvkа-аlgоrithm (дата обращения: 20.01.2022).
7. Томас Х. Кормен, Чарльз И.Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы. Построение и анализ. М.: Вильямс, 2018. 1328 с.
8. Седжвик Роберт. Фундаментальные алгоритмы на С++. Алгоритмы на графах. СПБ.: ООО «ДиаСофтЮП». 2014. 496 с.
9. Стивен Скиена. Алгоритмы. Руководство по разработке. СПБ.: БХВ-Петербург, 2015. 720 с.
10. Рrim, R. С. Shоrtеst соnnесtiоn nеtwоrks Аnd sоmе gеnеrаlizаtiоns, Bеll Systеm Tесhniсаl Jоurnаl, 1957. 1389–1401 р.
11. Берцун В.Н. Математическое моделирование на графах. Часть2. Томск: Изд-во Том. ун-та, 2014. 86 с.
Пока есть несвязанные деревья, для каждого несвязанного дерева:
Находим край с меньшим весом.
Добавим это ребро, чтобы соединить другое дерево[7].
Результаты пошагового выполнения алгоритма представлены на рисунке 6.
Рисунок 6. Результаты пошагового выполнения алгоритма Борувки
ГЛАВА 2. ПОСТАНОВКА И АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧИ ПОИСКА МИНИМАЛЬНОГО ОСТОВНОГО ДЕРЕВА
2.1 Постановка задачи поиска минимального остовного дерева