Экстремальные задачи на графах

Description

Во многих случаях, отвлекаясь от физического смысла, можно изобразить некоторые черты объекта в виде схемы, отображающей его внутренние связи и не зависящей от природы объекта. Такие схемы в математике называются графами. Бинарные отношения описываются графами, которые являются фундаментальным понятием теоретической информатики. В книге приводятся основные понятия теории графов, излагается теория однородных потоков, теория решения линейной сетевой и двойственной к ней задач, излагается теория оптимальных неоднородных потоков и методы их построения, рассматриваются задачи на построение в графе путей, удовлетворяющих различным ограничениям, в частности, задача коммивояжера. Книга рассчитана на научных работников и лиц, занимающихся вопросами математического программирования и планирования. Экстремальные задачи на графах. Ермольев Ю.М., Мельник И.М. Киев: Наукова думка, 1968. 176 с. Оглавление Предисловие Глава I. Графы, сети, потоки в сетях § 1. Основные определения § 2. Однородные потоки в сетях. Условия существования § 3. Максимальный поток в сети § 4. Метод расстановки пометок § 5. Доказательство теоремы существования § 6. Обобщения § 7. Элементарные свойства графов § 8. Поток в сети без пропускных способностей § 9. Неоднородные потоки в сетях Глава II. Линейная сетевая задача § 1. Постановка задачи § 2. Эквивалентное преобразование. Условия оптимальности § 3. Метод потенциалов § 4. Двойственная задача § 5. Транспортная задача, задача о поставщике § 6. Задача о максимальном потоке § 7. Задача о кратчайшем пути § 8. Комбинированный метод (метод Форда— Фалкерсона) § 9. Другие алгоритмы § 10. Решение задачи о кратчайшем пути §11. Задача об оптимальном потоке с двусторонними ограничениями. Пропускные способности вершин § 12. Мультисети. Модель взаимодействия различных видов транспорта Глава III. Нелинейная сетевая задача § 1. Задачи о размещении производства § 2. Условия оптимальности § 3. Распределение тока в электрических цепях. Гидравлический расчет сетей § 4. Метод взаимных корреспонденций § 5. Метод потенциалов § 6. Комбинированный метод § 7. Обоснование алгоритма § 8. Двойственный градиентный метод § 9. Задача о реконструкции сетей. Обучение смежным профессиям § 10. Нестационарная сетевая задача. Перераспределение интенсивностей в минимальное время Глава IV. Неоднородные потоки в сетях § 1. Многопродуктовые транспортные задачи, проблема развития сетей и размещения предприятий. Задача составления расписаний § 2. Необходимые и достаточные условия оптимальности. Игра р лиц § 3. Метод потенциалов. Общие замечания § 4. Линейная неоднородная сетевая задача § 5. Двойственный градиентный метод § 6. Метод линеаризации § 7. Метод разложения на однородные задачи § 8. Практические приложения, задача параметрического программирования Глава V. Кратчайшие допустимые пути § 1. Очередность проведения операций, составление расписаний, раскрой материалов (примеры) § 2. Постановка задачи и методы ее решения § 3. Обоснование и упрощение § 4. Обобщенная задача о кратчайшем пути § 5. Обобщенная задача коммивояжера § 6. Задача о времени пребывания. Управление дискретными системами § 7. Задача дискретного программирования § 8. Решение задачи об экспертах. Методы случайного поиска § 9. Графы со случайными связями. Общие замечания Библиографические указания Литература