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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Работа № 92193


Наименование:


Диплом Основные понятия теории графов.Алгоритмы нахождения кратчайших путей.Аналитическая реализация алгоритма Дейкстры

Информация:

Тип работы: Диплом. Добавлен: 13.11.2015. Сдан: 2015. Страниц: 79. Уникальность по antiplagiat.ru: < 30%

Описание (план):


Содержание

Введение
1.Теоритическая часть
1.1Основные понятия теории графов
1.2 Задачи теории графов
1.3 Алгоритмы нахождения кратчайших путей
2 Практическая часть
2.1Аналитическая реализация алгоритма Дейкстры
2.2 Программная реализация алгоритма Дейкстры
2.3. Анализ результатов решений
3 Экономическая часть
3.1 Обоснование для разработки
3.2 Расчет затрат на разработку программы
3.3Расчет цены разработанной программы
3.4 Анализ рыночный цены на аналогичный продукт
Заключение
Список использованных источников
Приложения
Приложения А функциональная схема программного продукта
Приложения Б Sadt- диаграмма
Приложения В листинг программы
Приложения Г руководство пользователя
Приложения Д руководство программиста
Приложения Е руководство системного программиста


2015
ВВЕДЕНИЕ

В коммерческой деятельности большинство возникающих задач удобно представлять для восприятия и анализа в виде сетей, которые позволяют ответить на два главных вопроса: до какого места необходимо дойти (цель) и какой путь следует избрать (как). Коммерческую деятельность можно рассматривать как совокупность задач, предназначенных для передвижения, складирования и распределения товаров, денег, документов, информации о поставках и покупателях воды, нефти, газа, электроэнергии, теле- и радиосистем. Наглядность и логическая обоснованность методов сетевого анализа позволяет выбрать довольно естественный подход к решению задач коммерческой деятельности. Сетевые модели для людей, не занимающихся научной работой, являются более понятными, чем другие модели, поскольку для них все же лучше один раз увидеть, чем сто раз услышать. В значительной степени методы сетевого анализа основаны на теории графов - области математики, началом развития которой явилась задача о кенигсбергских мостах, сформулированная швейцарским ученым Л. Эйлером в 1736 г. Через реку Прегель, на которой стоял город Кенигсберг, построено семь мостов, которые связывали с берегами и друг с другом два острова. Задача заключалась в том, чтобы пройти по всем мостам только один раз и вернуться обратно к началу маршрута. Эйлер доказал неразрешимость этой задачи.
Позже Д.К. Максвелл и Г.Р. Кирхгоф на основе исследования электрических цепей сформулировали некоторые принципы сетевого анализа. Были разработаны методы расчета наибольшей пропускной способности телефонных линий. В 40-х годах в результате развития теории исследования операций был разработан ряд математических методов, необходимых для анализа больших систем. В 50-60-х годах проводились работы по построению новых сетевых моделей и разработке алгоритмов их решения на основе элементов теории графов.
Цель работы: разработать программу, позволяющую рассчитывать наименее затратный маршрут для перевозки груза из начального пункта в конечный.
Достижение поставленной цели предполагает выполнение следующих задач:
· изучить предметную область;
· проанализировать методы решения поставленной задачи;
· осуществить проектирование программного продукта;
· выбрать средства и технологии разработки;
· разработать программный продукт;
· провести комплексное тестирование программного продукта;
· разработать план внедрения программного продукта.


1 ТЕОРИТИЧЕСКАЯ ЧАСТЬ

1.1Основные понятия теории графов

