Екатеринбург: Уральский государственный университет им. А.М. Горького (УрГУ), 2008. – 152 с.Основой для данного учебного пособия послужили лекции, которые читались авторами для студентов математико-механического факультета Уральского государственного университета им. А. М. Горького, обучающихся по специальностям «Математика, прикладная математика», «Математика, компьютерные науки» и «Компьютерная безопасность».В книге приводятся алгоритмы дискретной оптимизации на графах и сетях. Материал, посвященный алгоритмам, содержит достаточно строгое их обоснование. Разумеется, при построении и анализе алгоритмов, используются основные теоретико-графовые понятия и факты. Подбор тем, поднятых в книге, во многом определен вкусами авторов. Нам хотелось представить семейство алгоритмов дискретной оптимизации, наиболее часто используемых программистами. Мы стремились привести главные достижения, не останавливаясь на мелочах и не углубляясь в детальный обзор результатов по обсуждаемым темам.Введение в алгоритмы.Алгоритмы и их сложность.Запись алгоритмов.Корневые и бинарные деревья.Сортировка массивов.Поиск в графе.Поиск в глубину.Алгоритм отыскания блоков и точек сочленения.Алгоритм отыскания компонент сильной связности в орграфе.Поиск в ширину.Алгоритм отыскания эйлеровой цепи в эйлеровом графе.Задача о минимальном остове.Пути в сетях.Постановка задачи.Общий случай. Алгоритм Форда-Беллмана.Случай неотрицательных весов. Алгоритм Дейкстры.Случай бесконтурной сети.Задача о максимальном пути и сетевые графики.Задача о maxmin-пути.Задача о кратчайших путях между всеми парами вершин.Задача о максимальном потоке.Основные понятия и результаты.Алгоритм Форда-Фалкерсона.Паросочетания в двудольных графах.Основные понятия.Задача о наибольшем паросочетании. Алгоритм Хопкрофта-Карпа. Задача о полном паросочетании. Алгоритм Куна.Задача о назначениях. Венгерский алгоритм.Задача коммивояжера.Основные понятия.Алгоритм отыскания гамильтоновых циклов.Алгоритмы решения задачи коммивояжера с гарантированной оценкой точности.Решение задачи коммивояжера методом ветвей и границ.