Методические указания. При проектировании различных систем часто приходится решать задачи, которые можно назвать задачами согласования и упорядочения

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

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