Вопросы для самоконтроля

1. Какой граф называется взвешенным?

2. Как определяется кратчайшая цепь в графе?

3. Что представляет собой алгоритм Форда?

4. Для чего используется алгоритм Форда?

5. Какова сложность алгоритма Форда?

6. На чем основан метод Дейкстры?

7. Для чего используется алгоритм Дейкстры?

8. Какова сложность алгоритма Дейкстры?

9. Как определяется последовательность прохождения вершин в кратчайшей цепи?

10. В каком случае алгоритмы Форда и Дейкстры не позволяют найти кратчайший по стоимости путь?

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

1. Задан произвольный взвешенный неориентированный граф: G = (X, U), X = 9; U = 20. Найдите кратчайшие пути между всеми вершинами заданного графа, используя метод Форда.

2. Запишите словесный алгоритм нахождения кратчайших путей в графе (по методу Форда).

3. Постройте структурную схему алгоритма Форда нахождения кратчайших путей в графе.

4. Задан произвольный взвешенный неориентированный граф: G = (X, U), X = 9; U = 20. Найдите кратчайшие пути между всеми вершинами заданного графа, используя метод Дейкстры.

5. Запишите словесный алгоритм нахождения кратчайших путей в графе ( по методу Дейкстры).

6. Постройте структурную схему алгоритма Дейкстры нахождения кратчайших в графе.

7. Приведите псевдокод алгоритма Форда.

8. Приведите псевдокод алгоритма Дейкстры.

9. Определите временную сложность алгоритма Форда. Проведите сравнительную оценку с алгоритмом Дейкстры по времени работы и объему занимаемой памяти.

10. Определите временную сложность алгоритма Дейкстры. Проведите сравнительную оценку с алгоритмом Форда по времени работы и объему занимаемой памяти.

Алгоритмы Форда и Дейкстры являются эффективным способом определения кратчайшей по стоимости цепи между двумя вершинами графа.

Математика ─ позволяет познавать многое в окружающем нас реальном мире и овладевать им.

М. Клайн

Глава 16. Специальные циклы и метрика графов

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

Цели

Освоив эту главу, студенты должны:

• знать определение и условия существования эйлерова цикла;

• уметь строить эйлеров цикл в графе;

• решать задачу построения гамильтонова цикла в графе с помощью алгоритма Робертса─Флореса;

• уметь строить гамильтонов цикл в графе алгебраическим методом;

• решать задачу коммивояжера с помощью алгоритма Хелда─Карпа;

• решать задачу коммивояжера геометрическим методом;

• иметь представление о метрике графа;

• знать, каким образом определяется расстояние между вершинами графа;

• уметь строить матрицу расстояний и матрицу геометрии;

• знать, каким образом определяется диаметр и центр графа;

• знать определение дерева и покрывающего дерева в графе;

• уметь строить кратчайшее покрывающее дерево в графе на основе метода Прима;

• уметь строить кратчайшее покрывающее дерево в графе на основе алгоритма Краскала;

• уметь строить кратчайшее покрывающее дерево Штейнера в графе, отображенном в координатную решетку.