Алгоритмы сканирования и обхода Лекция 3

Алгоритм сканирования графа Input: Орграф (граф) G и вершина s. Output: Множество R вершин, достижимых из s, и множество T E(G) такое, что (R,T) ордерево с корнем в s (дерево). 1) Set R := {s}, Q := {s} and T := ø. 2) If Q = ø then stop, else выбрать v Q. 3) Выбрать w V(G) \R с e=(v,w) E(G). If нет такой w then Q := Q\{v} и go to 2. 4)Set R := R {w}, Q := Q {w} и T := T {e}. Go to 2.

Связность Предложение 3.1 Алгоритм сканирования графа находит решение.

Доказательство (для орграфа) По построению (R,T) ордерево с корнем в s. Предположим, что существует w V(G)\R, достижимая из s. Пусть P s-w-путь из s в w, и (x,y) дуга в P, такая что x R и y R. Так как x была добавлена в R, то она была добавлена в Q, на каком-то шаге алгоритма. Алгоритм не остановится пока не удалит x из Q. По шагу 3 это возможно только если нет дуги (x,y) с y R.

Матрица инцидентности Матрицей инцидентности графа G называется матрица A=( a v,e ) v V(G),e E(G), где Матрицей инцидентности орграфа G называется матрица A=( a v,e ) v V(G),e E(G), где

Матрица смежности Матрица смежности простого графа G 0-1- матрица A=( a v,w ) v,w V(G) с a v,w =1 тогда и только тогда, когда (v,w) E(G). Матрица смежности удобна, когда граф плотный, то есть имеет Θ(n 2 ) ребер.

Разреженные графы (O(n) ребер) Список ребер с указанием его граничных точек. Сопоставим каждой вершине число от 1 до n. (2m + 1)log n = O(m log n)

Лист смежности Сопоставим каждой вершине список ее инцидентных ребер. Для орграфа сопоставим каждой вершине два списка: список входящих в нее ребер и список исходящих из нее ребер. Такая структура данных называется листом смежности. Для прямого доступа к списку каждой вершины заведем указатели на начало списка (2n log m) O(m log n + n log m)

Время работы алгоритма сканирования графа Предложение 3.2 Алгоритм сканирования графа требует O(m+n) элементарных операций. Связные компоненты графа могут быть найдены за линейное время.

Алгоритм сканирования графа Input: Орграф (граф) G и вершина s. Output: Множество R вершин, достижимых из s, и множество T E(G) такое, что (R,T) ордерево с корнем в s (дерево). 1) Set R := {s}, Q := {s} and T := ø. 2) If Q = ø then stop, else выбрать v Q. 3) Выбрать w V(G)\R с e=(v,w) E(G). If нет такой w then Q := Q\{v} и go to 2. 4)Set R := R {w}, Q := Q {w} и T := T {e}. Go to 2.

Поиск ? В каком порядке выбирать вершины на шаге 3 ? Поиск в глубину (DFS-процедура) Выбираем v Q, последнюю из добавленных в Q. Другими словами, Q рассматривается как LIFO-стек (последний зашел, первый вышел). Поиск в ширину (BFS-процедура) Выбираем v Q, первую из добавленных в Q. Здесь Q рассматривается как FIFO-очередь (первый зашел, первый вышел). Дерево (R,T) построенное DFS -процедурой (resp. BFS - процедурой ) называется DFS-дерево (resp. BFS-дерево).

BFS-дерево Предложение 3.3 BFS-дерево содержит кратчайший путь из s к каждой вершине, достижимой из s. Величина dist G (s,v) для всех v V(G) может быть определена в линейное время.

Алгоритм сканирования графа-BFS Input: Орграф (граф) G и вершина s. Output: Множество R вершин, достижимых из s, и множество T E(G) такое, что (R,T) ордерево с корнем в s (дерево). 1) Set R := {s}, Q := {s} and T := ø, l(s):=0. 2) If Q = ø then stop, else выбрать v Q. 3) Выбрать w V(G) \R с e=(v,w) E(G). If нет такой w then Q := Q\{v} и go to 2. 4)Set R := R {w}, Q := Q {w} и T := T {e} l(w):= l(v) +1. Go to 2.