Первой работой теории графов как математической дисциплины считают статью Эйлера (1736 г.), в которой рассматривалась задача о Кёнингсбергских мостах. Эйлер показал, что нельзя обойти семь городских мостов и вернуться в исходную точку, пройдя по каждому мосту ровно один раз. Следующий импульс теория графов получила спустя почти 100 лет с развитием исследований по электрическим сетям, кристаллографии, органической химии и другим наукам.
С графами, сами того не замечая, мы сталкиваемся постоянно. Например, графом является схема линий метрополитена. Точками на ней представлены станции, а линиями - пути движения поездов. Исследуя свою родословную и возводя ее к далекому предку, мы строим так называемое генеалогическое древо. И это древо - граф.
Графы служат удобным средством описания связей между объектами. Ранее мы уже использовали графы как способ наглядного представления конечных бинарных отношений. Но граф используют отнюдь не только как иллюстрацию. Например, рассматривая граф, изображающий сеть дорог между населенными пунктами, можно определить маршрут проезда от пункта А до пункта Б. Если таких маршрутов окажется несколько, хотелось бы выбрать в определенном смысле оптимальный, например самый короткий или самый безопасный. Для решения задачи выбора требуется проводить определенные вычисления над графами. При решении подобных задач удобно использовать алгебраическую технику, да и само понятие графа необходимо формализовать.
Методы теории графов широко применяются в дискретной математике. Без них невозможно обойтись при анализе и синтезе различных дискретных преобразователей: функциональных блоков компьютеров, комплексов программ и т.д.
В настоящее время теория графов охватывает большой материал и активно развивается. При ее изложении ограничимся только частью результатов и основной акцент сделаем на описании и обосновании некоторых широко распространенных алгоритмов анализа графов, которые применяются в теории формальных языков.
Графы, как уже отмечалось в примерах, есть способ "визуализации" связей между определенными объектами. Связи эти могут быть "направленными", как, например, в генеалогическом древе, или "ненаправленными" (сеть дорог с двусторонним движением). В соответствии с этим в теории графов выделяют два основных типа графов: ориентированные (или направленные) и неориентированные.
Построение математического определения графа осуществляется путем формализации и "объектов", и "связей" как элементов некоторых (как правило, конечных) множеств.
Так в компьютерной сети точки - это отдельные серверы, а линии - различные виды электрических сигналов. В метрополитене первое - станции, второе - туннели, проложенные между ними. В теории графов точки именуется вершинами (узлами), а линии -ребрами (дугами). Таким образом, граф - это совокупность вершин, соединённых ребрами.
Математика оперирует не содержанием вещей, а их структурой, абстрагируя ее из всего того, что дано как целое. Пользуясь именно этим приемом, мы можем заключать о каких-либо объектах как о графах. А поскольку теория графов это часть математики, то для нее нет абсолютно никакого значения, что в принципе представляет собой объект; важно лишь то, является ли он графом, т. е. обладает ли обязательными для графов свойствами. Поэтому, прежде чем привести примеры, мы выделяем в рассматриваемом объекте лишь то, что как нам кажется, позволит показать аналогию, отыскиваем общее.
Вернемся к компьютерной сети. Она обладает определенной топологией, и может быть условно изображена в виде некоторого числа компьютеров и путей их соединяющих. На рисунке 1в качестве примера показана полносвязная топология.

< wp-content/uploads/example-of-a-graph.jpg>
Рисунок 1 - Полносвязная топология(неориентированный граф).

Это по сути граф. Пять компьютеров являются вершинами, а соединения (пути передачи сигналов) между ними - ребрами. Заменив компьютеры вершинами, мы получим математический объект - граф, который имеет 10 ребер и 5 вершин. Пронумеровать вершины можно произвольным образом, а не обязательно так, как это сделано на рисунке. Стоит отметить, что в данном примере не используется ни одной петли, то есть такого ребра, которое выходит из вершины и сразу же входит в нее, но петли могут встречаться в задачах.
Вот некоторые важные обозначения, используемые в теории графов:
G=(V, E), здесь G - граф, V - его вершины, а E - ребра;
|V| - порядок (число вершин);
|E| - размер графа (число рёбер).
В нашем случае (рис. 1) |V|=5, |E|=10;
Когда из любой вершины доступна любая другая вершина, то такой граф называется неориентированным связным графом (рисунок 1). Если же граф связный, но это условие не выполняется, тогда такой граф называется ориентированным или орграфом (рисунок 2).
В ориентированных и неориентированных графах имеется понятие степени вершины. Степень вершины - это количество ребер, соединяющих ее с другими вершинами. Сумма всех степеней графа равна удвоенному количеству всех его ребер. Для рисунка 2 сумма всех степеней равна 20.

