Прикладные аспекты теории графов

Авторы: Печенкин В.В., Королёв М.С., Дороднова Л.В., Каликинская Е.Ю.

Издательство: Саратовский государственный технический университет имени Ю.А. Гагарина, ЭБС АСВ

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