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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Московский педагогический государственный университет

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

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

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

На тему: «Алгоритмы на графах»

Выполнил: студент 2 курса 2 группы

А.В. Анцупов

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

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

Москва, 2015 г.



Содержание

Введение

1. Графы

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

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

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

1.2.2 Теоретико-множественное представление графов

1.2.3 Задание графов соответствием

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

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

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

Заключение

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



Введение

Тема данной курсовой работы «Алгоритмы на графах» является очень актуальной в настоящее время. Благодаря своему широкому применению данная тема постоянно развивается и совершенствуется. Данная тема очень широко применяется даже в обыденной жизни человека: поиск кратчайшего пути от одной точки до другой, в работе GPS при анализе загруженности дорог и выборе оптимального маршрута движения, коммутации информационных пакетов в сетях (например, Интернет) и прочее. Можно найти множество способов применить данную тему в жизни.

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

В настоящее время существует два наиболее популярных алгоритма поиска кратчайшего пути:

1. Алгоритмы Беллмана - Форда;

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

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

Каждый из представленных алгоритмов используется в компьютерной технике, поэтому важно отметить в данной курсовой работе и способы представления математической модели «граф», которые получили наибольшее распространение, выделить их достоинства и недостатки.

При выполнении данной курсовой работы ставятся следующие задачи:

1. Рассмотреть понятие графа и их существующие виды.

2. Рассмотреть существующие способы представления графов в вычислительной технике.

3. Дать определение кратчайшего пути.

4. Изучить существующие алгоритмы поиска кратчайшего пути в графах.

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

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

Так что же такое «граф»? Перейдем непосредственно к рассмотрению данного вопроса.



1. Графы

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

Граф задается множеством точек или вершин х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 может характеризоваться полустепенью исхода d0(хi) и полустепенью захода dt(хi).

Полустепенью исхода вершины хi -- d0(хi) называется количество дуг, исходящих из этой вершины. Например, для орграфа G1 (рис.1,а) характеристики полустепеней исхода следующие:

d0(х1)=1

d0(х2)=2

d0(х3)=2

d0(х4)=1

Полустепенью захода вершины хi -- dt(хi) называется количество дуг, входящих в эту вершину. Например, для орграфа G1:

dt(х1)=2

dt(х2)=1

dt(х3)=2

dt(х4 )=1

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

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

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

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

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

1.2.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.

1.2.2 Теоретико-множественное представление графов

Граф описывается перечислением множества вершин и дуг. Примеры описания приведены для орграфов на рис.3 и рис.4.

G4 = (Х, А)

где Х = {хi}, i = 1, 2, 3, 4 - множество вершин; А = {ai }, i = 1, 2, ..., 6 - множество дуг, причем А = {(х1, х2), (х4, х2), (х2, х4 ), (х2, х3), (х3, х3), (х4 , х1)}.

Рис.3. Пример орграфа.

G5 = (X, A)

где X = {B, C, D, E, F} - множество вершин графа, A = {ai}, i = 1, 2, ..., 5 - множество дуг графа, причем a1 = (F, B), a2 = (B, E), a3 = (F, D), a4 = (E, C), a5 = (C, D).

Рис.4. Пример орграфа.

1.2.3 Задание графов соответствием

Описание графов состоит в задании множества вершин Х и соответствия Г, которое показывает, как между собой связаны вершины.

Соответствием Г называется отображение множества Х в Х, а граф в этом случае обозначается парой G = (X, Г).

Отображением вершины хi -- Г(хi) является множество вершин, в которые существуют дуги из вершины хi, т. е. Г(хi) = { хj: ? дуга (хi, хj) ? A}.

Так для орграфа на рис.2 описание заданием множества вершин и соответствия выглядит следующим образом:

G4=(X, Г))

где X = {хi}, I = 1, 2, ..., 4 - множество вершин, Г(х1) = { х2 }, Г(х2) = { х3, х4 }, Г(х3) = {х3}, Г(х4) = { х1, х2 } - отображения.

Для неориентированного или смешанного графов предполагается, что соответствие Г задает такой эквивалентный ориентированный граф, который получается из исходного графа заменой каждого ориентированного ребра двумя противоположно направленными дугами, соединяющими те же самые вершины. Например, для графа на рис.1,б Г(х2) = { х1, х3, х5 }, Г(х4) ={ х3, х5} и т. д. граф матричный алгоритм вычислительный



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

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

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

Алгоритм решения. Предположим сначала, что граф не содержит циклов отрицательного веса.

Пусть N - количество вершин графа, M - количество дуг, - вес дуги, ведущей из вершины i в вершину j. Обозначим за вес кратчайшего пути из v в j, который содержит не более i дуг. В случае отсутствия такого пути положим , где бесконечность - это некоторое значение, заведомо превосходящее все возможные расстояния. При существует единственный допустимый путь - путь из вершины v в неё саму, имеющий нулевой вес. Соответственно, при . Пусть теперь . Понятно, что кратчайший путь из вершины v в вершину j состоит из кратчайшего пути из v в некоторую вершину p и дуги . Тогда можно записать следующие рекуррентные соотношения:

Здесь V -- множество вершин графа, E -- множество дуг.

Отметим, что оптимальный путь не должен содержать циклов. В самом деле, если у нас есть некоторый путь с циклом, то, выбросив цикл, мы получим путь меньшего либо равного веса. Тогда максимальное количество дуг в пути будет равно N-1(в противном случае в пути появится цикл).

Если реализовывать алгоритм непосредственно по приведённым выше соотношениям, то его сложность составит O(M). Попробуем улучшить эту оценку. Заметим, что для каждой дуги можно однозначно определить, при решении подзадач для какой именно вершины она будет использована. Тогда, вместо того чтобы при каждом i перебирать все вершины и для каждой из них все рёбра, можно просто перебрать все рёбра. Получаем асимптотическую сложность O(NM).

Кроме того, нет смысла хранить всю матрицу весов кратчайших путей. Достаточно лишь двух её последних строк. Если же мы немного отойдём от составленных рекуррентных соотношений, то сможем обойтись всего одной строкой. В самом деле, будем брать веса вспомогательных путей из некоторой строки и записывать улучшенные значения в неё же. Тогда после завершения i-ой итерации могут быть найдены веса оптимальных путей, содержащих более чем i дуг, однако все кратчайшие пути, содержащие t дуг, гарантированно будут найдены после выполнения t-ой итерации (действительно, они либо будут найдены на t-ой итерации в соответствии с рекуррентными соотношениями, либо ранее).

Предположим, что нам необходимо вывести также сам кратчайший путь. Тогда для каждой подзадачи необходимо будет сохранять предпоследнюю вершину в пути, т.е. значение k. Это значит, что понадобится матрица размерности NM.

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



Задача 1

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

Входные данные:

В первой строке записаны целые числа N и M - количество вершин и количество дуг соответственно . Дальше идет M строк с тройками целых чисел X, Y, W, обозначающими, что дуга из X в Y имеет вес W .

Выходные данные:

Вывести N-1 строку - длины кратчайших путей от первой вершины до всех остальных вершин в порядке возрастания их номеров. Если же до некоторой вершины не существует пути из первой, то в соответствующей строке необходимо вывести «NO».

1. import java.io.PrintWriter;

2. import java.util.Arrays;

3. import java.util.Scanner;

