Глава 1. Основные свойства ориентированных графов
§ 1. Основные понятия ориентированных графов
§ 2. Эйлеровы и гамильтоновы контуры
§ 3. Сильно связные графы
§ 4. Порядковая функция и функция Гранди орграфа
§ 5. Внутренняя и внешняя устойчивость орграфа
§ 6. Теоремы о ядрах орграфа
§ 7. Задачи и упражнения
Глава 2. Основные свойства неориентированных графов
§ 1. Основные понятия теории неориентированных графов
§ 2. Хроматическое число графа
§ 3. Цикломатическое число графа
§ 4. Эйлеровы графы
§ 5. Планарные графы
§ 6. Задачи и упражнения
Глава 3. Деревья
§ 1. Основные свойства деревьев
§ 2. Построение остовного дерева минимального веса
§ 3. Задачи и упражнения
Глава 4. Построение кратчайших путей в ориентированном графе
§ 1. Алгоритм поиска кратчайшего пути в орграфе с неотрицательными весами
§ 2. Алгоритм поиска кратчайших путей между всеми парами вершин орграфа для произвольной матрицы весов
§ 3. Задачи и упражнения
Глава 5. Оптимальные потоки в орграфах
§ 1. Основные определения. Построение максимального потока и минимального
разреза
§ 2. Построение заданного потока минимальной стоимости. Теорема о потоке минимальной стоимости
§ 3. Задачи и упражнения
Глава 6. Задача коммивояжера
§ 1. Поиск с возвращением. Метод ветвей и границ
§ 2. Алгоритм решения задачи коммивояжера методом ветвей и границ
§ 3. Пример решения задачи коммивояжера алгоритмом Литтла
§ 4. Метод динамического программирования
§ 5. Задачи и упражнения
Глава 7. Сложность алгоритмов оптимизации
§ 1. Алгоритмы и сложность
§ 2. Понятие о NP-полных задачах
§ 3. Задачи распознавания. Языки и кодирование
§ 4. Детерминированные машины Тьюринга и класс Р
§ 5. Недетерминированные машины Тьюринга и класс NP
§ 6. Соотношение между классами Р и NP
§ 7. Полиномиальная сводимость и NP-полные задачи
§ 8. Теорема Кука
§ 9. Метод сужения задачи для доказательства NP-полноты
§ 10. Задачи и упражнения
Глава 8. Приближенные алгоритмы оптимизации
§ 1. Оценки погрешности приближенных алгоритмов
§ 2. Приближенный алгоритм решения задачи коммивояжера. Алгоритм дерева
§ 3. Приближенные алгоритмы для задачи о рюкзаке
§ 4. Задачи и упражнения
Глава 9. Генетические алгоритмы
§ 1. Общая характеристика методов поиска решений оптимизационных задач
§ 2. Структура генетического алгоритма
§ 3. Пример генетического алгоритма
§ 4. Гипотеза "строительных блоков"
§ 5. Генетический алгоритм для задачи коммивояжера