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