Лабораторная работа: Лабораторная работа №4 ОТКДС

Цель работы: изучение алгоритмов согласования и упорядочения на графах; овла-дение навыками реализации их на ЭВМ.

Задание:
I. Поиск Гамильтоного пути (ГП) в графе.
1.1. Для заданного графически, ориентированного графа составить матрицу смеж-ности R с единицами на главной диагонали (матрица достижимости за один шаг).
1.2. Найти ГП в графе, используя алгоритм Фаулкса.
1.3. Найти ГП в графе, используя алгоритм Робертса и Флореса (см. лекции) для начальной вершины, выбранной в п. 1.2.
1.4. Найти ГП в графе для начальной вершины, выбранной в п. 1.2, используя стандартную программу на ЭВМ, сравнить результаты.
1.5. Предложить словесное содержание задачи, отвечающей задан-ному графу.

2. Определение связности графа.
2.1. Для заданного с помощью матрицы смежности неориентированного графа найти связные компоненты, используя алгоритм Фаулкса,
2.2. Представить заданный граф графически и предложить словесное содержание задачи, отвечающей указанному графу.
2.3. Найти связные компоненты в графе, используя стандартную программу на ЭВМ, сравнить результаты.

3. Поиск Эйлеровой линии (ЭЛ) в графе.
3.1. Для заданного графически, неориентированного графа составить матрицу смежности с единицами на главной диагонали (матрица достижимости за один шаг).
3.2. Найти ЭЛ в графе, используя алгоритм, приведенный в описании лабораторной работы.
3.3. Найти ЭЛ в графе для начальной вершины, выбранной в п. 3.2, используя стандартную программу на ЭВМ, сравнить результаты.
3.4. Предложить словесное содержание задачи, отвечающей заданному графу.