- •Введение
- •1 Исследовательская часть
- •1.1 Анализ предметной области
- •1.2 Постановка задачи
- •2 Технология разработки программного продукта
- •2.1 Анализ входных и выходных данных
- •2.2 Математическая (инфологическая) модель
- •2.3 Выбор и обоснование программных средств разработки
- •2.4 Выбор и обоснование аппаратных средств разработки
- •2.5 Десять важнейших возможностей ide Delphi. Стыковка окон. Броузер объектов.
- •3 Описание программных модулей
- •3.1 Структура и алгоритм работы программного продукта
- •3.2 Инструментарий разработки программного продукта
- •3.3 Интерфейс программного продукта
- •4.1 Построение математической модели задачи линейного программирования и ее решение
- •4.2 Решение задачи линейного программирования симплекс-методом
- •4.4 Решение задачи о назначениях
- •4.5 Поиск минимального остова в графе
- •Заключение
- •Список использованных источников
- •Приложение а
- •Приложение б
- •2 Технология разработки программного продукта 8
- •3 Описание программных модулей 22
- •Приложение в
4.5 Поиск минимального остова в графе
Теория графов – это область дискретной математики, особенностью которой является геометрический подход к изучению объектов. Теория графов находится сейчас в самом расцвете. Обычно её относят к топологии (потому что во многих случаях рассматриваются лишь топологические свойства графов), однако она пересекается со многими разделами теории множеств, комбинаторной математики, алгебры, геометрии, теории матриц, теории игр, математической логики и многих других математических дисциплин. Основной объект теории графов – граф и его обобщения. Граф – это множество точек (или вершин) и множество линий (или ребер), соединяющих между собой все или часть этих точек.
Существует несколько алгоритмов для нахождения минимального остовного дерева. Некоторые наиболее известные из них перечислены ниже:
- алгоритм Прима;
- алгоритм Краскала (или алгоритм Крускала);
- алгоритм Борувки.
Кратко рассмотрим сущности этих алгоритмов.
В алгоритме Крускала объединяются вершины графа в несколько связных компонентов, каждый из которых является деревом. На каждом шаге из всех ребер, соединяющих вершины из различных компонент связности, выбирается ребро с наименьшим весом. Необходимо проверить, что оно является безопасным. Безопасность ребра гарантируется ранее доказанной теоремой о безопасных ребрах. Так как ребро является самым легким из всех ребер, выходящих из данной компоненты, оно будет безопасным.
Алгоритм Прима состоит из нескольких этапов, в которых необходимо:
- упорядочить ребра графов по возрастанию весов;
- выбрать ребро с минимальным весом, не образующее цикл с раннее выбранными ребрами. Занести выбранное ребро в список ребер строящегося остова;
- проверить все ли вершины графа вошли в построенный остов, если нет, то выполнить алгоритм заново.
Далее будет представлено решение задачи №3 по нахождению минимального остова в графе с помощью алгоритма Прима.
Исходный граф представлен на рисунке 4.25.
Рисунок 4.25 – Исходный граф
Расстояния между вершинами графа приведены в таблице 22.
Таблица 22 – Расстояния между вершинами графа.
Вершины графа |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
1 |
|
5 |
7 |
5 |
|
|
3 |
|
|
2 |
|
|
|
6 |
4 |
|
|
|
|
3 |
|
|
|
|
3 |
4 |
|
6 |
|
4 |
|
|
|
|
|
2 |
4 |
|
|
5 |
|
|
|
|
|
|
8 |
|
7 |
6 |
|
|
|
|
|
|
|
|
6 |
7 |
|
|
|
|
|
|
|
7 |
|
8 |
|
|
|
|
|
|
|
|
5 |
9 |
|
|
|
|
|
|
|
|
|
Первое наименьшее значение в таблице равно 2, которое соответствует расстоянию между вершинами 4 и 6, необходимо провести соответствующее ребро в графе. Кратчайшее расстояние между пунктами на 1 этапе приведено в таблице 23.
Таблица 23 – Кратчайшее расстояние между пунктами на этапе 1
На рисунке 4.26 показан результат соединения выбранных пунктов на первом этапе.
Рисунок 4.26 – Результат на этапе 1
Далее необходимо повторять эту операцию до тех пор, пока в минимальный остов не войдут все вершины графа, с учетом того, что ребра не должны образовывать цикл.
Второе наименьшее значение в таблице равно 3, необходимо соединить пункты 1 и 7. Кратчайшее расстояние приведено в таблице 24.
Таблица 24 – Кратчайшее расстояние между пунктами на этапе 2
На рисунке 4.27 представлен результат решения задачи на втором этапе.
Рисунок 4.27 – Результат на этапе 2
Третье наименьшее значение в таблице равно 3, между пунктами 3 и 5.
Кратчайшее расстояние на 3 этапе приведено в таблице 25.
Таблица 25 – Кратчайшее расстояние между пунктами на этапе 3
На рисунке 4.28 представлен результат соединения выбранных пунктов на третьем этапе.
Рисунок 4.28 – Результат на этапе 3
Четвертое значение в таблице равно 4 (2 и 5). Выбранное на 4 этапе кратчайшее расстояние приведено в таблице 26.
Таблица 26 – Кратчайшее расстояние между пунктами на этапе 4
На рисунке 4.29 приведен результат решения задачи на 4 этапе.
Рисунок 4.29 – Результат на этапе 4
Пятое значение в таблице равно 4 (3 и 6). Выбранное на 4 этапе кратчайшее расстояние приведено в таблице 27.
Таблица 27 – Кратчайшее расстояние между пунктами на этапе 5
На рисунке 4.30 представлен результат решения задачи на этапе 5.
Рисунок 4.30 – Результат на этапе 5
Следующим значением, не образующим цикл, является число 4 (4 и 7). Выбранное на 6 этапе кратчайшее расстояние приведено в таблице 28.
Таблица 28 – Кратчайшее расстояние между пунктами на этапе 6
На рисунке 4.31 показан результат соединения выбранных пунктов на шестом этапе.
Рисунок 4.31 – Результат на этапе 6
Следующим минимальным значением также является число 5 (8 и 9). Элемент (4, 1) зачеркивается, так как при их соединении образуется цикл. Выбранное на 7 этапе кратчайшее расстояние приведено в таблице 29.
Таблица 29 – Кратчайшее расстояние между пунктами на этапе 7
На рисунке 4.32 представлен результат соединения пунктов на этапе 7.
Рисунок 4.32 – Результат на этапе 7
Следующее, удовлетворяющее условиям значение – 6 (9 и 6). Элементы (4, 2), (3, 1) следует зачеркнуть, так как при их соединении образуется цикл. Кратчайшее расстояние на 8 этапе приведено в таблице 30.
Таблица 30 – Кратчайшее расстояние между пунктами на этапе 8
На рисунке 4.33 показан результат соединения выбранных пунктов на восьмом этапе.
Рисунок 4.33 – Результат на этапе 8
Полученный минимальный остов представлен на рисунке 4.34.
Рисунок 4.34 – Минимальный остов в графе
Итак, все вершины исходного графа вошли в минимальный остов, ребра не образуют цикл. Следовательно, все условия можно считать выполненными. Чтобы найти минимальный остов, следует сложить все используемые раннее значения. Минимальный остов вычисляется по формуле (4.3):
Расстояние = (1,7)+(2,5)+(3,5)+(3,6)+(4,6)+ (4.3)
+(4,7)+(6,9)+ (9,8)
S=2+3+3+4+4+4+5+6= 31
Вес остова равен 31.
Далее будет представлено решение этой же задачи другим способом.
Расстояния между вершинами графа приведены в таблице 22.
Исходный граф представлен на рисунке 4.35.
Рисунок 4.35 – Исходный граф
Первым шагом вершину 1 необходимо отнести к остову.
Далее нужно оценить ребра от вершины 1 к вершинам 3, 2, 4, и 7, затем выбрать ребро с минимальным весом и вешину 7 отнести к минимальному остову.
Для вершин 1 и 7 нужно рассмотреть ребра, ведущие к вершинам 3, 2, 4, 5, 8. Ребро с минимальным весом идет к вершине 4, следовательно, нужно отнести ее к остову.
Из вершин 1, 7, 4 ребра идут к вершинам 3, 2, 5, 8, 6. Вершина 6 относится к остову, так как вес этого ребра минимальный.
Для вершин 1, 7, 4, 6 необходимо рассмотреть ребра, ведущие к вершинам 3, 2, 5, 8, 9. Вершину 3 нужно включит в остов.
Из вершин 1, 7, 4, 6, 3 ребра идут к вершинам 2, 5, 8, 9. Вершина 5 относится к остову, так как вес этого ребра минимальный.
Для вершин 1, 7, 4, 6, 3, 5 необходимо рассмотреть ребра, ведущие к вершинам 2, 8, 9. Вершину 2 нужно включит в остов.
Из вершин 1, 7, 4, 6, 3, 5, 2 ребра идут к вершинам 8, 9. Вершина 8 относится к остову, так как вес этого ребра минимальный.
Для вершин 1, 7, 4, 6, 3, 5, 2, 8 ребра идут к одной вершине – 9. Вершину 9 нужно включит в остов.
Минимальный остов представлен на рисунке 4.36.
Рисунок 4.36 – Минимальный остов в графе
Минимальный остов = (1,7)+(7,4)+(4,6)+(6,3)+(3,5)+(5,2)+(3,8)+(8,9) =
= 3+4+2+4+3+4+6+5=31.
Итак, результаты задачи по нахождению минимального остова различными способами сошлись. Минимальный остов равен 31.
В ходе решения данных задач по дисциплине «Математические методы» были закреплены следующие темы:
- математическое моделирование;
- решение задач линейного программирования симплекс-метод;
- решение транспортных задач;
- решение задач о назначениях;
- нахождение минимального остова в графах.
Все задачи решены верно, ответы задач решенных различными способами совпадают.