Для студентов МАИ по предмету Основы теории конечных дискретных систем (ОТКДС)Лабораторная работа №4 ОТКДСЛабораторная работа №4 ОТКДС
2015-11-202015-11-20СтудИзба
Лабораторная работа: Лабораторная работа №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. Предложить словесное содержание задачи, отвечающей заданному графу.
Задание:
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. Предложить словесное содержание задачи, отвечающей заданному графу.
Характеристики лабораторной работы
Учебное заведение
Семестр
Просмотров
181
Скачиваний
3
Размер
174,36 Kb
Список файлов
- Лабораторная работа №4 ОТКДС
- ReadMe.txt 276 b
- Задание к лабораторной работе.doc 135 Kb
- Лаб_р_№4_на А4.doc 712,5 Kb
ReadMe
Файлы скачаны со студенческого портала для студенты "Baumanki.net"
Файлы представлены исключительно для ознакомления
Не забывайте, что Вы можете зарабатывать, выкладывая свои файлы на сайт
Оценивайте свой ВУЗ в различных голосованиях, в том числе в досье на преподавателей!

Хочешь зарабатывать на СтудИзбе больше 10к рублей в месяц? Записывайся на бесплатное наставничество от Максима Рубцова