Составители:
69
Проверочная работа «Теория графов». Вариант 2
1 а)
Чем отличается цикл и путь Гамильтона?
_________________________________________________________________
_________________________________________________________________
_________________________________________________________________
1 б) Найдите гамильтонов цикл, если он существует, для каждого из
приведенных ниже графов.
1 в) Найдите гамильтонов путь, если он существует, для каждого из
приведенных ниже графов.
2 а) Запишите своими словами теорему, на которой основывается алгоритм
Дейкстры.
_________________________________________________________________
_________________________________________________________________
_________________________________________________________________
2 б) Используя алгоритм Дейкстры (2) (матричный), найдите кратчайшее
расстояние от вершины 1 ко всем другим вершинам во взвешенном графе.
________
________
________
________
________
________
________
________
8
7
6
5
4
3
2
1
ij
D
D – матрица расстояний, a – массив меток рассмотрения вершин, b –
массив текущих расстояний от начальной вершины, c – массив номеров
предпоследних вершин.
Страницы
- « первая
- ‹ предыдущая
- …
- 67
- 68
- 69
- 70
- 71
- …
- следующая ›
- последняя »
