Методические указания. Цель работы: изучение алгоритмов согласования и упорядочения на графах

Работа № 4. АЛГОРИТМЫ СОГЛАСОВАНИЯ И УПОРЯДОЧЕНИЯ НА ГРАФАХ И ИХ РЕАЛИЗАЦИЯ НА ЭВМ

Цель работы: изучение алгоритмов согласования и упорядочения на графах.

Задание

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. Составить отчет. Ответить на контрольные вопросы.

При проектировании различных систем часто приходится решать задачи, которые можно назвать задачами согласования и упорядочения. Такие задачи, в частности, возникают при планировании работы цехов и предприятий, выпускающих широкую номенклатуру продукции с использованием в производственном процессе различных комбинаций станков и другого оборудования. Даже еслирассматривается всего одна единица оборудования, на которой выполняются различные работы, задача определения порядка выполнения работ является часто довольно сложной. Аналогичные проблемы, возникают при определении очередности решения задач на ЭВМ или порядка доставки груза многим потребителям при наличии одной транспортной единицы; при определении наличия взаимосвязей между группами объектов в сложной информационной системе; при определении порядка регламентных проверок исправности всех каналов связи между звеньями какой-нибудь достаточно сложной системы, обслуживаемой одной ремонтной единицей; при определении подчиненности одних элементов системы другим, возможности передачи управляющих воздействий, определения совокупности пунктов управления, из которых возможна передача команд ко всем элементам сложной системы и т.д.

Решение многих из них эффективно сводятся к решению известных задач с использованием аппарата теории графов, в частности, таких как поиск гамильтонова пути в графе, определение связности графа, поиск эйлерового пути в графе, определение сильных компонент, базового и доминирующих множеств в графе и других.

Дата добавления: 2017-01-13