Лабораторная работа №4 ОТКДС (Задание к лабораторной работе)

Посмотреть архив целиком

4



Задание к лабораторной работе №4 (графы) по ОТКДС.


Часть I. Поиск Гамильтоного пути (ГП) в графе:


1. Для заданного графически ориентированного графа составить матрицу смежности с единицами на главной диагонали (матрица достижимости за один шаг).

2. Найти ГП в графе, используя алгоритм Фаулкса.

3. Найти ГП в графе, используя алгоритм Робертса и Флореса (см. лекции) для начальной вершины, выбранной в п.2.

4. Найти ГП в графе- для начальной вершины, выбранной в п. 2, используя стандартную программу на ЭВМ.

5. Предложить словесное содержание задачи, отвечающей задан ному графу.


Часть П. Определение связности графа:


1. Для заданного с помощью матрицы смежности неориентированного графа найти связные компоненты, используя алгоритм Фаулкса.

2. Представить заданный граф графически и предложить словесное содержание задачи, отвечающей указанному графу.

3. Найти связные компоненты в графе, используя стандартную программу на ЭВМ.


Часть III. Поиск Эйлерогопуги (ЭП) в графе.


1. Для заданного графически неориентированного графа составить матрицу смежности с единицами на главной диагонали (матрица достижимости за один шаг).

2. Найти ЭП в графе, используя алгоритм, приведенный в описании лаб.работ.

3. Найти ЭП в графе для начальной вершины, выбранной в п. 2,используя стандартную программу на ЭВМ.

4. Предложить словесное содержание задачи, отвечающей заданному графу.


Случайные файлы

Файл
Kursovik.doc
4992-1.rtf
22052-1.rtf
11030-1.rtf
138028.rtf