Задания для самостоятельной работы к разд.3.3

1. Алгоритм 3 находит кратчайший путь из начальной вершины S в конечную вершину t. Измените алгоритм, чтобы находились кратчайшие пути из вершины S до всех оставшихся вершин графа.

2. Реализуйте и исследуйте на эффектвность алгоритм Дейкстры.

3. Узким местом пути называется кратчайшая из входящих в него дуг. Задача об узких местах пути - задача поиска такого пути между двумя вершинами, в котором длина кратчайшей дуги максимальна.

Измените алгоритм Дейкстры для решения задачи об узких местах пути.

Придумайте реальные задачи, сводящиеся к задаче об узких местах пути.

4. Сопоставим каждой дуге действительное число, называемое коэффициентом усиления дуги. Коэффициентом усиления пути называется величина произведения коэффициентов усиления всех дуг, составляющих данный путь. Задача о путях с усилением формулируется как задача нахождения такого пути между двумя вершинами, который дает наибольшую величину усиления.

Модифицируйте алгоритм Дейкстры для решения задачи о путях с усилением.

Придумайте реальные задачи, сводящиеся к задаче о путях с усилением.

5. Рассмотренный алгоритм Флойда вычисляет только длины кратчайших путей между каждой парой вершин. Доработайте алгоритм таким образом, чтобы сохранялась информация о самих кратчайших путях.

Вопросы для повторения

1. Определение неориентированного графа.
2. Понятие вершины графа.
3. Понятие ребра графа.
4. Понятие порядка графа.
5. Понятие отношения инцидентности.
6. Понятие отношения смежности.
7. Определение ориентированного графа.
8. Обобщение понятия "граф" (мультиграф, псевдограф).
9. Понятие смешанного графа.
10. Понятие взвешенного графа.
11. Определение цепи.
12. Определение пути.
13. Определение цикла.
14. Определение контура.
15. Определение связного графа.
16. Определение полного графа.
17. Определение ациклического графа.
18. Определение дерева.
19. Определение покрывающего дерева.
20. Понятие гиперграфа.
21. Понятие матрицы смежности.
22. Понятие матрицы инцидентности.
23. Понятие матрицы весов.
24. Способы хранения графов в памяти ЭВМ.
25. Алгоритм построения покрывающих деревьев (алгоритм Краскала).
26. Алгоритм нахождения всех покрывающих деревьев.
27. Поиск на графах (поиск в глубину и поиск в ширину).
28. Понятие сильной связности.
29. Понятие матрицы достижимости, контрдостижимости и взаимодостижимости.
30. Анализ сильной связности с помощью алгоритмов поиска на графах.
31. Понятие транзитивного замыкания.
32. Алгоритм нахождения транзитивного замыкания.
33. Анализ сильной связности с помощью алгоритма нахождения транзитивного замыкания.
34. Алгоритм нахождения кратчайшего пути (алгоритм Дейкстры).
35. Алгоритм нахождения кратчайших путей (алгоритм Флойда).