39;язані з використанням (Правильним чи неправильним) цієї програми. p> 4) Ви не можете емулювати, клонувати, здавати в оренду, давати напрокат, продавати, змінювати, декомпілювати, аналізувати код "Алгоритм Краскала". Будь-яке подібне неавторизоване використання призводить до негайного і автоматичного припинення дії цієї ліцензії і може спричинити за собою кримінальне та/або цивільне переслідування.
5) Всі права, явно не представлені тут, належать автору програми.
6) Запуск і використання "Алгоритм Краскала" свідчить про згоду з умовами даної ліцензії.
7) Якщо ви не згодні з умовами цієї ліцензії, то повинні видалити файли "Алгоритм Краскала "з своїх пристроїв зберігання інформації і відмовитися від їх використання.
Дякуємо за використання "Алгоритм Краскала"!
Автор програми: Терешков Юрій Ігорович. <В
5 Контрольна задача моделювання
У даному розділі вирішено дві контрольні завдання:
-вручну;
-за допомогою програмної моделі. p> Після рішення контрольних завдань проведено порівняння отриманих мінімальних кістяків.
Задача № 1. Дан зважений зв'язний неорієнтовані граф, що складається з п'яти вершин. Необхідно знайти остов мінімальної ваги за допомогою алгоритму Краскала. <В
Малюнок 6. Вихідний граф. p> Вибираємо вершину початку побудови кістяка мінімальної ваги, наприклад, першу вершину. p> Крок 1. Знайдено ребро мінімальної ваги: ​​1-2 = 6. Отриманий остов на малюнок 7. <В
Малюнок 7. Отриманий Ост на кроці 1
Крок 2. Знайдено ребро мінімальної ваги: ​​2-3 = 7. Отриманий остов на малюнок 8. br/>В
Малюнок 8.Полученний остов на кроці 2
Крок 3. Знайдено ребро мінімальної ваги: ​​3-4 = 9. Отриманий остов на малюнок 9. <В
Малюнок 9.Полученний остов на кроці 3
Крок 4. Знайдено ребро мінімальної ваги: ​​3-5 = 11. p> Розглянуто всі вершини і інцідентние ребра цих вершин, що залишилися утворюють цикл в отриманому мінімальному кістяку. А це не задовольняє умовам поставленого завдання. p> На четвертому кроці отримали остаточний остов мінімальної ваги, який представлений на малюнку 10. br/>
В
Малюнок 10. Остов мінімальної ваги
При зміні вершини початку побудови конфігурація остова мінімального ваги не змінитися, а змінитися лише послідовність побудови ребер остова.
Наприклад, якщо в якості початкової вершини вибрати четверту вершину, то послідовність етапів побудови кістяка мінімальної ваги буде виглядати наступним чином:
Крок 1. 4-3 = 9;
Крок 2. 3-2 = 7;
Крок 3. 2-1 = 6;
Крок 4. 3-5 = 11;
При цьому конфігурація остова залишиться колишньою. Вирішимо дану задачу за допомогою програмної моделі. Щоб вирішити дану задачу необхідно побудувати матрицю ваг, матриця представлена ​​на малюнку 11.
В
Малюнок 11. Матриця ваг
Отриманий мінімальний остов за допомогою програмної модел...
