Теория графов Основные определения. Дуга Пусть имеется множество вершин V={V 1,V 2,…,V n } и пусть на нем задано бинарное отношение Г V×V, – V i Г V j. - презентация

1 Теория графов Основные определения

2 Дуга Пусть имеется множество вершин V={V 1,V 2,…,V n } и пусть на нем задано бинарное отношение Г V×V, – V i Г V j (V i V j ) Г – эту пару назовем дугой U k

3 Пример

4 Неориентированные графы Если бинарное отношение симметрично, то наряду с дугой (Vi,Vj) есть дуга (Vj,Vi). В этом случае чаще всего переходят к неориентированным графам.

5 Задание графов Матрица инцидентности A. По вертикали указываются вершины, по горизонтали - ребра. a ij =1 если вершина i инцидентна ребру j, в противном случае a ij =0. Для орграфа a ij =-1 если из вершины i исходит ребро j, a ij =1 если в вершину i входит ребро j. Если ребро - петля, то a ij =2. Список ребер. В первом столбце ребра, во втором вершины им инцидентные. Матрица смежности - квадратная симметричная матрица. По горизонтали и вертикали - все вершины. D ij = число ребер, соединяющее вершины i,j. Матрица Кирхгофа: b ij =-1, если вершины i и j смежны, b ij =0 если вершины i и j не смежны. Сумма элементов в каждой строке и каждом столбце матрицы Кирхгофа равна 0.

6

7 Полустепень вершины Для ориентированных графов: полустепенью исхода вершины |Г(V i )| будем называть число дуг, исходящих из вершины V i ; полустепенью захода вершин |Г -1 (V i )| будем называть число дуг, заходящих в вершину. В орграфе две локальных степени вершины v: deg(v)+ и deg(v) - (число ребер с началом и концом в v). Для неориентированных графах говорят только о степени. Следствие 2 из леммы о рукопожатиях. Число ребер в полном графе n(n-1)/2.

8 Достижимость Матрица достижимости R={r ij }, {r ij }=1, если V j достижима из V i, {r ij }=0 в противном случае. R=E+A+А 2 +…+A k В степенях используется «булевское» умножение матриц (строк на столбец, но 1+1=1, 0+1=1,0+0=0, 1+0=0). K – такое число, при котором дальнейшее сужение степеней не меняет матрицу R.

9 Алгоритм Краскалла Составляется список ребер в порядке увеличения весов. В искомое дерево добавляем, начиная с первого элемента списка по порядку этого списка ветви до те пор, пока не встречаем ветвь, образующую с ранее включенной цикл. Данную ветвь вычеркиваем из списка. Затем продолжаем аналогичные действия до (n-1) ветви.

10

11 Алгоритм Дейкстры Пусть имеется направленный ориентированный граф с двумя выделенными вершинами V s и V t. Найти минимальный направленный путь из V s в V t. Помечаем вершину V s, и присваиваем ей вес q s :=0, а всем остальным присваиваем временный вес q i = Полагаем i=s – номер последней отмеченной вершины Для каждой неотмеченной вершины V j выполняется следующий оператор q j :=min(q j, q i +p ij ), где p ij – вес ветви, ведущей из i-той вершины в j-тую, если нет p ij, считаем p ij =

12 Алгоритм Дейкстры Проверяем, есть ли среди только что отмеченных q j конечное значение. Если таких вершин нет, то мы завершаем алгоритм, пути из s в t не существует. Если же конечное значение q j найдется, то из них выбирается минимальная. Пусть это вершина j 0, тогда мы помечаем эту вершину, а так же помечаем ту дугу, по которой мы добирались в вершину V j0, при получении этого минимального значения. I=j o Проверяем условие i=t. Если это так, алгоритм завершается, L(s-t)=q j0. Сам же минимальный путь считается, начиная с вершины Vt по выделенным дугам в обратном порядке. Если же it, возвращаемся к пункту 3.

13

14

15

16

17

18