Филиппова А.С. Лекции по дисциплине Комбинаторные алгоритмы

Уфа: УГАТУ, 2010 г., 85 стр. Содержание:
Введение
Основные определения комбинаторики
Сеть. Кратчайшие пути. Алгоритм Дейкстры
Кратчайшие пути между всеми парами узлов. Алгоритм с тройственными операциями
Поиск остовного дерева в ширину и поиск в глубину. Алгоритмы Прима и Краскала (жадный) для поиска минимального остовного дерева
Проблема коммивояжера. Алгоритмы "ближайшего соседа" и "самой близкой вставки"
Сетевое планирование. Задача о кратчайшем сроке. Задача о критическом пути
Максимальные потоки. Теорема Форда и Фалкерсона
Метод нахождения максимального потока. Теорема о максимальных разрезах
Алгоритмы для нахождения максимального потока и минимального разреза
Потоки с минимальной стоимостью. Метод анализа и оценки проекта REPT-метод
Непересекающиеся цепи и разделяющие множества. Теорема Менгера
Максимальные и наибольшие паросочетания. Алгоритм выбора наибольшего сочетания в двудольном графе с матрицей двудольного графа
Задачи о назначении. Венгерский алгоритм
Классы задач в зависимости от их трудности. Полиномиальные, недетерминированные алгоритмы. Стандартные NP-полные задачи. Решение NP-полной задачи
Контрольные вопросы
Литература