Для студентов МАИ по предмету Основы теории конечных дискретных систем (ОТКДС)Задание для 4 лабораторной ОТКДСЗадание для 4 лабораторной ОТКДС
2015-11-202015-11-20СтудИзба
Лабораторная работа: Задание для 4 лабораторной ОТКДС
Описание
Задание к лабораторной работе №4 (графы) по ОТКДС в качестве примера:
Часть I. Поиск Гамильтоного пути (ГП) в графе:
1. Для заданного графически ориентированного графа составить матрицу смежности с единицами на главной диагонали (матрица достижимости за один шаг).
2. Найти ГП в графе, используя алгоритм Фаулкса.
3. Найти ГП в графе, используя алгоритм Робертса и Флореса (см. лекции) для начальной вершины, выбранной в п.2.
4. Найти ГП в графе- для начальной вершины, выбранной в п. 2, используя стандартную программу на ЭВМ.
5. Предложить словесное содержание задачи, отвечающей задан ному графу.
Часть П. Определение связности графа:
1. Для заданного с помощью матрицы смежности неориентированного графа найти связные компоненты, используя алгоритм Фаулкса.
2. Представить заданный граф графически и предложить словесное содержание задачи, отвечающей указанному графу.
3. Найти связные компоненты в графе, используя стандартную программу на ЭВМ.
Часть III. Поиск Эйлерогопуги (ЭП) в графе.
1. Для заданного графически неориентированного графа составить матрицу смежности с единицами на главной диагонали (матрица достижимости за один шаг).
2. Найти ЭП в графе, используя алгоритм, приведенный в описании лаб.работ.
3. Найти ЭП в графе для начальной вершины, выбранной в п. 2,используя стандартную программу на ЭВМ.
4. Предложить словесное содержание задачи, отвечающей заданному графу.
Часть I. Поиск Гамильтоного пути (ГП) в графе:
1. Для заданного графически ориентированного графа составить матрицу смежности с единицами на главной диагонали (матрица достижимости за один шаг).
2. Найти ГП в графе, используя алгоритм Фаулкса.
3. Найти ГП в графе, используя алгоритм Робертса и Флореса (см. лекции) для начальной вершины, выбранной в п.2.
4. Найти ГП в графе- для начальной вершины, выбранной в п. 2, используя стандартную программу на ЭВМ.
5. Предложить словесное содержание задачи, отвечающей задан ному графу.
Часть П. Определение связности графа:
1. Для заданного с помощью матрицы смежности неориентированного графа найти связные компоненты, используя алгоритм Фаулкса.
2. Представить заданный граф графически и предложить словесное содержание задачи, отвечающей указанному графу.
3. Найти связные компоненты в графе, используя стандартную программу на ЭВМ.
Часть III. Поиск Эйлерогопуги (ЭП) в графе.
1. Для заданного графически неориентированного графа составить матрицу смежности с единицами на главной диагонали (матрица достижимости за один шаг).
2. Найти ЭП в графе, используя алгоритм, приведенный в описании лаб.работ.
3. Найти ЭП в графе для начальной вершины, выбранной в п. 2,используя стандартную программу на ЭВМ.
4. Предложить словесное содержание задачи, отвечающей заданному графу.
Характеристики лабораторной работы
Учебное заведение
МАИСеместр
Просмотров
135
Размер
224,93 Kb
Список файлов
![Картинка-подпись](https://s.studizba.com/z.php?f=/uploads/fotos/podpt_2_43798.png&w=1632&h=400&t=1")
Зарабатывай на студизбе! Просто выкладывай то, что так и так делаешь для своей учёбы: ДЗ, шпаргалки, решённые задачи и всё, что тебе пригодилось.
Начать зарабатывать
Начать зарабатывать
zzyxel
20 ноября 2015 в 15:40
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
