Практическое занятие №18

Практическое занятие №18 (1И)

Тема: Алгоритмы моделирования кратчайших путей между вершинами

Цель работы: решить задачу о нахождении кратчайших путей в графе. Решить задачу о нахождении максимального потока.

 Оборудование: персональный компьютер, MS Word

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

Графы обычно изображаются в виде геометрических фигур, так что вершины графа изображаются точками, а ребра - линиями, соединяющими точки (рис. 1).

Петля это дуга, начальная и конечная вершина которой совпадают.

Простой граф - граф без кратных ребер и петель.

Степень вершины это удвоенное количество петель, находящихся у этой вершины плюс количество остальных прилегающих к ней ребер.

Пустым называется граф без ребер. Полным называется граф, в котором каждые две вершины смежные.

Рис. 1

Путь в ориентированном графе — это последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей.

Маршрут в графе путь, ориентацией дуг которого можно пренебречь.

Цепь маршрут, в котором все ребра попарно различны.

Цикл замкнутый маршрут, являющийся цепью.

Маршрут, в котором все вершины попарно различны, называют простой цепью. Цикл, в котором все вершины, кроме первой и последней, попарно различны, называются простым циклом.

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

Подграф называется остовным подграфом, если множество его вершин совпадает с множеством вершин самого графа.

Граф называется связным, если любая пара его вершин связана.
Связными компонентами графа называются подграфы данного графа, вершины которых связаны.

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

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

Очевидно, что графический способ представления графов непригоден для ПК. Поэтому существуют другие способы представления графов.

В теории графов применяются

• Матрица инцидентности. Это матрица А с n строками, соответствующими вершинам, и m столбцами, соответствующего рёбрам. Для ориентированного графа столбец, соответствующий дуге (х,y) содержит - 1 в строке, соответствующей вершине х и 1, в строке, соответствующей вершине у. Во всех остальных 0. Петлю, т.е. дугу (х,х) можно представлять иным значением в строке х, например, 2. Если граф неориентированный, то столбец, соответствующий ребру (х,у) содержит 1, соответствующие х и у и нули во всех остальных строках.

• Матрица смежности. Это матрица n×n где n - число вершин, где b_ij = 1, если существует ребро, идущее из вершины х в вершину у и b_ij = 0 в противном случае.

Нахождение минимального остова в графе

Алгоритм решения

1. Упорядочить ребра графа по возрастанию весов;

2. Выбрать ребро с минимальным весом, не образующее цикл с ранее выбранными ребрами. Занести выбранное ребро в список ребер строящегося остова;

3. Проверить, все ли вершины графа вошли в построенный остов. Если нет, то выполнить пункт 2.

Нахождение кратчайшего пути в графе

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

Данная задача может быть разбита на две:

1. для начальной заданной вершины найти все кратчайшие пути от этой вершины к другим;

2. найти кратчайшие пути между всеми парами вершин.

Рассмотрим алгоритм решения для задачи первого типа:

Необходимо найти путь от s - начальной вершины до t - конечной вершины. Каждой вершине присваиваем пометки I(Xi).

1. I(s) = 0, I(Xi) равно бесконечности для всех Хi не равных s и считать эти пометки временными. Положить р = s.

2. Для всех Хi, принадлежащих Г(р) и пометки которых временны, изменить пометки по следующему правилу:
   I(Xi) = min[I(Xi), I(p) + c(p, Xi)]

3. среди всех вершин с временными пометками найти такую, для которой I(Xi*) = min[I(Xi)]

4. считать пометку вершины Хi* постоянной и положить р = Хi*.

5. если р = t, то I(р) является длинной кратчайшего пути, если нет, перейти к шагу 2.

Как только все пометки расставлены, кратчайшие пути получают, используя соотношение I(Xi') + c(Xi',Xi) = I(Xi) (1).

Для решения задачи второго типа можно применять данный алгоритм для каждой вершины.

Порядок выполнения заданий

Задача 1. Составить матрицы инцидентности и смежности для графа:

Решение.

Задача 2. На представленном графе найдите: а) минимальный остов дерева, б) найдите кратчайший путь от начальной точки Х1 до всех остальных точек.

Решение. а) Найдем минимальный остов дерева представленного на рисунке. Составим таблицу значений расстояний между точками.

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

Из элементов матрицы выбираем минимальный - (Х2,Х5) = 1. Обводим выбранный элемент кружком и указываем на рисунке соответствующее ребро.

Из оставшихся элементов выбираем минимальный - (Х3,Х5) = 4. Элемент обводим кружком. Чтобы выполнялось условие 2 пункты Х2 и Х3 не должны соединяться, поэтому элемент (Х2,Х3) зачёркивается. И т.д.

В итоге получаем:

Длина минимального остова равна (Х1,Х2)+(Х2,Х5)+(Х3,Х5)+(Х4,Х5)=23+1+4+9=37

Б) Найдем кратчайший путь представленного графа от начальной точки Х1 до всех остальных точек.

Начальное расстояние I(X1)=0*, I(Xi)=∞, Xi≠X1, p=X1.

Находим множество точек, соединяющиеся с точкой Х1:

Г{X1}={X2,X5}

Находим минимальное расстояние каждой из этих точек:

I(X2)=min[∞,0*+23]=23,

I(X5)=min[∞,0*+36]=36,

min[I(X2), I(X3), I(X4), I(X5)]=min[23, 36, ∞, ∞]=23,

X2: I(X2)=23*, p=23, рядом с точкой Х2 поставим расстояние 23.

Находим множество точек, соединяющиеся с точкой Х2, точку Х1 не трогаем, так как мы ее уже рассмотрели.

Г{X2}={X3,X5}

Находим минимальное расстояние каждой из этих точек:

I(X3)=min[∞,23*+20]=43,

I(X5)=min[36,23*+1]=24,

min[I(X3), I(X4), I(X5)]=min[43,∞, 24]=24,

X5: I(X5)=24*, p=24, рядом с точкой Х5 поставим расстояние 24.

Аналогично находим все остальные расстояния до остальных точек:

Г{X5}={X3,X4}

Находим минимальное расстояние каждой из этих точек:

I(X3)=min[43,24*+4]=28,

I(X4)=min[∞,24*+9]=33,

min[I(X3), I(X4)]=min[28, 33]=28,

X3: I(X3)=28*, p=28, рядом с точкой Х3 поставим расстояние 28.

Г{X3}={X4}

Находим минимальное расстояние до этой точки:

I(X4)=min[33,28*+15]=33,

X4: I(X4)=33*, p=33, рядом с точкой Х4 поставим расстояние 33.

Запишем ответ в виде таблицы кратчайших расстояний от точки Х1 до всех остальных точек графа.

1 подгруппа

Задача 1. Составить матрицы инцидентности и смежности для графа:

Задача 2. На представленном графе найдите: а) минимальный остов дерева, б) найдите кратчайший путь от начальной точки Х1 до всех остальных точек.

2 подгруппа

Задача 1. Составить матрицы инцидентности и смежности для графа:

Задача 2. На представленном графе найдите: а) минимальный остов дерева, б) найдите кратчайший путь от начальной точки Х1 до всех остальных точек.

1. Дайте определение граф.

2. В чем состоит отличие ориентированного графа от неориентированного графа?

3. В чем отличие пустого графа от простого графа?

4. Как определить степень вершины?

5. Чем отличается цепь в графе от цикла?

6. Дайте понятие подграф графа.

7. В чем суть связанного графа?

8. Как находятся матрицы инцидентности и матрицы смежности?

9. Как найти минимальный остов дерева?

10. Как найти кратчайшее расстояние в графе?