і зображений на малюнку 12. В
Малюнок 12. Отриманий мінімальний остов
Після перевірки обчислень вручну і програмної моделі результат однаковий, це означає, що програмна модель працює і функціонує вірно.
Задача № 2. Дан зважений, зв'язний, неорієнтовані граф, що складається з дев'яти вершин. Необхідно знайти остов мінімальної ваги за допомогою алгоритму Краскала. Вихідний граф на малюнку 13. <В
Малюнок 13. Вихідний граф
Вибираємо вершину початку побудови кістяка мінімальної ваги, наприклад, першу вершину.
Крок 1. Знайдено ребро мінімальної ваги: ​​AC = 1. Отриманий остов на малюнок 14. <В
Малюнок 13. Отриманий остов на кроці 1
Крок 2. Знайдено ребро мінімального ваги: ​​CF = 3, AB = 4, AC = 4. Отриманий остов на малюнок 15. <В
Малюнок 14. Отриманий остов на кроці 2
Крок 3. Знайдено ребро мінімального ваги: ​​FD = 4, EK = 3, AE = 4. Отриманий остов на малюнок 15. <В
Малюнок 15. Отриманий остов на кроці 3
Крок 4. Знайдено ребро мінімальної ваги: ​​KH = 5, KG = 4. Розглянуто всі вершини і інцідентние ребра цих вершин, що залишилися ребра утворюють цикл в отриманому мінімальному остові. А це не задовольняє умовам поставленого завдання. p> На четвертому кроці отримано остаточний остов мінімальної ваги, який представлений на малюнку 16.
В
Малюнок 16. Остов мінімальної ваги
Вирішимо дану задачу за допомогою програмної моделі. Щоб вирішити дану задачу необхідно побудувати матрицю ваг.
Таблиця 1. Матриця ваг
В
A
B
C
D
E
F
G
H
K
A
-
4
1
9
4
-
-
-
-
B
4
-
-
-
-
-
-
5
-
