Содержание
- 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. Нахождение маршрутов Длина 1 a1a a2b b2a b3c b4c c3b c4b Длина 2 a1a1a a1a2b a2b2a
- 12. Число маршрутов
- 13. Число различных маршрутов длины 2 из вершины xi в вершину xj через вершину xk есть Далее
- 14. Пример Для орграфов изменяется только матрица R.
- 15. c
- 16. Достижимость
- 17. Ориентированные маршруты Понятие маршрута можно обобщить на случай ориентированных графов. Ориентированная цепь (орцепь) часто называется путем
- 18. 2.2. Компоненты связности
- 19. Компоненты и бикомпоненты
- 20. Отношение «быть в одной компоненте » для ребер – эквивалентность, как и для вершин.
- 21. Для ориентированных графов
- 22. Множество вершин, достижимых из вершины x, обозначим Д(x). Теорема Вершины x и y взаимодостижимы тогда и
- 25. Фрагмент программы выглядит так: Пример (компоненты) 1 2 3 4 5 6 (**)
- 27. Пример (бикомпоненты, матрица достижимости) 1 2 3 5 4
- 28. Фрагмент программы: for k=1 to n for i=1 to n (***) for j=1 to n {r[i,j]:=r[i,j]∨r[i,k]
- 29. Ахо А., Хопкрофт Д., Ульман Д. (стр. 194-195) Структуры данных и алгоритмы. : Пер. с англ.
- 30. Пример (алгоритм Уоршалла)
- 31. Warshall Stephen (1935 – 2006) https://en.wikipedia.org/wiki/Stephen_Warshall Warshall carried out research and development in operating systems, compiler
- 32. 2.3. Кратчайшие цепи
- 33. Волновой алгоритм
- 35. 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2
- 36. Взвешенный граф
- 37. Пример
- 38. Алгоритм Беллмана - Форда
- 41. +
- 42. 0a ∞a ∞a 10 a ∞a ∞a ∞a 1 a 17b 12b 3 d 9 d
- 43. Если метка у вершины не меняется, клетка в следующей строке данного столбца не заполняется. Заключительные метки
- 44. В таком представлении алгоритм Беллмана — Форда более пригоден для «ручного» исполнения. Пусть вершины пронумерованы V={1,2,…,n}
- 45. Пример 1 2 3 4 ⊗ =
- 46. БЕЛЛМАН, Ричард (1920- 1984) – «отец «динамического программирования» - американский математик. Опубликовал 619 статей и 39
- 47. Алгоритм Дейкстры
- 50. 0a ∞a ∞a ∞a ∞a ∞a 10a 1a 3d 9d 7d 5b 8e 14e 13c
- 51. Иллюстрация работы алгоритма Дейкстры
- 52. в
- 53. Обобщения 1. Алгоритмы Беллмана – Форда и Дейкстры легко распространяются на случай ориентированных (частично ориентированных) графов,
- 54. ДЕЙКСТРА, Эдсгер (Edsger Dijkstra, 1930-2002). Нидерландский учёный, труды которого оказали большое влияние на развитие информатики; один
- 55. Алгоритм Флойда Замечание. В алгоритме Флойда, так же как и в алгоритме Беллмана – Форда, нет
- 56. for i=1 to n for j=1 to n p[i,j]:=i; Инициализация Основной цикл Алгоритм работает «на месте»:
- 57. Фрагмент программы: for k=1 to n for i=1 to n for j=1 to n { s:=c[i,k]+c[k,j];
- 58. 4 4
- 59. 4 4
- 60. -1 4 4
- 61. Замечание. Алгоритмы Беллмана – Форда и Флойда работают кор- ректно, если в графе нет циклов отрицательной
- 63. ФЛОЙД, Роберт В (Robert W Floyd, 1936 – 2001) — американский учёный в области теории вычислительных
- 65. Скачать презентацию