Э. Майника - Алгоритмы оптимизации на сетях и графах (1981) (1162193)
Текст из файла
Э.МайникаАЛГОРИТМЫ ОПТИМИЗАЦИИ НА СЕТЯХ И ГРАФАХМ.: Мир, 1981, 324 стр.Предисловие редактора переводаПредисловиеГлава 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. Задача почтальона для ориентированного графа5799111521222323304041424251637781838484911001111221461661701711711751892012162182192192222276.4. Задача почтальона для смешанного графаУпражненияЛитератураГлава 7. Задача коммивояжера7.1.
Формулировка и некоторые свойства решений задачи коммивояжера7.2. Условия существования гамильтонова контура7.3. Нижние границы7.4. Методы решения задачи коммивояжераУпражненияЛитератураГлава 8. Задачи размещения8.1. Введение8.2. Задачи поиска центра8.3. Задачи поиска медиан8.4. ОбобщенияУпражненияЛитератураГлава 9. Сетевые графика9.1. Метод критического пути (МКП)9.2. Определение длительности выполнения операции из условияобеспечения минимальной стоимости 3029.3. Обобщенные сетевые графикиУпражненияЛитератураПредметный указательПредметный указательБазисное решение 20, 21Абсолютная медиана 272, 281Букет 25Абсолютный центр графа 272, 275Величина дефекта 116—118Алгебраическое направление теорииВенгерское дерево 181—183графов 10Вершина 10Алгоритм 11, 15- внешняя 180- Данцига 51, 57—60, 63, 249- внутренняя 180- - обобщенный 74—77- конечная 12- Дейкстры 44—49, 61—63, 81- концевая 25- дефекта 111, 113, 117—122, 304- насыщенная 203, 204- Джевелла 153- начальная 12- Флойда 53, 58, 61—63- ненасыщенная 203, 205- - обобщенный 74—77- открытая 179- Форда 49—51, 61—63- паросочетания 179- - и Фалкерсона 92—101- пустая 203- Эдмондса 178, 189Вершинное число 105, 109, 151Анализ вычислительной сложностиВес дерева 2360—63231239240241241244251255262264265265273279287288289290290309315318319Взвешенное размещение 287Внутренняя точка 267Время прохождения 123Гамильтонов контур 241, 243, 244—264- - оптимальный 242, 244—264- цикл 250Главная абсолютная медиана 272,282- медиана 272, 280Главный абсолютный центр 272, 275,278- центр графа 272, 274, 275Граф 10- двудольный 175, 178- неориентированный 11- нечетный 222- связный 13, 14- сильно связный 244, 246- четный 221Дерево 13- кратчайших путей 45- минимальной стоимости 23- ориентированное 254- чередующееся 180Динамический поток 123—132Длина пути, 78- цепи 12Дуга 10- обратная 87, 136- порождающая спрос 147- промежуточная 86- прямая 87, 136- увеличивающая 85, 89- уменьшающая 85, 89Единица потока 84Задача коммивояжера 241- - общая 241- об узких местах 78- о Кенигсбергских мостах 9- - максимальном потоке 91, 92, 102- - паросочетания 11- - - максимальной мощности 173,175, 178- - - минимальной мощности 173- - - с максимальным весом 172, 175- - - - минимальным весом 173- - покрытии максимальноймощности 172- - - минимальной мощности 172, 175- - - с максимальным весом 173- - - - минимальным весом 173, 175- - потоке минимальной стоимости101, 113, 114, 147—149, 151,152- - путях с усилениями 79- поиска медиан 279—285- - центра 273—279- почтальона 9, 219—240- размещения 265—288Источник 84Компонент графа 13, 14- - сильно связный 245Контур 12, 33- простой 12, 247Коэффициент усиления дуги 79, 80,146Критическая операция 300Критический путь 300Лес 14- максимальный ориентированный31, 38, 39- минимальный 31Линейное программирование 15—21,92, 147- - двойственная задача 18- - прямая задача 18Маршрут 219- коммивояжера 241- - оптимальный 242, 243- почтальона 220, 222, 225Матрица графа 15- инциденции 15Медиана 266, 272, 279Метод ветвей и границ 256—259- критического пути 290—302- РЕКТ 301, 302- последовательного улучшениярешения 256, 260—264Модель Фалкерсона 302Неравенство треугольника 242, 243Обобщенная операция сложения 64- - сравнения 64Обратный поиск 67, 73Окрашивание ребер 24Оптимальная длина пути 65Оптимальный поток 155- путь 77Оптимизационное направлениетеории графов 9Оценка времени выполненияоперации 301Паросочетание 171—205- максимальное по мощности 171,183- минимальной мощности 172- с максимальным весом 172, 189Петля 12Подграф 13- порожденный 13Поедающий алгоритм 26, 40Покрывающее дерево 14, 23—29, 31,32Покрытие 171, 205—217Поток лексикографический 144- наипозднейшего отправления 140,143- - прибытия 139- наискорейшего отправления 140,141- - прибытия 132—143- с усилениями 146, 153Пропускная способность 84, 91, 95Прямой поиск 67, 73Путь 12, 42- кратчайший 42—59Разрез 14, 94- насыщенный 105, 130, 131- простой 14, 94Расстояние вершина — вершина 267- вершина — дуга 268- точка — вершина 267- точка — дуга 269Ребро 11Резерв времени независимый 299- - полный 298- - свободный 298, 299Решающий узел 310Свертка вектора 74Сетевой график 290, 293—315- - обобщенный 309—315Сеть 11, 85, 122- с усилениями 151, 152Симплекс-алгоритм 21Степень вершины 220- - внешняя 221- - внутренняя 221- дефектности дуги 116- захода 21- исхода 21Сток 84Теорема Гуйя-Ури 246Теория графов 9Увеличение потока 87- - максимальное 87, 88, 96Узкое место 97Уменьшение потока 87Уравнение сохранения потока 151,152Усиление дуги 146Условия дополняющей нежесткости18, 19, 107, 108, 120, 149- неотрицательности 17Функция расстояний 281, 282f-точка 267Целевая функция 16Центр графа 266, 272Цепь 12- взвешенная увеличивающаясячередующаяся 189- простая 12, 179- увеличивающаяся 88, 138, 139, 184- - чередующаяся 179- чередующаяся 178—180Цикл 12, 117- генерирующий 149, 150, 152- нечетный 179, 181, 184- поглощающий 150, 152- простой 179Чистый поток 86, 87, 116, 120Эйлеров маршрут 220, 228, 229, 231,232.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