< wp-content/uploads/orgraph.jpg>
Рисунок 2 - Ориентированный граф

В орграфе, в отличие от неориентированного графа, имеется возможность двигаться из вершины h в вершину s без промежуточных вершин, лишь тогда когда ребро выходит из h и входит в s, но не наоборот.
Ориентированные графы имеют следующую форму записи:
G=(V, A), где V - вершины, A - направленные ребра.
Третий тип графов - смешанные графы (рисунок 3). Они имеют как направленные ребра, так и ненаправленные. Формально смешанный граф записывается так: G=(V, E, A), где каждая из букв в скобках обозначает тоже, что ей приписывалось ранее.

< wp-content/uploads/mix_graph.jpg>
Рисунок 3 - Смешанный граф

В графе на рисунке 3 одни дуги направленные [(e, a), (e, c), (a, b), (c, a), (d, b)], другие - ненаправленные [(e, d), (e, b), (d, c)…].
Два или более графов на первый взгляд могут показаться разными по своей структуре, что возникает вследствие различного их изображения. Но это не всегда так. Возьмем два графа (рисунке 4).
< wp-content/uploads/izomorph_graph.jpg>
Рисунок 4 - Изоморфные графы

Они эквивалентны друг другу, ведь не изменяя структуру одного графа можно построить другой. Такие графы называются изоморфными, т. е. обладающими тем свойством, что какая-либо вершина с определенным числом ребер в одном графе имеет тождественную вершину в другом. На рисунке 4 изображены два изоморфных графа.
Когда каждому ребру графа поставлено в соответствие некоторое значение, называемое весом ребра, тогда такой граф взвешенный. В разных задачах в качестве веса могут выступать различные виды измерений, например длины, цены маршруты и т. п. В графическом представлении графа весовые значения указываются, как правило, рядом с ребрами.
В любом из рассмотренных нами графов имеется возможность выделить путь и, причем не один. Путь - это последовательность вершин, каждая из которых соединена с последующей посредством ребра. Если первая и последняя вершины совпадают, то такой путь называется циклом. Длина пути определяется количеством составляющих его ребер. Например, на рисунке 4.а путем служит последовательность [(e), (a), (b), (c)]. Этот путь является подграфом, так как к нему применимо определение последнего, а именно: граф G’=(V’, E’) является подграфом графа G=(V, E), только тогда когда V’ и E’ принадлежат V, E.
Способы представления графов:
Матрица смежности
Матрица смежности графа - это квадратная матрица, в которой каждый элемент принимает одно из двух значений: 0 или 1. Прежде чем отобразить граф через матрицу смежности, рассмотрим простой пример такой матрицы (рисунок 5).

< wp-content/uploads/binary_matrix.jpg>
Рисунок 5 - Матрица смежности

Это двоичная квадратная матрица, т. к. число строк в ней равно числу столбцов, и любой из ее элементов имеет значение либо 1, либо 0. Первая строка и первый столбец (не входят в состав матрицы, а показаны здесь для легкости ее восприятия) содержат номера, на пересечении которых находится каждый из элементов, и они определяют индексное значение последних. Имея в наличии лишь матрицу такого типа, несложно построить соответствующий ей граф.

< wp-content/uploads/matrix_smeghnost.jpg>
Рисунок 6 Матрица смежности и ее граф