Доказательство Предложения 3.3 l(v) = dist (R,T) (s,v) Пусть v текущая просматриваемая вершина (выбранная на шаге 2). Не существует w R с l(w) > l(v) + 1. Предположим, что после завершения работы алгоритма существует w V(G) c dist (G) (s,w) < dist (R,T) (s,w). Пусть w лежит на кратчайшем расстоянии от s в G среди всех вершин с таким свойством. Пусть P кратчайший s-w-путь в G и e = {v,w} последнее ребро в P. Тогда dist (G) (s,v) = dist (R,T) (s,v) и e T. Кроме того, по предположению l(w) = dist (R,T) (s,w) > dist (G) (s,w) = =dist (G) (s,v) + 1= dist (R,T) (s,v) + 1 = l(v) + 1. Следовательно w R, когда v удаляется из Q. Противоречие шагу 3 алгоритма.

Алгоритм поиска сильно связных компонент Input: Орграф G. Output: Функция comp: V(G) N, указывающая принадлежность вершины к сильно связной компоненте. 1) Set R := ø. Set n:= 0. 2) For all v V(G) do: If v R then Visit1(v). 3) Set R := ø. Set K := 0. 4) For i :=|V(G)| down to 1 do: If - 1 (i) R then K := K+1 and Visit2( - 1 (i)).

Алгоритм поиска сильно связных компонент (2) Visit1(v) 1) Set R := R {v}. 2) For all w V(G) \ R с (v,w) E(G) do Visit1(w). 3) Set n := n +1, (v) := n и - 1 (N) := v. Visit2(v) 1) Set R := R {v}. 2) For all w V(G) \ R с (w,v) E(G) do Visit2(w). 3) Set comp(v) := K.

Пример a b g c d e f a b (1) g c d e f a g c d (3) e (2) f a (6) b (1) g (5) c (7) d (3) e (2) f (4) a (6) b (1) g (5) c (7) d (3) e (2) f (4)

Сильная связность Теорема 3.4 Алгоритм поиска сильно связных компонент находит сильно связные компоненты в линейное время. a b g c d e f

Эйлеров граф Определение 3.5 Эйлеровым обходом в графе G называется замкнутый обход, содержащий все ребра. Граф G называется Эйлеровым если степень каждой вершины четна. Орграф G Эйлеров, если – v + v для всех v V(G). Теорема 3.6 (Эйлер [1736]) Граф G имеет Эйлеров обход тогда и только тогда, когда он связный и Эйлеров.

Алгоритм Эйлера Input: Связный Эйлеров граф G. Output: Эйлеров обход W в G. Выбрать произвольную v 1 V(G). Return W := Euler(G, v 1 ) Euler(G, v 1 ). 1) Set W := v 1 и x := v 1. 2) If X = then go to 4. Else пусть e X, скажем e = {x,y}. 3) Set W := W, e, y и x := y. Set E(G := E(G \{e } и go to 2. 4) Let v 1, e 1, v 2, e 2,…, v k, e k, v k+1 be the sequence W. For i := 1 to k do: Set W i := Euler(G, v i ). 5) Set W := W 1, e 1, W 2, e 2, …, W k, e k, v k+1. Return W

Алгоритм Эйлера(2) Теорема 3.7 Алгоритм Эйлера находит решение за O(m+n) элементарных операций, где n V(G) и m E(G)

Доказательство (индукция по |E(G)|) E(G) = ø (очевидно) Так как степени вершин четные, то v k+1 =x=v 1, когда выполняется шаг 4. W замкнутый обход. Пусть G граф G на этот момент. В G также степени всех вершин четны.

Биразбиение Биразбиением графа G называется разбиение множества вершин V(G)=A B так что подграфы индуцированные на A и B оба пустые. Граф называется двудольным, если для него существует биразбиение.

Теорема Кёнига Предложение 3.8 (König[1916]) Граф является двудольным тогда и только тогда, когда он не содержит циклов нечетной длины. Существует линейный алгоритм, который по данному графу находит либо его биразбиение, либо цикл нечетной длины.

Достаточность Пусть G связный. Выберем произвольную вершину s V(G). Применим поиск в ширину и найдем расстояние от s до остальных вершин. Пусть T будет полученное BFS-дерево. A := {v V(G): dist G (s, v) четно}. B := {v V(G): dist G (s, v) нечетно}. e={x,y} ребро в G[A] или в G[B]. x-y-путь в T вместе с e дают нечетный цикл. Таких ребер в G[A] и в G[B] нет! A B биразбиение, G двудольный.

Упражнение 3.1 Пусть G простой граф. Доказать, что G или его дополнение связно.

Упражнение 3.2 Доказать, что любой разрез в неориентированном графе является непересекающимся объединением минимальных разрезов

Упражнение 3.3 Дан граф или орграф G. Показать, что существует линейный алгоритм находящий цикл или показывающий, что его не существует.

Упражнение 3.4 Пусть G неориентированный граф, C цикл в нем, а D разрез. Показать, что |E(C)D| четно.