Гданский И.И. Основы теории и алгоритмы на графах

Учебное пособие. — Москва: Инфра-М, 2022. — 206 с.В учебном пособии изложены основные теоретические положения теории графов, основные задачи, решаемые с использованием графовых структур, а также общие методы их решения и конкретные алгоритмы с оценками их сложности. Рассмотрено множество примеров, приведены вопросы для проверки уровня знаний и задачи для самостоятельного решения. Наряду с контрольными заданиями для проверки теоретической подготовки указаны варианты практических заданий на разработку программ по изучаемым разделам теории графов.
Соответствует требованиям федеральных государственных образовательных стандартов высшего образования последнего поколения.
Рассчитано на студентов бакалавриата и магистратуры, изучающих информационные технологии, для углубленной подготовки в области анализа и проектирования систем сложной структуры. Также пособие может быть полезно специалистам Iт-сферы при изучении алгоритмических аспектов теории графов.Основные виды графовых структур, их характеристики и способы задания. Задачи на графовых структурах.
Псевдографы, мультиграфы, графы . Маршруты, циклы.
Вопросы и задания для самопроверки.
Способы задания графов и орграфов. Гиперграфы.
Вопросы и задания для самопроверки.
Практические задачи.
Типы задач на графов ых структурах.
Общие методы, применяемые при решении задач на графовых структурах.
Полный перебор.
Динамическое программирование.
Эвристические методы.
Жадный алгоритм.
Метод ветвей и границ.
Линейное программирование.
Формальные методы.
Применение параллельных и распределенных алгоритмов.
Вопросы и задания для самопроверки.Свойства достижимости и связности. Покрытия графов. Реберные графы.
Свойства достижимости и связности у графов и орграфов.
Вопросы и задания для самопроверки.
Практические задачи.
Паросочетания и реберные покрытия графов.
Вопросы и задания для самопроверки.
Практические задачи.
Вершинные покрытия и независимые множества вершин.
Вопросы и задания для самопроверки.
Практические задачи.
Реберные графы.
Вопросы и задания для самопроверки.
Практические задачи.Основные типы графовых структур. Деревья.
Определение дерева. Его основные свойства.
Вопросы и задания для самопроверки.
Практические задачи.
Остовные деревья (каркасы) связных графов.
Вопросы и задания для самопроверки.
Практические задачи.
Однокорневые деревья. Их основные характеристики, классификация.
Вопросы и задания для самопроверки.
Двоичные (бинарные) деревья.
Логические уравнения и системы уравнений.
Логические задачи по идентификации свойств объектов.
Вопросы и задания для самопроверки.
Практические задачи.Основные типы графовых структур. Полные, двудольные графы, единичные кубы, сети.
Полные графы.
Вопросы и задания для самопроверки.
Практические задачи.
Двудольные графы.
Вопросы и задания для самопроверки.
Практические задачи.
Единичные n-мерные кубы.
Вопросы и задания для самопроверки.
Практические задачи.
Сети.
Моделирование транспортных систем. Потоки в сетях.
Моделирование управляющих схем.
Вопросы и задания для самопроверки.
Практические задачи.
Контрольные задания по теме «Общие характеристики и свойства графовых структур. Их основные типы».
Практические задачи по алгоритмизации и программированию по теме «Общие характеристики и свойства графовых структур. Их основные типы».Изоморфизм, гомеоморфизм, обходы графов.
Изменение структуры графов. Изоморфизм графов.
Вопросы и задания для самопроверки.
Практические задачи.
Подразбиения и гомеоморфизм графов.
Вопросы и задания для самопроверки.
Практические задачи.
Гамильтоновы цепи и циклы.
Вопросы и задания для самопроверки.
Практические задачи.
Эйлеровы цепи и циклы.
Вопросы и задания для самопроверки.
Практические задачи.Оптимальные пути во взвешенных графах.
Оптимальные маршруты во взвешенных графах.
Алгоритм Шимбелла.
Алгоритм Флойда - Уоршалла.
Вопросы и задания для самопроверки.
Практические задачи.
Алгоритм Дейкстры.
Вопр осы и задания для самопроверки.
Практические задачи.
Взвешенные графы с ребрам и отрицательного веса. Алгоритм Беллмана - Форда.
Графы с неотрицательными весами ребер . Базовый вариант алгоритма Беллмана - Форда.
Графы с отрицательными весами ребер. Модификации алгоритма Беллмана - Форда.
Точное решение задач и на графах с отрицательными весам и ребер с использованием метода ветвей и границ . Алгоритм исчерпывания вершин.
Вопросы и задания для самопроверки.
Практические задачи.Раскраски графов. Планарность графов.
Раскраски. Основные определения.
Вершинные раскраски. Оценки хроматических чисел графов.
Алгоритмы вершинной раскраски графов.
Вопросы и задания для самопроверки.
Практические задачи.
Реберные раскраски графов. Оценки реберных хроматических чисел.
Алгоритмы реберной раскраски графов.
Вопросы и задания для самопроверки.
Практические задачи.
Тотальные раскраски, их особенности. Оценки полных хромат ических чисел графов.
Алгоритмы тотальной раскраски графов.
Вопросы и задания для самопроверки.
Практические задачи.
Планарность графов.
Вопросы и задания для самопроверки.
Практические задачи.
Контрольные задания по теме «Изоморфизм и гомеоморфизм, раскраски и планарность графов».
Практические задачи по алгоритмизации и программированию по теме «Изоморфизм и гомеоморфизм, раскраски и планарность графов.
Библиографический список.