Наверх

Э.Майника, 1981 (Rus)
Алгоритмы оптимизации на сетях и графах

Книга Э.Майники - профессора Иллинойского университета (США) - посвящена дискретному программированию, которое широко используется для решения проблем оптимизации. Рассматриваются задачи почтальона, коммивояжера, управления проектами и размещений. Приводится количественная оценка времени сходимости описываемых алгоритмов, которые могут быть сравнительно легко запрограммированы и практически реализованы с помощью ЭВМ


ПРЕДИСЛОВИЕ

ГЛАВА 1. ВВЕДЕНИЕ В ТЕОРИЮ ГРАФОВ И СЕТЕЙ
  
1.1 Вводные замечания
   1.2 Некоторые понятия и определения
   1.3 Линейное программирование
Упражнения
Литература

ГЛАВА 2. АЛГОРИТМЫ ПОСТРОЕНИЯ ДЕРЕВА
  
2.1 Алгоритмы построения покрывающих деревьев
   2.2 Алгоритм построения максимального ориентированного леса
Упражнения
Литература

ГЛАВА 3. Алгоритмы поиска путей
  
3.1 Алгоритм поиска кратчайшего пути
   3.2 Алгоритмы поиска всех кратчайших путей
   3.3 Алгоритм поиска k кратчайших путей
   3.4 Поиск других оптимальных путей
Упражнения
Литература

ГЛАВА 4. ПОТОКОВЫЕ АЛГОРИТМЫ
  
4.1 Введение
   4.2 Алгоритм поиска максимального потока
   4.3 Алгоритм поиска потока минимальной стоимости
   4.4 Алгоритм дефекта
   4.5 Алгоритм поиска динамического потока
   4.6 Потоки с усилениями
Упражнения
Литература

ГЛАВА 5. АЛГОРИТМЫ ПОИСКА ПАРОСОЧЕТАНИЙ И ПОКРЫТИЙ
  
5.1 Введение
   5.2 Алгоритм решения задачи о паросочетании максимальной мощности
   5.3 Алгоритм выбора паросочетания с максимальным весом
   5.4 Алгоритм построения покрытия с минимальным весом
Упражнения
Литература

ГЛАВА 6. ЗАДАЧА ПОЧТАЛЬОНА
  
6.1 Введение
   6.2 Задача почтальона для неориентированного графа
   6.3 Задача почтальона для ориентированного графа
   6.4 Задача почтальона для смешанного графа
Упражнения
Литература

ГЛАВА 7. ЗАДАЧА КОММИВОЯЖЕРА
  
7.1 Формулировка и некоторые свойства решений задачи коммивояжера
   7.2 Условия существования гамильтонова контура
   7.3 Нижние границы
   7.4 Методы решения задачи коммивояжера
Упражнения
Литература

ГЛАВА 8. ЗАДАЧИ РАЗМЕЩЕНИЯ
  
8.1 Введение
   8.2 Задачи поиска центра
   8.3 Задач поиска медиан
   8.4 Обобщения
Упражнения
Литература

ГЛАВА 9. СЕТЕВЫЕ ГРАФИКИ
  
9.1 Метод критического пути (МКП)
   9.2 Определение длительности выполнения операций из условия обеспечения минимальной стоимости
   9.3 Обобщенные сетевые графики
Упражнения
Литература