Содержание
- 2. Графы Способы представления графов в программах Обходы графа Содержание
- 3. Во многих задачах, встречающихся в компьютерных науках, математике, технических дисциплинах часто возникает необходимость наглядного представления отношений
- 4. Первая работа по теории графов, принадлежащая известному швейцарскому математику Л.Эйлеру, появилась в 1736г., связанная с решением
- 5. В настоящее время графы эффективно используются в теории планирования и управления, теории расписаний, социологии, экономике, биологии,
- 6. 1. Графы
- 7. Ориентированный граф определяется как пара (V, Е), где V – конечное множество, а Е – бинарное
- 8. На рисунке показан ориентированный граф с множеством вершин {1, 2, 3, 4, 5, 6}. Вершины изображены
- 9. В неориентированном графе G = (V, Е) множество рёбер Е состоит из неупорядоченных пар вершин: парами
- 10. Многие понятия параллельно определяются для ориентированных и неориентированных графов (с соответствующими изменениями). Про ребро (и, v)
- 11. Про ребро (u, v) неориентированного графа говорят, что оно инцидентно вершинам и и v. Например, на
- 12. Если в графе G имеется ребро (u, v), говорят, что вершина v смежна с вершиной и.
- 13. Граф G' = (V ', Е') называют подграфом графа G = (V, Е), если Е' ⊆
- 14. Степенью вершины в неориентированном графе называется число инцидентных ей рёбер. Например, для графа на рисунке степень
- 15. Путь длины k из вершины, u в вершину v определяется как последовательность вершин , в которой
- 16. Путь называется простым, если все вершины в нём различны. Например, на рисунке есть простой путь длины
- 17. Циклом в ориентированном графе называется путь, в котором начальная вершина совпадает с конечной и который содержит
- 18. Например, на рисунке пути , и представляют один и тот же цикл. Этот цикл является простым,
- 19. Ориентированный граф, не содержащий петель, называется простым. В неориентированном графе путь называется (простым) циклом, если k≥3,
- 20. Неориентированный граф называется связным, если для любой пары вершин существует путь из одной в другую. Подграф
- 21. Ориентированный граф называется сильно связным, если из любой его вершины достижима (по ориентированным путям) любая другая.
- 22. Два графа G = (V, Е) и G' = (V ', Е') называются изоморфными, если существует
- 23. На рисунке приведен пример двух изоморфных графов G и G' с множествами вершин V = {1,
- 24. Графы на рисунке ниже не изоморфны, хотя оба имеют по 5 вершин и по 7 рёбер.
- 25. Для любого неориентированного графа G можно рассмотреть его ориентированный вариант, заменив каждое неориентированное ребро {u, v}
- 26. Если задана функция F: V→M, то множество M называется множеством пометок, а граф – помеченным. Если
- 27. Некоторые виды графов имеют специальные названия. Полным графом называют неориентированный граф, содержащий все возможные рёбра для
- 28. Неориентированный граф (V, E) называют двудольным, если множество вершин V можно разбить на две части V1
- 29. Ациклический неориентированный граф называют лесом, а связный ациклический неориентированный граф называют деревом без выделенного корня. Определения
- 30. 2. Способы представления графов в программах
- 31. Представление в программе объектов математической модели – это важная составляющая программирования. Выбор наилучшего представления определяется требованиями
- 32. Есть два стандартных способа представить граф G = (V, E): как набор списков смежных вершин или
- 33. Первый обычно предпочтительнее, т.к. даёт более компактное представление для разреженных графов – тех, у которых |Е|
- 34. Рисунок – Два представления неориентированного графа: списки смежности, матрица смежности Способы представления графов
- 35. Способы представления графов Рисунок – Два представления ориентированного графа: списки смежности, матрица смежности
- 36. Представление графа G = (V, Е) в виде списков смежных вершин использует массив Adj из |V|
- 37. Для ориентированного графа сумма длин всех списков смежных вершин равна общему числу рёбер: ребру (u, v)
- 38. Списки смежных вершин удобны для хранения взвешенных графов, в которых каждому ребру приписан некоторый вещественный вес,
- 39. Недостаток представления графа списком смежности: если мы хотим узнать, есть ли в графе ребро из и
- 40. При использовании матрицы смежности мы нумеруем вершины графа (V, Е) числами 1, 2, ..., |V| и
- 41. Как и для списков смежных вершин, хранение весов не составляет проблемы: вес w(u, v) ребра (u,
- 42. При описании графа списком его ребер каждое ребро представляется парой инцидентных ему вершин. Это представление можно
- 43. Матрицей инцидентности называется матрица B= [bij], i = 1, 2, ..., n, j = 1, 2,
- 44. Матрица инцидентности однозначно определяет структуру графа (рисунок). В каждом столбце матрицы B ровно две единицы. Равных
- 45. Недостаток данного представления состоит в том, что требуется n×m единиц памяти, большинство из которых будет занято
- 46. 3. Обходы графа
- 47. Графы могут представлять собой что угодно – карту маршрута, схему, компьютерную сеть. Но порой возникает необходимость
- 48. При решении многих задач с использованием графов необходимо уметь обходить все вершины и ребра (дуги) графа.
- 49. При решении многих задач, касающихся графов, необходимы эффективные методы систематического обхода вершин и ребер графов. Обходя
- 50. Если при посещении вершины структура графа не меняется, то наиболее полезны два основные способа обхода: поиск
- 51. Этот алгоритм поиска в графе также называют волновым алгоритмом из-за того, что обход графа идет по
- 52. Алгоритм поиск в ширину может быть описан и так. Пусть задан граф G = (V, Е)
- 53. Алгоритм применим и к ориентированным, и к неориентированным графам. Название объясняется тем, что в процессе поиска
- 54. Для для определения вершин, которые ранее посещались, – массив Visited: сначала присвоить всем элементам массива Visited
- 55. Алгоритм поиска в ширину формально можно записать следующим образом: Поиск в ширину void WidthSearch(int v) {
- 56. Поиск в ширину do { Q.head = Q.head +1; Cur = Delayed[Q.Head]; for (каждой вершины y,
- 57. Поиск в ширину void main() { while (есть непомеченные вершины) { v = любая непомеченная вершина;
- 58. Функция поиска в ширину для графа с n вершинами, представленного матрицей смежности A: Поиск в ширину:
- 59. Поиск в ширину: программа while (Q.front { for (int i=0; i { if ((A[v][i]!=0) && (not
- 60. Поиск кратчайшего пути в невзвешенном графе. Поиск компонент связности в графе. Нахождения решения какой-либо задачи (игры)
- 61. Нахождение кратчайшего цикла в ориентированном невзвешенном графе: производим поиск в ширину из каждой вершины; как только
- 62. Найти все вершины, лежащие на каком-либо кратчайшем пути между заданной парой вершин. Найти кратчайший чётный путь
- 63. Поиск в ширину: пример Исходный граф на левом рисунке. На правом рисунке рядом с вершинами в
- 64. Поиск в глубину является обобщением метода обхода дерева в прямом порядке. Предположим, что есть ориентированный граф
- 65. Поиск в глубину начинается с выбора начальной вершины v графа G, и эта вершина помечается как
- 66. Этот метод обхода вершин орграфа называется поиском в глубину, т.к. поиск непосещенных вершин идет в направлении
- 67. Например, пусть x – последняя посещенная вершина. Для продолжения процесса выбирается какая-либо нерассмотренная дуга x →
- 68. Для определения вершин, которые ранее посещались, – массив Visited: сначала присвоить всем элементам массива Visited значение
- 69. Алгоритм поиска в глубину формально можно записать следующим образом: funcrion DepthSearch(int v) { Visited[v] = true;
- 70. Поиск в глубину: пример Поиск начинается с первой вершины. На левом рисунке приведен исходный граф, а
- 71. Возможны две реализации алгоритма поиска в глубину: одна в виде рекурсивной процедуры (слайд 76), другая –
- 72. Поиск в глубину: программа int Graph[n][n]; // матрица смежности графа bool Visited[n]; int stack[n]; // стек
- 73. Поиск в глубину: программа void DFS(Matrix Graph, int n, v) { int top = 0; cout
- 74. Поиск в глубину: программа if (flag) { // помещена в стек и посещена новая вершина i
- 75. Вызов нерекурсивной процедуры: for (i=0; i visited[i] = false; for (i=0; i if (visited[i] == false)
- 76. Рекурсивная процедура, реализующая алгоритм поиска в глубину: void DFS(int v) { // Массивы Graph и Visited
- 78. Скачать презентацию