4. public class Solution {

5. private static final int INF = 1000 * 1000 * 1000; //в качестве условной бесконечности выберем достаточно большое число 10^9

6. public static void main(String[] args) {

7. Solution solution = new Solution();

8. solution.solve(); //вызываем процедуру решения задачи

9. }

10. private void solve() {

11. Scanner scanner = new Scanner(System.in);//для считывания воспользуемся классом Scanner

12. PrintWriter printWriter = new PrintWriter(System.out); //для считывания воспользуемся классом PrintWriter

13. int vertexCount = scanner.nextInt(); //считываем число вершин графа

14. int edgeCount = scanner.nextInt(); //считываем число дуг графа

15. Edge[] edges = new Edge[edgeCount]; //дуги графа будем хранить в массиве

16. for (int i = 0; i < edgeCount; i++) { //экземпляров класса Edge

17. int from = scanner.nextInt(); //считываем начальную вершину i-ой дуги

18. int to = scanner.nextInt(); //считываем конечную вершину i-ой дуги

19. int weight = scanner.nextInt(); //считываем вес i-ой дуги

20. from--;

21. to--; //так как нами используется 0-ая индексация, то уменьшим индексы вершин на единицу

22. edges[i] = new Edge(from, to, weight); //кладём считанную дугу в массив дуг

23. }

24. int[] distance = new int[vertexCount]; //создаем массив, i-ый элемент которого будет хранить текущее расстояние от 1-ой (или 0-ой в нашем случае 0-индексации) до i-ой вершины графа

25. Arrays.fill(distance, INF); //до начала работы алгоритма все расстояния, кроме 0-го, равны бесконечности (условной)

26. distance[0] = 0; //0-ое расстояние, очевидно равно нулю,

27. так как расстояние от 0-ой вершины до самой себя равно нулю

28. for (int i = 0; i < vertexCount - 1; i++) {

29. for (int j = 0; j < edgeCount; j++) {

30. int from = edges[j].from;

31. int to = edges[j].to;

32. int weight = edges[j].weight; //в соответствии с алгоритмом будем обновлять массив расстояний

33. if (distance[from] == INF) { //ясно, что если вершина from на текущем шаге работы алгоритма находится бесконечно далеко от 0-ой, то она не изменит ответ

34. continue;

35. }

36. distance[to] = Math.min(distance[to], //В противном случае обновим расстояние до вершины to, это называют релаксацией

37. distance[from] + weight);

38. }

39. }

40. for (int i = 1; i < vertexCount; i++) {

41. if (distance[i] == INF) {

42. printWriter.println("NO");

43. }

44. else {

45. printWriter.println(distance[i]); //выводим расстояние от 0-ой вершины до каждой отличной от нее

46. }

47. }

48. scanner.close(); //закрытие потока ввода

49. printWriter.close(); //закрытие потока вывода

50. }

51. public class Edge {

52. int from;

53. int to;

54. int weight; //для удобства хранения дуг графа создадим класс, содержащий информацию о весе дуги, начальной и конечной вершинах дуги

55. public Edge(int u, int v, int w) {

56. this.from = u;

57. this.to = v;

58. this.weight = w;

59. }

60. }

61. }

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

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

Алгоритм решения. Пусть веса дуг заданы в виде матрицы D. Будем решать задачу методом динамического программирования. Обозначим за длину кратчайшего пути между вершинами i и j, который в качестве промежуточных содержит только вершины с номерами, не превосходящими k. Рассмотрим случай, когда k=0. Это означает, что промежуточных вершин в путях быть не может. Значит, путь будет существовать между теми вершинами, между которыми по условию есть дуга. Тогда матрицу построим на основе матрицы D следующим образом. Во-первых, расстояние между вершинами, между которыми нет дуги, положим равным бесконечности. Во-вторых, из вершины в неё саму всегда можно добраться за нулевое число шагов, поэтому если вес дуги (i,j) положителен, то заменим его нулём. Пусть теперь k>0. Понятно, что искомый кратчайший путь может либо проходить через вершину с номером k, либо нет. Если он проходит через эту вершину, то его можно разбить на две части: путь от i до k и путь от k до j. Поскольку оба этих пути должны являться кратчайшими, имеем следующее рекуррентное соотношение:



Асимптотическая сложность алгоритма - O(), где N - число вершин графа.

Так же, как и в алгоритме Форда-Беллмана, объём используемой памяти можно сократить. Нам достаточно одной матрицы размерности N. Все обновления расстояний мы будем осуществлять именно в ней.

Отметим, что при наличии в графе циклов отрицательного веса существуют кратчайшие пути сколь угодно малого веса. Имеет место следующий критерий: в графе есть циклы отрицательного веса тогда и только тогда, когда для некоторого i .

Задача 2

Дан взвешенный ориентированный граф из N вершин. Требуется найти в нем величину кратчайшего пути между каждой парой вершин.

Входные данные:

