Программная реализация построения кратчайшего остова неографа с использованием алгоритма Краскала и Прима (с помощью Delphi)

Введение

Графы широко используются как в самой математике, так и в ее приложениях. Они применяются при построении различных математических моделей: линий электропередачи, сетей автодорог, линий воздушных сообщений и пр.
Алгоритм Краскала — алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Открыт Джозефом Краскалом в 1956 году.
Алгоритм Прима — алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Алгоритм впервые был от-крыт в 1930 году чешским математиком Войцехом Ярником, позже переоткрыт Робертом Примом в 1957 году, и, независимо от них, Э. Дейкстрой в 1959 году.
Объектом исследования курсовой работы на тему «Программная реализация построения кратчайшего остова неорграфа с использованием алгоритма Краскала и Прима» являются алгоритмы решения графовых задач.
Цель работы - разработка алгоритмического и программного обеспечения для решения задач поиска кратчайшего пути между вершинами графа и минимального остовного дерева графа.
В результате исследований были рассмотрены алгоритмы построения кратчайшего остова неорграфа с использованием алгоритма Краскала и Прима.
Разработан программный продукт на языке программирования высокого уровня Delphi, реализующий алгоритм Краскала и Прима поиска кратчайшего пути между вершинами графа.
Курсовой проект на тему: «Программная реализация построения кратчайшего остова неорграфа с использованием алгоритма Краскала и Прима» основывается на разработанной программе на языке программирования - Delphi и включает программу PrimaKrascal.exe.
Задача курсового проекта – разработка и реализация на языке программирования высокого уровня алгоритма для решения следующих задач:
1) нахождения кратчайшего пути между 2-мя заданными вершинами графа;
2) нахождения минимального остовного дерева графа.
В первой главе курсовой работы рассмотрены общие аспекты теории графов, проблемы реализации, методы и средства решения поставленной задачи, обоснование...

Заключение

В представленной курсовой работе были рассмотрены основы теории графов - раздела конечной математики, особенностью которого является геометрический подход к изучению объектов, а также их применение на практике, в частности рассмотрен алгоритм Краскала и Прима, реализующий построение кратчайшего остова неорграфа. В качестве примера приведено решение практической задачи нахождения оптимального пути прокладки телефонного кабеля в каждый заданный город. Цель курсовой работы – решить задачу о жадном «алгоритме», посвященной нахождению минимальной суммы длин между его вершинами методом Прима - Краскала. Задача алгоритма — построение минимального остовного дерева.
Связанный граф, не содержащий циклов, называется деревом. Если граф является взвешенным, то актуальной задачей является задача построения минимального дерева, т.е. дерева с минимальным суммарным весом его ребер.
При построении минимального дерева важнейшим ограничением является максимально допустимая степень вершины, т.е. максимальное количество ребер, инцидентных одной вершине в графе. Вес ребра определяется по расстоянию между инцидентными данному ребру вершинами.
Алгоритм Прима является последовательным и наращивает дерево, состоящее из одной компоненты связности по матрице расстояний D=∣dij∣nxn (n-количество вершин графа). Элемент матрицы dij равен расстоянию между i и j вершинами графа.
Алгоритм Краскала может строить дерево одновременно для нескольких компонент связности, которые в процессе решения объединяются в одно связанное дерево.
Полный граф задается списком ребер. Перед работой список ребер сортируется по возрастанию длины. На каждом шаге просматривается список ребер, начиная с ребра, следующего за вошедшим в решение на предыдущем шаге, и к строящемуся поддереву присоединяют то ребро, которое не образует цикла с ребрами, ухе включенными в решение.
При выполнении курсовой работы по теме «Программная реализация построения кратчайшего остова неорграфа с использованием...