Глава 6. Основы теории графов

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

Графы очень часто используются в приложениях, поскольку они возникают как модель при изучении многих объектов. Например, структура молекулы является графом, в котором вершинами служат атомы, а ребрами – валентные связи. Блок-схема алгоритма представляет собой орграф, в котором вершинами являются отдельные операторы, а дуги указывают переходы между ними. Другие примеры графов: узлы и соединения в электрической цепи, схема дорог, множество предприятий с указанием двухсторонних связей между ними, группа людей с указанием их психологической совместимости, структура управления с указанием объектов и их подчиненности друг другу и т.д.

В полном объеме теория графов представляется собой курс, для изучения которого при наличии базовой математической подготовки потребуется несколько семестров, а для глубокого понимания - несколько лет вдумчивой и целеустремленной работы.

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

140