В первой строке записано натуральное число . В каждой из следующих N строк записано по N чисел -- матрица весов дуг графа. Все веса представляют собой целые неотрицательные числа, не превосходящие 1000. Если в матрице в i-й строке j-м столбце стоит 0, то это означает, что дуги из вершины i в вершину j нет.

Выходные данные:

В выходной файл надо вывести матрицу кратчайших путей между каждой парой вершин графа (т.е. матрицу у которой в i-й строке j-м столбце стоит длина кратчайшего пути из вершины i в вершину j или 0 -- если пути из i в j не существует).

1. import java.io.PrintWriter;

2. import java.util.Arrays;

3. import java.util.Scanner;

4. public class Solution {

5. private static final int INF = 1000 * 1000 * 1000; //в качестве условной бесконечности выберем достаточно большое число 10^9

6. public static void main(String[] args) {

7. Solution solution = new Solution();

8. solution.solve(); //вызываем процедуру решения задачи

9. }

10. private void solve() {

11. Scanner scanner = new Scanner(System.in);//для считывания воспользуемся классом Scanner

12. PrintWriter printWriter = new PrintWriter(System.out); //для считывания воспользуемся классом PrintWriter

13. int vertexCount = scanner.nextInt(); //cчитываем число вершин графа

14. int[][] g = new int[vertexCount][vertexCount]; //граф будем хранить в матрице смежности

15. for (int i = 0; i < vertexCount; i++) {

16. for (int j = 0; j < vertexCount; j++) {

17. g[i][j] = scanner.nextInt(); //считываем вес ребра между вершинами i и j соответственно

18. if (g[i][j] == 0) {

19. g[i][j] = INF; //по условию если g[i][j] = 0, то это

20. означает, что дуги из i в j нет; в этом случае расстояние между этими вершинами бесконечно велико

21. }

22. }

23. }

24. for (int k = 0; k < vertexCount; k++) {

25. for (int i = 0; i < vertexCount; i++) {

26. for (int j = 0; j < vertexCount; j++) { // Согласно алгоритму будем обновлять ответ для каждой пары вершин i и j, перебирая промежуточную вершину k

27. g[i][j] = Math.min(g[i][j], g[i][k] + g[k][j]);

28. }

29. }

30. }

31. for (int i = 0; i < vertexCount; i++) {

32. for (int j = 0; j < vertexCount; j++) {

33. if (g[i][j] == INF) {

34. printWriter.print(0 + " ");

35. }

36. else {

37. printWriter.print(g[i][j] + " "); //для каждой пары вершин выведем величину кратчайшего пути от i до j, или 0, если j не достижима из i

38. }

39. }

40. printWriter.println();

41. }

42. scanner.close(); //закрытие потока ввода

43. printWriter.close(); //закрытие потока вывода

44. }

45. }



Заключение

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

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

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



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

Источники на русском языке

1. Ананий В. Левитин. Алгоритмы: введение в разработку и анализ. - М.: «Вильямс», 2006.

2. Асельдеров З.М., Донец Г.А. Представление и восстановление графов - К.: Наукова Думка, 1991.

3. Басакер Р., Саати Т. Конечные графы и сети. - М.: Наука, 1974.

4. Зыков А. А. Основы теории графов. - М.: «Вузовская книга», 2004.

5. Касьянов В. Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. - СПб.: БХВ-Петербург, 2003.

6. Оре О. Теория графов. - 2-е изд. - М.: Наука, 1980.

7. Харари Ф. Теория графов. - М.: КомКнига, 2006

Электронные ресурсы

8. Википедия: Граф [электронный ресурс]: URL: http://ru.wikipedia.org/wiki/Граф_(математика)

9. Википедия: Теория графов [электронный ресурс]: URL: http://ru.wikipedia.org/wiki/Теория_графов

10. Сиберн: Алгоритм Беллмана-Форда [электронный ресурс]: URL: http://cybern.ru/algoritm-forda-bellmana.html

11. Сиберн: Алгоритм Флойда-Уоршелла [электронный ресурс]: URL: http://cybern.ru/algoritm-flojda-uorshella.html

Размещено на Allbest.ru