Поиск минимального остова в графе

Теория графов – это область дискретной математики, особенностью которой является геометрический подход к изучению объектов. Теория графов находится сейчас в самом расцвете. Обычно её относят к топологии (потому что во многих случаях рассматриваются лишь топологические свойства графов), однако она пересекается со многими разделами теории множеств, комбинаторной математики, алгебры, геометрии, теории матриц, теории игр, математической логики и многих других математических дисциплин. Основной объект теории графов – граф и его обобщения. Граф – это множество точек (или вершин) и множество линий (или ребер), соединяющих между собой все или часть этих точек.

Существует несколько алгоритмов для нахождения минимального остовного дерева. Некоторые наиболее известные из них перечислены ниже:

- алгоритм Прима;

- алгоритм Краскала (или алгоритм Крускала);

- алгоритм Борувки.

Кратко рассмотрим сущности этих алгоритмов.

В алгоритме Крускала объединяются вершины графа в несколько связных компонентов, каждый из которых является деревом. На каждом шаге из всех ребер, соединяющих вершины из различных компонент связности, выбирается ребро с наименьшим весом. Необходимо проверить, что оно является безопасным. Безопасность ребра гарантируется ранее доказанной теоремой о безопасных ребрах. Так как ребро является самым легким из всех ребер, выходящих из данной компоненты, оно будет безопасным.

Алгоритм Прима состоит из нескольких этапов, в которых необходимо:

- упорядочить ребра графов по возрастанию весов;

- выбрать ребро с минимальным весом, не образующее цикл с раннее выбранными ребрами. Занести выбранное ребро в список ребер строящегося остова;

- проверить все ли вершины графа вошли в построенный остов, если нет, то выполнить алгоритм заново.

Далее будет представлено решение задачи №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.

В ходе решения данных задач по дисциплине «Математические методы» были закреплены следующие темы:

- математическое моделирование;

- решение задач линейного программирования симплекс-метод;

- решение транспортных задач;

- решение задач о назначениях;

- нахождение минимального остова в графах.

Все задачи решены верно, ответы задач решенных различными способами совпадают.

 

 

Заключение

В ходе стажировки был разработан программный продукт,  позволяющий автоматизировать систему сбора сведений программно-аппаратной конфигурации персональных компьютеров.

Программа имеет удобный интерфейс и не затруднит действия в эксплуатации даже неопытному пользователю. Также созданный программный продукт удовлетворяет всем функциональным требованиям и выполняет все поставленные задачи.

 Была разработана база данных, модули программы, интерфейс программы и документация, соответствующие руководства программиста и пользователя.

В дальнейшем проектировании возможно модифицирование базы данных: для повышения эффективности работы приложения, повышения функциональных возможностей самого приложения – совершенствование функций фильтраций, поиска и улучшение интерфейса программы.

В данной работе реализован на логическом уровне программный продукт, который полностью соответствует нормативным документам, определяющим порядок ведения документации.