Алгоритмы сканирования и обхода Лекция 3. Алгоритм сканирования графа Input: Орграф (граф) G и вершина s. Output: Множество R вершин, достижимых из s, - презентация

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

2 Алгоритм сканирования графа 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 Связность Предложение 3.1 Алгоритм сканирования графа находит решение.

4 Доказательство (для орграфа) По построению (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.

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

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

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

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

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

10 Алгоритм сканирования графа 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.

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

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

13 Алгоритм сканирования графа-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.

14 Доказательство Предложения 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 алгоритма.

15 Алгоритм поиска сильно связных компонент 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)).

16 Алгоритм поиска сильно связных компонент (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.

17 Пример 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)

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

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

20 Алгоритм Эйлера 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

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

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

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

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

25 Достаточность Пусть 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 двудольный.

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

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

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

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