Для студентов МАИ по предмету Основы теории конечных дискретных систем (ОТКДС)Методичка для 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. Предложить словесное содержание задачи, отвечающей заданному графу.
Характеристики книги
Тип
Учебное заведение
Семестр
Просмотров
214
Скачиваний
5
Размер
64,26 Kb
Список файлов
- Методичка для 4 лабы по ОТКДС
- ReadMe.txt 276 b
- Лабораторная работа 4 ОТКДС.doc 733,5 Kb
ReadMe
Файлы скачаны со студенческого портала для студенты "Baumanki.net"
Файлы представлены исключительно для ознакомления
Не забывайте, что Вы можете зарабатывать, выкладывая свои файлы на сайт
Оценивайте свой ВУЗ в различных голосованиях, в том числе в досье на преподавателей!
Хочешь зарабатывать на СтудИзбе больше 10к рублей в месяц? Научу бесплатно!
Начать зарабатывать
Начать зарабатывать