Дискретная математика. Комбинаторная оптимизация на графах

Купить бумажную книгу и читать

Название: Дискретная математика. Комбинаторная оптимизация на графах

Автор: Галкина В. А.

Издательство: Гелиос АРБ

Год: 2003

Формат: djvu

Размер: 1,52 Мб (+3%)

В учебном пособии систематически излагается материал, входящий в федеральный компонент дисциплины «Дискретная математика» Государственных образовательных стандартов группы специальностей «Информационная безопасность». Рассмотрены основы теории графов, основные постановки и методы решения оптимизационных задач на графах, Особое внимание уделено вопросам построения алгоритмов приближенного решения оптимизационных задач и оценкам сложности.

Для студентов и аспирантов, изучающих курсы дискретной математики в технических университетах, всех, интересующихся алгоритмами решения оптимизационных задач на графах.

Содержание

Глава 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. Генетический алгоритм для задачи коммивояжера