55) Маршруты в графавах.

Пусть G -- мульти- или псевдограф. Последовательность вершин и рёбер вида:

такая, что - ребро в графе G, соединяющее vi c vi+1 называется. Вершина v1 при этом называется началом маршрута, а vn+1 – концом маршрута. Число рёбер n в маршруте называется длиной маршрута. Во взвешенном графе за длину маршрута принимается сумма весов входящих в маршрут рёбер.

В простом графе, когда смежные вершины соединены только одним  ребром, для задания маршрута достаточно указать только последовательность вершин ( разумеется, любые две соседние вершины в этой последовательности должны быть смежными). В этом случае (v1, v n+1) – маршрут обозначается: (v1, v2, v3, …, vn+1).

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

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

Минимальная из длин всех циклов графа называется охватом графа.

Граф G называется связным, если в нем для любых двух вершин u и υ существует (u,υ)-маршрут.

В ориентированных графах рассматриваются ориентированные маршруты, в которых для любой пары соседних вершин υi и υi+1 существует дуга (υi, υi+1) (υi – начало дуги , υi+1 – конец). Другими словами – это маршруты, по которым можно передвигаться от начала маршрута к концу с соблюдением ориентации (стрелок).

56. Матрица смежности и матрица инцидентности.

57. Алгоритмы обхода графа в ширину и глубину.

58. Алгоритм Дейкстры.

56) Матрица смежности и матрица инцидентности.

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

A(Г) =	B(Г) =

Матрица смежности для неориентированного графа всегда симметрична. Фигурирующая в ней 2 может быть в некоторых случаях заменена на 1. В матрице инцидентности сумма единиц по столбцам указывает на степень вершины v_i. Нередко расположение вершин и ребер в этой матрице меняют местами (транспонируют). Так, для нашего конкретного орграфа Г₀ матрица A и B выглядят иначе:

A(Г0 ) =	B(Г0 ) =

В общем случае матрица смежности для ориентированного графа уже не будет симметричной. В матрице инцидентности ставится 1, если дуга исходит из вершины, и – 1, если дуга заходит в нее.

Число дуг в пути минимальной длины от вершины v_i до v_j называется расстоянием r(v_i, v_j). Если между вершинами не существует никакого пути, то расстояние равно бесконечноти: r(v_i, v_j) = ∞.

57) Алгоритмы обхода графа в ширину и глубину.

Обход графа в глубину

Описание алгоритма

Поиск в глубину (DFS, depth-first search) представляет собой классический гибкий алгоритм, который применяется для решения задачи связанности и множества других задач обработки графов. Возможны две реализации этого базового алгоритма: одна в виде рекурсивной процедуры, другая — с использованием явно заданного стека. Мы будем использовать стек магазинного типа. Применение правила LIFO (Last In First Out — последним пришел, первым обслужен), которое характеризует работу стека магазинного типа, соответствует исследованию соседних коридоров в лабиринте: из всех еще не исследованных коридоров выбирается последний из тех, с которым мы столкнулись. Словом стратегия поиска в глубину такова: идти «вглубь», пока это возможно (есть непройденные исходящие ребра), и возвращаться и искать другой путь, когда таких ребер нет. Так делается, пока не обнаружены все вершины, достижимые из исходной.

Цвет. Алгоритм поиска в глубину использует три цвета. Каждая из вершин вначале белая. Будучи обнаруженной (discovered), она становится темно серой; затем когда она будетполностью обработана (finished), то есть когда список смежных с ней вершин будет просмотрен, мы красим ее в черный цвет.

Процедура обхода графа в глубину

procedure push(const n: longint);

1 t := t + 1;

2 stack[t] := n;

3 visited[n] := 1;

function pop;

1 t := t - 1;

2 pop := stack[t];

procedure DFS(adjMatrix: array [0..n-1] of longint);

1 for i := 0 to n - 1 do visited[i] := 0;

2 for i := 0 to n - 1 do begin

3 if (visited[i] <> 1) then begin

4 t := 0;

5 push(i);

6 flag := false;

7 while t > 0 do begin

8 if flag then k := pop else k := stack[t];

9 flag := true;

10 for i := 0 to n - 1 do

11 if (adjMatrix[k, j] > 0) and (visited[j] <> 1) and flag then begin

12 push(j);

13 flag := false;

14 end;

15 end;

16 end;

17 end;

Пояснения

Процедура Push

добавляет элемент в стек; красит элемент в темно-серый цвет.

Функция Pop

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

Процедура DFS

Строка 1 — все вершины красятся в белый цвет. Строки 2–3 — находим начальный элемент новой компоненты связанности. Строки 4–6 — добавляем начальный элемент в стек. Строка 7 — проверяем, есть ли в стеке элементы. Строка 8 — проверяем, есть ли у элемента смежные вершины. Строки 10–14 — ищем смежную с элементом k вершину и добавляем ее в стек.

Обход графа в ширину

Описание алгоритма

Замена стека, используемого в обходе в глубину очередью FIFO (First In First Out — первым пришел, первым обнаружен) приводит к другому классическому алгоритму — к алгоритму поиска в ширину (BFS, breath-first search), который используется для решения других задач обработки графов, связанных с нахождением кратчайших путей. Поиск в ширину — один из базисных алгоритмов, составляющий основу многих других. Например, алгоритм Дейкстры поиска кратчайших путей и алгоритм Прима поиска минимального покрывающего дерева могут рассматриваться как обобщения поиска в ширину. Алгоритм поиска в ширину перечисляет все достижения из начальной вершины (вершины в порядке возрастания от начальной). Словом мы идем «вширь», а не «вглубь» (сначала просматривая все соседние вершины, затем соседей соседей и т. д.)

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

Процедура обхода графа в ширину

procedure push(const n: longint);

1 queue[head] := n;

2 head := head + 1;

3 visited[n] := 1;

function pop;

1 pop := queue[tail];

2 tail := tail + 1;

procedure BFS(adjMatrix: array [0..n-1] of longint);

1 for i := 0 to n - 1 do visited[i] := 0;

2 for i := 0 to n - 1 do begin

3 if (visited[i] <> 1) then begin

4 push(i);

5 while tail <> head do begin

6 k := pop;

7 for i := 0 to n - 1 do

8 if (adjMatrix[k, j] > 0) and (visited[j] <> 1) then

9 push(j);

10 end;

11 end;

12 end;