Задание к лабораторной работе (Лабораторная работа №4 ОТКДС)
Описание файла
Файл "Задание к лабораторной работе" внутри архива находится в папке "Лабораторная работа №4 ОТКДС". Документ из архива "Лабораторная работа №4 ОТКДС", который расположен в категории "". Всё это находится в предмете "основы теории конечных дискретных систем (откдс)" из 4 семестр, которые можно найти в файловом архиве МАИ. Не смотря на прямую связь этого архива с МАИ, его также можно найти и в других разделах. Архив можно найти в разделе "лабораторные работы", в предмете "откдс" в общих файлах.
Онлайн просмотр документа "Задание к лабораторной работе"
Текст из документа "Задание к лабораторной работе"
4
Задание к лабораторной работе №4 (графы) по ОТКДС.
Часть I. Поиск Гамильтоного пути (ГП) в графе:
1. Для заданного графически ориентированного графа составить матрицу смежности с единицами на главной диагонали (матрица достижимости за один шаг).
2. Найти ГП в графе, используя алгоритм Фаулкса.
3. Найти ГП в графе, используя алгоритм Робертса и Флореса (см. лекции) для начальной вершины, выбранной в п.2.
4. Найти ГП в графе- для начальной вершины, выбранной в п. 2, используя стандартную программу на ЭВМ.
5. Предложить словесное содержание задачи, отвечающей задан ному графу.
Часть П. Определение связности графа:
1. Для заданного с помощью матрицы смежности неориентированного графа найти связные компоненты, используя алгоритм Фаулкса.
2. Представить заданный граф графически и предложить словесное содержание задачи, отвечающей указанному графу.
3. Найти связные компоненты в графе, используя стандартную программу на ЭВМ.
Часть III. Поиск Эйлерогопуги (ЭП) в графе.
1. Для заданного графически неориентированного графа составить матрицу смежности с единицами на главной диагонали (матрица достижимости за один шаг).
2. Найти ЭП в графе, используя алгоритм, приведенный в описании лаб.работ.
3. Найти ЭП в графе для начальной вершины, выбранной в п. 2,используя стандартную программу на ЭВМ.
4. Предложить словесное содержание задачи, отвечающей заданному графу.