Слева на рисунке 6 изображена все та же матрица смежности, имеющая размерность 4?4. Числа, выделенные синим, можно рассматривать как вершины смешанного графа, расположенного справа - того, представлением которого является матрица.
Для графического отображения графа необходимо уметь вычислять по матрице смежности количество его вершин, а также обладать знанием следующего правила. Когда из одной вершины в другую проход свободен (имеется ребро), тогда в ячейку заноситься 1, иначе - 0. Немного формализовав только что сказанное, получим: если из i в j существует ребро, то A[i][j]:=1, в противном случае A[i][j]:=0. Как видно, все элементы на главной диагонали равны нулю, это следствие отсутствия у графа петель. Но ни что не мешает, чтобы некоторые или все элементы главной диагонали были единицами.
В программе матрица смежности задается при помощи обычного двумерного массива, имеющего размерность n?n, где n - число вершин графа.
Матрица инцидентности
Говорить о том, что ребро g и каждая из вершин u и y инцидентна g, стоит лишь в том случае, если g соединяет u и y. Уяснив это, перейдем к рассмотрению данного метода. Матрица инцидентности строиться по похожему, но не по тому же принципу, что и матрица смежности. Так если последняя имеет размер n?n, где n - число вершин, то матрица инцидентности - n?m, здесь n - число вершин графа, m - число ребер. То есть теперь чтобы задать значение какой-либо ячейки, нужно сопоставить не вершину с вершиной, а вершину с ребром.
В каждой ячейки матрицы инцидентности неориентированного графа стоит 0 или 1, а в случае ориентированного графа, вносятся 1, 0 или -1. То же самое, но наиболее структурировано:
Неориентированный граф
1 - вершина инцидентна ребру
0 - вершина не инцидентна ребру
Ориентированный граф
1 - вершина инцидентна ребру, и является его началом
0 - вершина не инцидентна ребру
-1 - вершина инцидентна ребру, и является его концом
Построим матрицу инцидентности сначала для неориентированного графа (рисунок 7), а затем для орграфа.

< wp-content/uploads/incidence_matrix.jpg>
Рисунок 7 - Матрица инцидентности для неориентированного графа

Ребра обозначены буквами от a до e, вершины - цифрами. Все ребра графа не направлены, поэтому матрица инцидентности заполнена положительными значениями.

< wp-content/uploads/incidence_matrix2.jpg>
Рисунок 8 - Матрица инцидентности для ориентированного графа

Для орграфа графа (рисунок 8) матрица имеет немного другой вид. В каждую из ее ячеек внесено одно из трех значений. Обратите внимание, что нули в двух этих матрицах (рисунок 7 и 8) занимают одинаковые позиции, ведь в обоих случаях структура графа одна. Но некоторые положительные единицы сменились на отрицательные, например, в неориентированном графе ячейка (1, b) содержит 1, а в орграфе -1. Действительно, это уместно, так как в первом случае ребро b не направленное, а во втором - направленное, и, причем вершиной входа для него является вершина «1».
Каждый столбец отвечает за какое-либо одно ребро, поэтому граф, описанный при помощи матрицы инцидентности, всегда будет иметь следующий признак: любой из столбцов матрицы инцидентности содержит две единицы, либо 1 и -1 когда это ориентированное ребро, все остальное в нем - нули.
В программе матрица инцидентности задается, также как и матрица смежности, а именно при помощи двумерного массива. Его элементы могут быть инициализированы при объявлении, либо по мере выполнения программы.
Структурная матрица.
Именно эта матрица имеет особое значение в теории сетей связи.
Именно эта матрица имеет особое значение в теории сетей связи. Структурная матрица - это символьная матрица порядка п. Она составляется следующим образом: на главной диагонали стоит 1, то есть. aii = 1, остальные элементы - это символьные обозначения ребер (если вершины i и j не соединены ребром, то aii = 0). При этом, если при ij - это отрицание а, которое обычно отмечается чертой сверху. Если связи вершины i с вершиной j нет, то соответствующий элемент равен 0, структурная матрица может составляться и для орграфа и для мультиграфа без петель (здесь если два ребра а и b соединяют две вершины, то соответствующий элемент при i j этот элемент равен.
Отметим, что в ........



Перейти к полному тексту работы


Скачать работу с онлайн повышением уникальности до 90% по antiplagiat.ru, etxt.ru или advego.ru


Смотреть похожие работы

* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.