Студопедия

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника



Математический факультет




Читайте также:
  1. агрономического факультета
  2. Введение в математический язык
  3. для студентов 6 курса лечебного факультета
  4. Для студентов стоматологического факультета.
  5. Для студентов факультетов механизации с/х, екологомелиоративного
  6. Для студентов факультетов – ветеринарная медицина и биотехнологического
  7. Кафедра факультетской терапевтической стоматологии
  8. Любая научная дисциплина станет действительно научной, когда она будет опираться на определенный математический аппарат, который делает любую науку точной.
  9. Математический аппарат факторного анализа
  10. Математический вид

 

 

«Алгоритмы на графах»

 

Курсовая работа

Студента 2 курса 2 группы

А. В. Анцупова

 

Научный руководитель:

Доцент кафедры теоретической информатики и

дискретной математики

А. А. Привалов

 

Москва-2015

Оглавление

Введение……………………………………………………….…………………3

1. Графы………………………………………………………………………….5

1.2. Понятие графов и их виды…………………………………………………5

1.3. Способы описания графов…………………………………………………8

1.3.1. Матричное представление графов………………………………………8

1.3.2. Теоретико-множественное представление графов……………………10

1.3.3. Задание графов соответствием……………………………………….…11

2.Алгоритмы на графах………………………………………………………..12

2.1. Алгоритм Беллмана-Форда……………………………………………….12

2.2. Алгоритм Флойда-Уоршелла……………………………………………..18

Заключение……………………………………………………………………...22

Список использованной литературы……………………………………….…23

 

 

Введение


Тема данной курсовой работы «Алгоритмы на графах» является очень актуальной в настоящее время. Благодаря своему широкому применению данная тема постоянно развивается и совершенствуется. Данная тема очень широко применяется даже в обыденной жизни человека: поиск кратчайшего пути от одной точки до другой, в работе GPS при анализе загруженности дорог и выборе оптимального маршрута движения, коммутации информационных пакетов в сетях (например, Интернет) и прочее. Можно найти множество способов применить данную тему в жизни.
Иногда применение графов для отображения какой-либо модели является очень полезным и наглядным. Графы применяются во многих областях науки. Например, в химии – молекулярная структура, в электронике – сети, дорожные карты и многое другое. Поэтому очень важно уметь применять поиск кратчайшего пути в графе.
В настоящее время существует два наиболее популярных алгоритма поиска кратчайшего пути:
1. Алгоритмы Беллмана – Форда;
2. Алгоритм Флойда – Уоршелла.
У каждого из представленных алгоритмов существуют свои достоинства и недостатки, которые необходимо отметить в данной курсовой работе и выбрать наилучший алгоритм. Выбор будет осуществляться по сложности программного кода, скорости работы, затратам памяти.
Каждый из представленных алгоритмов используется в компьютерной технике, поэтому важно отметить в данной курсовой работе и способы представления математической модели «граф», которые получили наибольшее распространение, выделить их достоинства и недостатки.
При выполнении данной курсовой работы ставятся следующие задачи:
1. Рассмотреть понятие графа и их существующие виды.
2. Рассмотреть существующие способы представления графов в вычислительной технике.
3. Дать определение кратчайшего пути.
4. Изучить существующие алгоритмы поиска кратчайшего пути в графах.
В первой главе будет дано определение графа, выделены их основные виды, а также подробно рассмотрены способы представления графов в вычислительной технике.
Во второй главе следует дать определение кратчайшего пути и вынести на рассмотрение основные алгоритмы поиска кратчайших путей, их особенности, достоинства и недостатки.
Так что же такое «граф»? Перейдем непосредственно к рассмотрению данного вопроса.



 

1. Графы

1.2. Понятие графов и их виды

Граф задается множеством точек или вершин х1, х2, ..., хn и множеством линий или ребер a1, a2, ... , am, соединяющих между собой все или часть точек. Формальное определение графа может быть дано следующим образом [1].



Графом называется двойка вида:

 

G = (X, A),

 

где X = {xi}, i = 1, 2, ..., n – множество вершин графа, A = {ai}, i = 1, 2,., m – множество ребер графа.

Графы могут быть ориентированными, неориентированными и смешанными (рис.1). Если ребра у множества A ориентированы, что обычно показывается стрелкой, то они называются дугами, и граф с такими ребрами называется ориентированным графом или орграфом (рис.1,а).

Рис.1. Примеры ориентированных и неориентированных графов.

 

 

