---

РЕФЕРАТ

Пояснительная записка к курсовой работе: 15с., 7 рис., 3 табл., 4 разделов, 1 приложения.

АЛГОРИТМ, АНАЛИЗ, БЛОК-СХЕМА, ВЕРШИНА, РЕБРО, ОСТОВ, МАТРИЦА СМЕЖНОСТИ, КАРКАС, ВЗВЕШЕННЫЙ ГРАФ.

Объект исследования: алгоритм нахождения минимального остовного дерева ­– алгоритм Прима.

Цель работы – разработка и реализация алгоритма Прима и Крускала для поиска минимального остовного дерева взвешенного неориентированного графа. А также анализ трудоемкости роста функции, тестирование правильности и анализ по времени алгоритма. Разработка псевдокода и блок-схемы для обоих алгоритмов.

В ходе работы была разработана программа, блок-схема и псевдокод для поиска минимального остовного дерева между всеми вершинами графа с помощью алгоритма Прима и алгоритма Крускала. Разработки проводились в среде (программе) MicrosoftVisualStudio.

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

Y

---

Введение

Объектом исследования курсовой работы стала реализация алгоритма Прима. 

• Целями работы являлись:

• ознакомление с алгоритмом Прима, его историей;

• реализация алгоритма, для построения минимального остовного дерева;

• анализ трудоёмкости алгоритма;

• тестирование алгоритма.

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

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

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

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

Этот алгоритм назван в честь американского математика Роберта Прима (Robert Prim), который открыл его в 1957 г.

---

1 Графы

1.1Основные характеристики графов

Граф G – это математический объект, состоящий из множества вершин X = dox₁,x₂,...,x_nend; и множества ребер A=doa₁, a₂,..., a_mend;. Таким образом, граф полностью определяется совокупностью множеств X, A и обозначается G(X, A).

Если ребрам графа приданы направления от одной вершины к другой, то такой граф называется ориентированным. Ребра ориентированного графа называются дугами. Соответствующие вершины ориентированного графа называют началом и концом. Если направления ребер не указываются, то граф называется неориентированным (или просто графом).Граф, имеющий как ориентированные, так и неориентированные ребра, называется смешанным.Неориентированное ребро графа эквивалентно двум противоположно направленным дугам, соединяющим те же самые вершины.

Множество ребер графа может быть пустым. Множество вершин графа не может быть пустым. Граф G (X, A)– полный, если для любой пары вершин x_i и x_j существует ребро (x_i, x_j).

1.2 Пути и маршруты

Маршрутом или цепью в неориентированном графе G называется такая последовательность (конечная или бесконечная) ребер a₁, a₂,...,a_n,…, что каждые соседние два ребра a_i и a_i+1имеют общую инцидентную вершину. Одно и то же ребро может встречаться в маршруте несколько раз. В конечном маршруте (a₁,a₂,...,a_n) имеется первое ребро a₁и последнее ребро a_n. Вершина x₁, инцидентная ребру a₁, но не инцидентная ребру a₂, называется началом маршрута, а вершина x_n, инцидентная ребру a_n, но не инцидентная ребруa_n-1, называется концом маршрута.

Длиной (или мощностью) маршрута называется число ребер, входящих в маршрут, причем каждое ребро считается столько раз, сколько оно входит в данный маршрут.

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

1.3 Каркас неориентированного графа

Оптимальным каркасом взвешенного графа называется каркас, минимизирующий некоторую функцию от весов входящих в него ребер. Чаще всего в качестве такой функции выступает сумма весов ребер, реже — произведение. Оптимальный каркас еще называют кратчайшей связывающей сетью для данного графа. Задача о построении кратчайшей связывающей сети встречается в различных приложениях достаточно часто. 

1.4 Задача об оптимальном каркасе

Задача об оптимальном каркасе (стягивающем дереве) состоит в следующем. Дан обыкновенный граф G=(V,E) и весовая функция на множестве ребер u: V R. Вес множества X  E определяется как сумма весов составляющих его ребер. Требуется в графе G найти каркас минимального веса. В этом разделе будем предполагать, что граф G связен, так что решением задачи всегда будет дерево. Для решения задачи об оптимальном каркасе известно несколько алгоритмов. Рассмотрим два из них: Алгоритм Прима и Алгоритм Крускала, алгоритм впервые описан Джозефом Крускалом в 1956 году.

---

---

Смотрите также файлы

• Методы оптимизации Курсовой проект О распределении.docx

• Методы оптимизации Зыкина.docx

• РЕФЕРАТ_ФИЗКУЛЬТУРА.docx

• физра реферат.doc

• конкуренты.docx