Advertisement
Guest User

2 вопрос

a guest
Jun 20th, 2019
109
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.03 KB | None | 0 0
  1. 2 вопрос
  2. Граф – конечное множество вершин и множеств рёбер. Каждому ребру сопоставлены 2 вершины – концы ребра.
  3. Представление графов в памяти
  4. Обычно используются 2 типа матриц: 1) матрица смежности 2) весовая матрица
  5. Матрица смежности – матрица размером N*N, где каждый эл-т с индексами i,j является логическим значением и показывает есть ли дуга между i и j.
  6. Весовая матрица – квадратичная матрица, где каждый эл-т с индексами i,j равен весу ребра из вершины i в j.
  7. DFS
  8. Поиск в глубину – один из способов обхода графа, заключается в том, чтобы идти вглубь графа насколько это возможно. Алгоритм – рекурсивный. Перебираются все исходящие из рассматриваемой вершины ребра. Если ребро ведет в вершину, которая не была рассмотрена ранее, то запускаем алгоритм от этой нерассмотренной вершины, а после возвращаемся и продолжаем перебирать ребра, возврат происходит если в рассматриваемой вершине не осталось рёбер, которые ведут в нерассмотренную вершину.
  9. visited[] // хранит информацию о пройденных и не… вершинах
  10. function before( G[n]: graph){
  11. visited = array [n; false];
  12. }
  13. function dfs (int i){
  14. visited[i]=true;
  15. for v: (u,v) in G
  16. if not visited[v]
  17. dfs(v);
  18. }
  19. main(){
  20. for i = 1 to n
  21. if not visited[i]
  22. dfs(i);
  23. }
  24. Сложность O ( V + E), где V – множество вершин, E мн-во ребёр графа.
  25. Лемма о белом пути
  26. Не существует такого момента поиска в глубину, в которой бы существовало ребро из черной вершины в белую.
  27. Док-во: Пусть в процессе dfs нашлось ребро из черной вершины V в белую вершину U. Рассмотрим момент времени, когда был запущен dfs(V). В этот момент вершина V была перекрашена в серый, и не будет окрашена в черный пока не пройдет по всем вершинам белого цвета.
  28. Рёбра
  29. 1. Дуги дерева – рёбра, ведущие к вершинам, которые раньше не посещались.
  30. 2. Обратные дуги – рёбра, ведущие от потомков к предкам.
  31. 3. Прямые дуги - рёбра, ведущие от предков к собственным потомкам, не являющиеся дугами дерева
  32. 4. Поперечные дуги – рёбра, соединяющие вершины, не являющиеся ни предками, ни потомками
  33. Свойства времен входа и выхода
  34. Метки времени d[v] и f[v] являются целочисленными от 1 до 2|V|. Для каждой вершины v имеет место неравенство d[v]<f[v]. Вершина v будет белой до момента времени d[v], серой с d[v] до f[v] и чёрной после f[v].
  35. Проверка графа на ацикличность
  36. Произведём серию поисков в глубину в графе. Из каждой вершины, в которую мы ещё ни разу не приходили, запустим поиск в глубину, который при входе будет красить вершины в серый, а при выходе в чёрный. И если поиск в глубину из какой-то вершины пытается пойти в серую вершину, то это означает, что цикл обнаружен.
  37. Подсчет компонент связности
  38. Производится серия обходов: сначала запустим обход из первой вершины, и все вершины, которые он при этом обошёл – образуют первую компоненту связности. Затем найдём первую из оставшихся вершин, которые ещё не были посещены, и запустим обход из неё, найдя тем самым вторую компоненту связности, пока все вершины не станут помеченными. Асимптотика O(n+m)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement