Реферат: Графовые модели. Остов минимального веса

Рисунок 5. Помощь для пользователя.

Последняя кнопка, которая размещена на форме «Выход», при нажатии на кнопку приложение будет закрыто.

4.4 Лицензионное соглашение

Алгоритм Краскала (версия 1.0)

1) Всеми авторскими правами на "Алгоритм Краскала" эксклюзивно владеет автор программы – Терешков Юрий Игоревич.

2) " Алгоритм Краскала " могут распространяться только в том виде, в котором они поставляются автором.

3) " Алгоритм Краскала " распространяются по принципу "как есть". При этом не предусматривается никаких гарантий, явных или подразумеваемых. Вы используете его на свой собственный риск. Автор не отвечает за потери данных, повреждения, потери прибыли или любые другие виды потерь, связанные с использованием (правильным или неправильным) этой программы.

4) Вы не можете эмулировать, клонировать, сдавать в аренду, давать напрокат, продавать, изменять, декомпилировать, дизассемблировать " Алгоритм Краскала". Любое подобное неавторизованное использование приводит к немедленному и автоматическому прекращению действия этой лицензии и может повлечь за собой уголовное и/или гражданское преследование.

5) Все права, явно не представленные здесь, принадлежат автору программы.

6) Запуск и использование " Алгоритм Краскала " свидетельствует о согласии с условиями данной лицензии.

7) Если вы не согласны с условиями данной лицензии, то должны удалить файлы " Алгоритм Краскала " со своих устройств хранения информации и отказаться от их использования.

Спасибо за использование " Алгоритм Краскала "!

Автор программы: Терешков Юрий Игоревич.

5 Контрольная задача моделирования

В данном разделе решено две контрольные задачи:

-вручную;

-с помощью программной модели.

После решения контрольных задач проведено сравнение полученных минимальных остовов.

Задача №1. Дан взвешенный связный неориентированный граф, состоящий из пяти вершин. Необходимо найти остов минимального веса с помощью алгоритма Краскала.

Рисунок 6. Исходный граф.

Выбираем вершину начала построения остова минимального веса, например, первую вершину.

Шаг 1. Найдено ребро минимального веса: 1-2=6. Полученный остов на рисунок 7.

Рисунок 7. Полученный оостов на шаге 1

Шаг 2. Найдено ребро минимального веса: 2-3=7. Полученный остов на рисунок 8.

Рисунок 8.Полученный остов на шаге 2

Шаг 3. Найдено ребро минимального веса: 3-4=9. Полученный остов на рисунок 9.