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

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

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

Студента 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. Понятие графов и их виды

Граф задается множеством точек или вершин х₁, х₂, ..., х_n и множеством линий или ребер a₁, a₂, ... , a_m, соединяющих между собой все или часть точек. Формальное определение графа может быть дано следующим образом [1].

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

G = (X, A),

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

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

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

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

Дуга a_i может быть представлена упорядоченной парой вершин (х_n, х_k), состоящей из начальной х_n и конечной х_k вершин. Например, для графа G₁ (рис.1,а) дуга a₁ задается парой вершин (x₁, x₂), а дуга а₃ парой (x₂, x₃). Если х_n, х_k – концевые вершины дуги a_i, то говорят, что вершины х_n и х_k инцидентны дуге a_i или дуга a_i инцидентна вершинам х_n и х_k.

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

Каждая вершина орграфа х_i может характеризоваться полустепенью исхода d₀(х_i) и полустепенью захода d_t(х_i).

Полустепенью исхода вершины х_i — d₀(х_i) называется количество дуг, исходящих из этой вершины. Например, для орграфа G₁ (рис.1,а) характеристики полустепеней исхода следующие: d₀(х₁)=1, d₀(х₂)=2, d₀(х₃)=2, d₀(х₄)=1.

Полустепенью захода вершины х_i — d_t(х_i) называется количество дуг, входящих в эту вершину. Например, для орграфа G₁: d_t(х₁)=2, d_t(х₂)=1, d_t(х₃)=2, d_t(х₄ )=1.

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

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

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

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

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

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

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

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

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

a_ij = 1, если ∃ дуга (х_i, х_j),

a_ij = 0, если нет дуги (х_i, х_j).

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

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

b_ij = 1, если х_i является начальной вершиной дуги a_j,

b_ij = –1, если х_i является конечной вершиной дуги a_j,

b_ij = 0, если х_i не является концевой вершиной дуги a_j или если a_j является петлей.

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

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

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

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