Седжвик Р. — Фундаментальные алгоритмы на C++. Часть 5. Алгоритмы на графах
Обсудите книгу на
Нашли опечатку? Выделите ее мышкой и нажмите Ctrl+Enter
Название: Фундаментальные алгоритмы на C++. Часть 5. Алгоритмы на графах
Автор: Седжвик Р.
Аннотация:
Эта книга посвящена глубокому исследованию всех основополагающих концепций и алгоритмов, которые, несомненно, относятся к категории «вечных». Тщательным образом проштудировав их, вы получите знания, которые никогда не устареют и которыми вы будете пользоваться всегда.
Краткость, точность, выверенность, актуальность, изобилие примеров и учебных заданий - вот лишь небольшой перечень очевидных достоинств книги. Иллюстрация алгоритмов на одном из наиболее эффективных языков программирования С лишний раз подчеркивает их популярность и «вечность». Подробно рассматривается широчайший спектр фундаментальных алгоритмов на графах, в числе которых: поиск в орграфах, неорграфах и сетях; построение минимальных остовных деревьев и кратчайших путей; вычисление потоков в сетях с различными характеристиками. Большое внимание уделяется рабочим характеристикам алгоритмов, а также их математическому выводу.
Книгу можно использовать в качестве курса лекций (как студентами, так и преподавателями), справочного пособия или просто «романа», получая при этом ни с чем не сравнимое удовольствие.
Клика (clique)27; см. также «Подграф: полный» Контур (tour)25 Коридор (passage)94 Кратчайший путь (shortest path)132 Лабиринт (maze)94 Лес (forest)26 Лес (forest) DFS112 Лес (forest) остовный26 Математическое программирование338 Матрица178290 Матрица булева178 Матрица путей290 Матрица расстояний290 Матрица смежности графа2138 Метод99376 Метод аугментального пути376 Метод быстрого объединениясм. «Алгоритм: быстрого объединения» Метод быстрого поискасм. «Алгоритм: быстрого поиска» Метод выталкивания превосходящего потока402413 Метод поиска в глубину99 Метод Тремо100 Метод Уоршалла180 Метод Форда — Фалкерсона376; см. также «Метод: аугментального пути» Минимальное остовное дерево (MST)231 Модель линейного программирования (LP-модель)364 Мост (bridge)124 Мультиграф22 Мультиграф с петлями23 Набор соединений (connections)18 Набор элементов (items)18 Насыщенность графа27 Номер предпорядка (preorder number)110 Обращение орграфа163 Объединение двух графов27 Операция47146254321 Операция, decrease key (уменьшить ключ)270 Операция, edge existence (проверка наличия ребра)47 Операция, find edge (найти ребро)53 Операция, find minimum (поиск минимального ребра)254 Операция, remove edge (удалить ребро)47 Операция, remove the minimum (удалить минимальное ребро)254270 Операция, reweighting (повторное взвешивание)321350 Операция, update (обновления )146 Операция, арбитражная343 Орграф29157279; Орграф взвешенный279 Орграф, декомпозиция175 Орграф, обращение (reverse)162 Орграф, сильно связный (strongly connected)164 Ослабление287; см. также «Релаксация (relaxation)» Остаточная сеть (residual network)382 Отделимость123 Отношение (relation)190 Отношение (relation) рефлексивное190 Отношение (relation) симметричное190 Отношение (relation) эквивалентности191 ОЧЕРЕДЬ (QUEUE)141 Очередь (queue) FIFO132 Очередь (queue) LIFO132 Очередь (queue) с приоритетами146 Перекресток (intersection)94 Петля (self-loop)22 Планирование329 Планирование календарное329 Подграф23 Подграф максимальный связный26 Подграф полный27 Подграф, индуцированный подграф23 Поиск в глубину (DFS)699399169 Поиск в глубину (DFS) на матрице смежности169 Поиск в глубину (DFS) на списках смежных вершин169 Поиск в ширину (BFS)94132 Поиск на графе93104 Поиск простого пути70 Порядок192 Порядок полный192 Порядок частичный191 Потенциал (potential)445 Потенциал (potential), потенциалы вершин448 Поток (flow)368 Поток (flow) допустимый423436 Поток (flow) максимальный369419 Поток (flow) минимальной стоимости435437 Поток (flow) превосходящий (preflow)403 Поток (flow), допустимое остовное дерево449 Поток (flow), остаточная сеть (residual network)437 Поток (flow), остовное дерево максимального потока446 Поток (flow), стоимость потока (flow cost)435 Приложение составления расписаний194 Программирование332 Программирование библиотечное332 Программирование математическое338 Путь (path)2569132161165231384 Путь (path) аугментальный384 Путь (path) аугментальный кратчайший386399 Путь (path) аугментальный с максимальной пропускной способностью388397 Путь (path) аугментальный самый длинный389 Путь (path) Гамильтонов72 Путь (path) кратчайший132231281 Путь (path) кратчайший в ациклических сетях311 Путь (path) кратчайший из нескольких источников312 Путь (path) обходной341 Путь (path) ориентированный161 Путь (path) простой69 Путь (path) циклический25165 Путь (path) Эйлеров74 Путь (path), вес пути279 Путь (path), длина пути25 Путь (path), непересекающиеся пути26 Путь (path), непересекающиеся пути по вершинам26 Путь (path), непересекающиеся пути по ребрам26 Ребро23244379 Ребро инцидентно (incident on)23 Ребро ориентированные ребра29 Ребро случайное59 Ребро, пересекающее ребро (crossing edge)244379 Ребро, реберная связность (edge connectivity)130 Релаксация (relaxation)287; см. также «Ослабление» Сведение325334336338 Сведение эффективное334 Свойство сечения244 Свойство цикличности245 Связность129 Связность вершинная129 Связность реберная130 Сеть (network)279382; Сеть (network) ациклическая312 Сеть (network) транспортная30366 Сеть (network) транспортная, со случайными потоками396 Сеть (network) Эвклидова319 Сеть (network), st-сеть368 Сеть (network), диаметр сети305 Сеть (network), остаточная сеть (residual network)382410437 Сеть (network), управление потоками в сети368 Сечение (cut) графа244379 Сечение (cut) графа минимальное379 Сечение (cut) графа, st-сечение379 Сильная связность (strong connectivity)212 Сортировка199 Сортировка топологическая194199 Сортировка топологическая обратная200 Список смежных вершин графа213844 Стандартная библиотека шаблонов (STL)33 Степень (degree) вершины23 Стоимость потока (flow cost)435 Схема BDD (binary decision diagram)196 Теорема378 Теорема декомпозиции потоков371 Теорема Куратовского85 Теорема Менгера130429