Достижимость и обходы графа

Графовые алгоритмы(33-39)

33.

1) Граф G(V,E) - совокупность двух множеств – непустого множества V (множества вершин) и множества E (множества ребер) неупорядоченных пар различных элементов множества V

G(V,E) = {V,E}, V ¹Æ, EÌV´V, E=E^-1.

Число вершин графа G - p, а число ребер – q:

p = p(G) = |V|, q = q(G) = |E|.

2) Пусть v1, v2 – вершины, e=(v1,v2) – соединяющее их ребро. Тогда вершина v1 и ребро e инцидентны, вершина v2 и ребро e также инцидентны. Два ребра, инцидентные одной вершине, называются смежными; две вершины, инцидентные одному ребру, также называются смежными

3) Множество вершин, смежных с вершиной v, называется множеством смежности вершины v и обозначается

Г (v): Г (v) = {uÎV | (u,v)ÎE}

4) Если элементами множества E являются упорядоченные пары, то граф называется ориентированным (или орграфом). В этом случае элементы множества V называются узлами, а элементы множества E – дугами

5) Если элементом множества E может быть пара одинаковых элементов V, то такой элемент E называется петлей, а граф называется графом с петлями (или псевдографом).

6) Если E является не множеством, а набором, содержащим несколько одинаковых элементов, то эти элементы называются кратными ребрами, а граф называется мультиграфом.

7) Если задана функция F:VàM и/или F:EàM, то множество M называется множеством пометок, а граф называется помеченным.

8) Маршрутом в графе называется чередующаяся последовательность вершин и ребер v₀,e₁,v₁,e₂,v₂,…,e_k,v_k, в которой любые два соседних элемента инцидентны.

Для обычных графов достаточно просто перечислить либо последовательность вершин либо ребер. Если v₀=v_k, то маршрут замкнут, в противном случае – открыт. Если все входящие в маршрут ребра различны, то маршрут называется цепью.

9) Длиной маршрута называется количество ребер в нем (с повторениями). Расстоянием между вершинами u и v (обозначается d(u,v)) называется длина кратчайшей цепи {u,v}

10) Две вершины в графе связаны, если существует соединяющая их цепь. Граф, в котором все вершины связаны, называется связным.

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

Это двоичная матрица, кот определяется по правилу:

ì1, если вершина v _iсмежна с вершиной v _j

M[i,j] = í

î0, если вершины v _iи v _j не смежны

Размер матрицы смежности n(p,q) = O(p²).

G:| 0 1 0 1 | D: | 0 1 0 0 |

| 1 0 1 1 | | 0 0 1 1 |

| 0 1 0 1 | | 0 0 0 0 |

| 1 1 1 0 | | 1 0 1 0 |

Матрица инцидентности

Отражает отношение инцидентности

ì1, если v _i инцидентна e _j

H[i,j] = í

î0, в противном случае.

Для ориентированного графа используется троичная матрица:

ì1, если v _iинцидентна e _j и является его концом;

H[i,j] = í0, если v _i не инцидентна e _j;

î-1, если v _iинцидентна e _j и является его началом.

n(p,q) = O(pq).

G: | 1 0 0 1 0 | D: |-1 0 0 1 0 |

| 1 1 0 0 1 | | 1 -1 0 0 1 |

| 0 1 1 0 0 | | 0 1 1 0 0 |

| 0 0 1 1 1 | | 0 0 –1 –1 1 |

Списки смежности

Представление с помощью списочной структуры, отражающей смежность вершин – список смежности.

В случае представлений неориентиров.графовn(p,q) = O(p+2q), ориентированных – n(p,q) = O(p+q).

37. Массив дуг

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

begin	end

begin	end

 

 

Для массива ребер (или дуг) оценка n(p,q) = O(2q).

Достижимость и обходы графа

Требуется определить, существует ли путь (задача определения достижимости), ведущий из i-ой вершины в j-ую, а также найти самый короткий и самый длинный.

Проверка достижимости достигается перемножением матриц смежности – каждое следующее перемножение на матрицу смежности приводит к матрице, содержащей пути соответствующей степени.

Обход графа –некоторое систематическое перечисление его вершин (и/или ребер)

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

Задача: задан ориентированный «взвешенный» граф. Найти кратчайший по длине путь между двумя заданными вершинами.

«Взвешенный» – каждой дуге сопоставлено некотор.отриц.число.

Обозначим через u_i кратчайшее расстояние от исходного узла 1 до узла i, через d_ij - длину ребра (i, j).

Тогда для узла j определим метку [u_j, i] следующим образом: [u_j, i] = [u_i + d_ij, i], d_ij >= 0.

Метки узлов могут быть двух типов: временные и постоянные.

Шаг 0. Исходному узлу (1) присваивается метка [0, -]. Полагаем i = 1.

Шаг i. а) Вычисляются временные метки [u_i + d_ij, i] для всех узлов j, которые можно достичь непосредственно из узла i и которые не имеют постоянных меток. Если узел j уже имеет метку [u_j, k], полученную от другого узла k, и если u_i + d_ij < u_j, тогда метка [u_j, k] заменяется на [u_i + d_ij, i].

b) Если все узлы имеют постоянные метки, процесс вычислений заканчивается. В противном

случае выбирается метка [u_r, s] с наименьшим значением расстояния u_r среди всех временных меток

(если таких меток несколько, то выбор произволен). Полагаем i = r и повторяем шаг i.

Шаг 0. Назначаем узлу 1 постоянную метку [0, -].

Шаг 1. Из узла 1 можно достичь узлов 2 и 3. Вычисляем метки для этих узлов, в результате получаем следующую таблицу меток:

Узел Метка Статус метки 1 [0, -] Постоянная 2 [0 + 100, 1] = [100, 1] Временная 3 [0 + 30, 1] = [30, 1] <-Временная

Третий узел имеет наименьшее значение расстояния (u₃ = 30). Поэтому статус метки этого узла изменяется на "постоянная".

Шаг 2. Из узла 3 (последнего узла с постоянной меткой) можно попасть в узлы 4 и 5. Получаем следующий список узлов:

Узел Метка Статус метки 1 [0, -] Постоянная 2 [100, 1] Временная 3 [30, 1] Постоянная 4 [30 + 10, 3] = [40, 3] <-Временная 5 [30 + 60, 3] = [90, 3] Временная

Временный статус метки [40, 3] узла 4 заменяется на постоянный (u₄ = 40).

Шаг 3. Из узла 4 можно достичь узлов 2 и 5. После вычисления меток получим следующий их список:

Узел Метка Статус метки 1 [0, -] Постоянная 2 [40 + 15, 4] = [55, 4] <-Временная 3 [30, 1] Постоянная4 [40, 3] Постоянная 5 [90, 3] или [40+50, 4]=[90,4] Временная

Временная метка [100, 1], полученная узлом 2 на втором шаге, изменена на [55, 4]. Это указывает на то, что найден более короткий путь к этому узлу (проходящий через узел 4). На третьем шаге узел 5 получает две метки с одинаковым значением расстояния u₅ = 90.

Шаг 4. Из узла 2 можно перейти только в узел 3, но он уже имеет постоянную метку, которую нельзя изменить. Поэтому на данном шаге получаем такой же список меток, как и на предыдущем шаге, только метка узла 2 получает статус постоянной.

Шаг 5. С временной меткой остается только узел 5, но так как из этого узла нельзя попасть ни в какой другой, ему присваивается постоянный статус и процесс вычислений заканчивается.

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

(2) -> [55, 4] -> (4) -> [40, 3] -> (3) -> [30, 1] ->(1)

Между узлами (2) и (1): [55, 4].