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

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

1.1. Для заданного графически, ориентированного графа составить матрицу R ¹ достижимости не более чем за один шаг.

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

1.3. Найти ГП в графе, используя алгоритм Робертса и Флореса для начальной вершины, выбранной в п. 1.2.

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

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

2. Определение связности графа.

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

2.2. Представить заданный граф графически.

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

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

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

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

3.2. Найти ЭП в графе, используя алгоритм, приведенный ниже в методических указаниях.

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

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

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

4.1. Для заданного преподавателем графа найти матрицы достижимости L, и контрдостижимости Q.

4.2. Найти сильные компоненты графа. Составить конденсацию графа.

4.3. Предложить алгоритмы нахождения базового и доминирующего множеств в графе.

4.4. Найти с помощью предложенных алгоритмов базовое и доминирующие множества.

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

5. Составить отчет. Ответить на контрольные вопросы.