Лабораторная работа по "Высшей математике"
Автор: Анжела Кушнир • Август 27, 2022 • Лабораторная работа • 416 Слов (2 Страниц) • 165 Просмотры
ст. Дегтярев Д. А., г. ИКН-311, Вариант 4
Лабораторная работа № 3.
Задание 1. Для графа G, заданного матрицей весов, построить минимальный по весу остов и найти его вес, используя алгоритм Крускала.
Заданная матрица весов:
[pic 1]
Реализация алгоритма Крускала:
[pic 2]
Последовательность добавления ребер по алгоритму Крускала:
(1, 2; 2, 7; 3,4; 1, 3; 1,5; 4, 6).
Минимальный вес остового дерева 30.
Задание 2. Для графа G, заданного матрицей весов, построить минимальный по весу остов и найти его вес, используя алгоритм Прима.
Заданная матрица весов:
[pic 3]
Реализация алгоритма Прима:
[pic 4]
Последовательность добавления ребер по алгоритму Прима:
(1, 2; 2, 7; 1, 3; 3,4; 1,5; 4, 6).
Минимальный вес остового дерева 30.
Задание 3. Вычислить число остовных деревьев в графе.
Заданная матрица весов:
[pic 5]
Матрица Кирхгофа:
С = [pic 6]
При подсчете получим число остовных деревьев в графе 792.
Тест
Укажите центроид дерева.
1.
[pic 7]
А – 14; Б – 9; В – 19; Г – 10.
2.
[pic 8]
А – 12; Б – 2; В – 13; Г – 7.
3.
[pic 9]
А – 22; Б – 24; В – 17; Г – 23.
4.
[pic 10]
А – 23; Б – 24; В – 22; Г – 18.
5.
[pic 11]
А – 17; Б – 13; В – 12; Г –14.
Укажите наименьший вес вершин дерева.
1.
[pic 12]
А – 11; Б – 12; В – 23; Г – 17.
2.
[pic 13]
А – 12; Б – 21; В – 15; Г – 20.
3.
[pic 14]
А – 11; Б – 12; В – 10; Г – 8.
4.
[pic 15]
А – 21; Б – 12; В – 22; Г –14.
5.
[pic 16]
А – 12; Б – 11; В – 9; Г – 20.
Вопросы
1. Что такое остов?
2. Какое дерево называют минимальным остовным?
3. Какой граф называют деревом?
4. Какой граф называют ациклическим?
5. Что такое концевой узел?
...