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

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

G₄ = (Х, А),

где Х = {х_i}, i = 1, 2, 3, 4 – множество вершин; А = {a_i }, i = 1, 2, ..., 6 – множество дуг, причем А = {(х₁, х₂), (х₄, х₂), (х₂, х₄ ), (х₂, х₃), (х₃, х₃), (х₄ , х₁)}.

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

G₅ = (X, A),

где X = {B, C, D, E, F} – множество вершин графа, A = {a_i}, i = 1, 2, ..., 5 – множество дуг графа, причем a₁ = (F, B), a₂ = (B, E), a₃ = (F, D), a₄ = (E, C), a₅ = (C, D).

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

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

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

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

Отображением вершины х_i — Г(х_i) является множество вершин, в которые существуют дуги из вершины х_i, т. е. Г(х_i) = { х_j: ∃ дуга (х_i, х_j) ∈ A}.

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

G₄=(X, Г)),

где X = {х_i}, I = 1, 2, ..., 4 – множество вершин, Г(х₁) = { х₂ }, Г(х₂) = { х₃, х₄ }, Г(х₃) = {х₃}, Г(х₄) = { х₁, х₂ } – отображения.

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

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-ое расстояние, очевидно равно нулю,
так как расстояние от 0-ой вершины до самой себя равно нулю

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

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

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

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

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

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

33. continue;

34. }

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

36. distance[from] + weight);

37. }

38. }

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

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

41. printWriter.println("NO");

42. }

43. else {

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

45. }

46. }

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

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

49. }

50. public class Edge {

51. int from;

52. int to;

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

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

55. this.from = u;

56. this.to = v;

57. this.weight = w;

58. }

59. }

60. }

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, то это
означает, что дуги из i в j нет; в этом случае расстояние между этими вершинами бесконечно велико

20. }

21. }

22. }

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

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

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

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

27. }

28. }

29. }

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

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

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

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

34. }

35. else {

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

37. }

38. }

39. printWriter.println();

40. }

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

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

43. }

44. }

Заключение

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

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

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

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