Плетнева Л.А., Плетнев А.Л., Леева М.А., Каграманова И.Г. Алгоритмы и теория графов

Учебное пособие. — М.: Московский автомобильно-дорожный государственный технический университет (МАДИ), 2021. — 120 с. — ISBN 978-5-7962-279-1.В учебном пособии изложены основные разделы теории графов и алгоритмы на дискретных структурах данных. Теоретический материал рассматривается на конкретных практических задачах и упражнениях. В приведенном списке литературы можно найти дополнительные сведения из теории, а также задачи для самостоятельного решения.
Учебное пособие предназначено для студентов обучающихся по направлениям подготовки бакалавров, магистров и аспирантов. Оно будет полезно практикующим программистам и специалистам в области дискретной математики.Введение.
Теоретическая часть.
Основные понятия и определения.
Смежность, инцидентность, степени.
Маршруты, пути.
Задача Эйлера.
Матричное задание графов, матрицы смежности, инцидентности.
Связность, компоненты связности.
Матрицы связности.
Выделение компонент связности.
Алгоритм определения числа компонент сильной связности орграфа.
Поиск путей (маршрутов) с минимальным числом дуг (ребер).
Алгоритм фронта волны.
Минимальные пути (маршруты) в нагруженных орграфах (графах).
Алгоритм Форда — Беллмана.
Внутренняя и внешняя устойчивость в графах.
Внутренняя устойчивость в ориентированных графах.
Внешняя устойчивость в ориентированных графах.
Метод Магу.
Ядра орграфа.
Деревья и леса.
Сетевые модели.
Основные понятия сетевого планирования и управления.
Параметры сетей и методы их расчета.
Временные параметры сетевых графиков.
Матричный метод расчета параметров сетевого графика.
Графический метод расчета параметров сетевого графика.
Расчет параметров сетевого графика методом потенциалов.
Табличный метод расчета параметров сетевого графика.
Сетевое планирование в условиях неопределенности.
Анализ и оптимизация сетевой модели.
Предварительный анализ сетевой модели.
Оптимизация сетевого графика по времени.
Оптимизация сетевого графика по трудовым ресурсам.
Оптимизация сетевого графика по материальным ресурсам.
Оптимизация сетевого графика по денежным ресурсам.
Управление производством работ по сетевым графикам.
Расчет параметров сетевой модели с помощью электронной таблицы Excel.
Задания для самостоятельной работы.
Список литературы.