Если ребра не имеют ориентации, то граф называется неориентированным (рис.1,б). Граф, в котором присутствуют и ребра, и дуги называется смешанным (рис.1,в). В случае, когда G = (X, A) является орграфом, и мы хотим пренебречь направленностью дуг из множества A, то неориентированный граф, соответствующий G, будет обозначаться и называться неориентированным дубликатом или неориентированным двойником (рис.1,г).

Дуга ai может быть представлена упорядоченной парой вершин (хn, хk), состоящей из начальной хn и конечной хk вершин. Например, для графа G1 (рис.1,а) дуга a1 задается парой вершин (x1, x2), а дуга а3 парой (x2, x3). Если хn, хk – концевые вершины дуги ai, то говорят, что вершины хn и хk инцидентны дуге ai или дуга ai инцидентна вершинам хn и хk.

Дуга, у которой начальная и конечная вершины совпадают, называется петлей. В графе G3 (рис.1,в) дуга a7 является петлей.

Каждая вершина орграфа хi может характеризоваться полустепенью исхода d0i) и полустепенью захода dti).

Полустепенью исхода вершины хi — d0i) называется количество дуг, исходящих из этой вершины. Например, для орграфа G1 (рис.1,а) характеристики полустепеней исхода следующие: d01)=1, d02)=2, d03)=2, d04)=1.



Полустепенью захода вершины хi — dti) называется количество дуг, входящих в эту вершину. Например, для орграфа G1: dt1)=2, dt2)=1, dt3)=2, dt4 )=1.

Очевидно, что сумма полустепеней исхода всех вершин графа, а также сумма полустепеней захода всех вершин графа равна общему числу дуг графа, т. е.

 

 

где n – число вершин графа, m – число дуг.

Каждая вершина неориентированного графа хi может характеризоваться степенью вершины d(хi).

Степенью вершины хi – d(хi) называется количество ребер, инцидентных этой вершине. Например, для орграфа G1 (рис.1,б) характеристики степеней следующие: d(х1)=2, d(х2)=3, d(х3)=2, d(х4 )=2.

 

1.3. Способы описания графов

1.3.1. Матричное представление графов

Для обработки на ЭВМ графы удобно представлять в виде матриц смежности и инциденций.

Матрица смежности – это квадратная матрица размерностью n x n, (где n – число вершин графа), однозначно представляющая его структуру.

A = {aij}, i, j = 1, 2, ..., n, а каждый элемент матрицы определяется следующим образом:

 

aij = 1, если ∃ дуга (хi, хj),

aij = 0, если нет дуги (хi, хj).

 

Матрица инциденций представляет собой прямоугольную матрицу размером n x m, где n – количество вершин графа, а m – количество дуг графа. Обозначается матрица инциденций B = = {bij}, i = 1, 2, ..., n, j = 1, 2, ..., m.

Каждый элемент матрицы определяется следующим образом:

bij = 1, если хi является начальной вершиной дуги aj,

bij = –1, если хi является конечной вершиной дуги aj,

bij = 0, если хi не является концевой вершиной дуги aj или если aj является петлей.

 

Рис.2. Орграф и его матричное представление: а – орграф; б – матрица смежности; в – матрица инциденций

 

На рис.2, а,б приведен граф и его матрица смежности, по которой можно найти характеристики вершин. Так сумма элементов i-ой строки матрицы дает полустепень исхода вершины хi, а сумма элементов i-го столбца дает полустепень захода вершины хi. По матрице смежности можно найти прямые и обратные отображения. Рассмотрим i-ю строку матрицы. Если элемент aij=1, то элемент графа хj входит в отображение Г(хi). Например, в 2-й строке матрицы А (рис.2,б) единицы стоят в 2-м и 5-м столбцах, следовательно, Г(х2) = { х2, х5}.

Для графа на рис.2,а матрица инциденций приведена на рис.4,в. Поскольку каждая дуга инцидентна двум различным вершинам, за исключением того случая, когда дуга образует петлю, то каждый столбец либо содержит один элемент равный 1 и один – равный – 1, либо все элементы столбца равны 0.

Для неориентированного графа, матрица инциденций определяется так же, за исключением того, что все элементы, равные –1, заменяются на 1.


Дата добавления: 2015-08-05; просмотров: 15; Нарушение авторских прав







lektsii.com - Лекции.Ком - 2014-2022 год. (0.016 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты