Содержание
- 2. 2.1. Маршруты, цепи, циклы
- 3. Маршруты
- 4. Цепи и циклы
- 5. Лемма. Всякий маршрут графа содержит хотя бы одну простую цепь, соединяющую ту же пару вершин. Доказательство
- 6. Пример Маршрут a 1 b 2 c 3 d 4 b 5 e содержит простую цепь
- 7. Если маршрут рассматривать с учетом ориентации ребер (может быть и по звеньям), то получим соответствующие определения:
- 8. Задачи о маршрутах В теории рассматривается ряд задач и алгоритмов определения свойств маршрутов: существование маршрутов заданной
- 9. Существование маршрутов Рассматривается неориентированный (маршрут не предполагает ориентации) униграф (важен лишь факт смежности вершин). Такой граф
- 10. и вершины xk и xj смежны. Для маршрутов других видов задаются соответствующие матрицы смежности.
- 11. Нахождение маршрутов Зададим граф общего вида тройками вида (x,v,y), где x,y∈V, v ∈E. Умножение отношений примет
- 12. Число маршрутов
- 13. Число различных маршрутов длины 2 из вершины xi в вершину xj через вершину xk есть Далее
- 14. Пример Для орграфов изменяется только матрица R.
- 15. c
- 16. Достижимость
- 17. Ориентированные маршруты Понятие маршрута можно обобщить на случай ориентированных графов. Ориентированная цепь (орцепь) часто называется путем
- 18. 2.2. Компоненты связности
- 19. Компоненты и бикомпоненты
- 20. Отношение «быть в одной компоненте » для ребер – эквивалентность, как и для вершин.
- 22. Для ориентированных графов
- 23. Множество вершин, достижимых из вершины x, обозначим Д(x). Теорема Вершины x и y взаимодостижимы тогда и
- 25. Алгоритм работает «на месте» -- матрица Rl+1 записывается на месте матрицы R.
- 26. Фрагмент программы выглядит так: Пример (для компонент) (**)
- 28. 1 2 3 5 4 Пример (бикомпоненты, матрица достижимости)
- 29. Фрагмент программы: for k=1 to n for i=1 to n (***) for j=1 to n {r[i,j]:=r[i,j]∨r[i,k]
- 30. Ахо А., Хопкрофт Д., Ульман Д. (стр. 194-195) Структуры данных и алгоритмы. : Пер. с англ.
- 31. Пример (алгоритм Уоршалла)
- 32. Warshall Stephen (1935 – 2006) https://en.wikipedia.org/wiki/Stephen_Warshall Warshall carried out research and development in operating systems, compiler
- 33. 2.3. Кратчайшие цепи
- 34. Волновой алгоритм
- 36. 0 1 2 3 3 4 4 5 6 7 Пример 1. Задача о Волке, Козе
- 38. https://www.youtube.com/watch?v=YDX-ohCVtxY
- 39. 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2
- 40. Взвешенный граф
- 41. Пример
- 42. Алгоритм Беллмана - Форда
- 45. +
- 46. 0a ∞b ∞c 10 a ∞f ∞d ∞e 1 a 17b 12b 3 d 9 d
- 47. Если метка у вершины не меняется, клетка в следующей строке данного столбца не заполняется. Заключительные метки
- 48. В таком представлении алгоритм Беллмана — Форда более пригоден для «ручного» исполнения. Пусть вершины пронумерованы V={1,2,…,n}
- 49. Пример 1 2 3 4 ⊗
- 50. БЕЛЛМАН, Ричард (1920- 1984) – «отец «динамического программирования» - американский математик. Опубликовал 619 статей и 39
- 51. Алгоритм Дейкстры
- 54. 0a ∞b ∞c ∞d ∞e ∞f 10a 1a 3d 9d 7d 5b 8e 14e 13c
- 55. Иллюстрация работы алгоритма Дейкстры
- 56. Обобщения 1. Алгоритмы Беллмана – Форда и Дейкстры легко распространяются на случай ориентированных (частично ориентированных) графов,
- 57. ДЕЙКСТРА, Эдсгер (Edsger Dijkstra; 1930-2002). Нидерландский учёный, труды которого оказали большое влияние на развитие информатики; один
- 58. Алгоритм Флойда Замечание. В алгоритме Флойда, так же как и в алгоритме Беллмана – Форда, нет
- 59. for i=1 to n for j=1 to n p[i,j]:=i; Инициализация Основной цикл Алгоритм работает «на месте»:
- 60. Фрагмент программы: for k=1 to n for i=1 to n for j=1 to n { s:=c[i,k]+c[k,j];
- 61. 4 4
- 62. 4 4
- 63. -1 4 4
- 64. Замечание. Алгоритмы Беллмана – Форда и Флойда работают кор- ректно, если в графе нет циклов отрицательной
- 66. Скачать презентацию