Авторизация
Поиск по указателям
Седжвик Р. — Фундаментальные алгоритмы на C++. Часть 5. Алгоритмы на графах
Обсудите книгу на научном форуме Нашли опечатку?
Название: Фундаментальные алгоритмы на C++. Часть 5. Алгоритмы на графахАвтор: Седжвик Р. Аннотация: Эта книга посвящена глубокому исследованию всех основополагающих концепций и алгоритмов, которые, несомненно, относятся к категории «вечных». Тщательным образом проштудировав их, вы получите знания, которые никогда не устареют и которыми вы будете пользоваться всегда.
Язык: Рубрика: Computer science /Алгоритмы /Статус предметного указателя: Готов указатель с номерами страниц ed2k: ed2k stats Год издания: 2002Количество страниц: 496Добавлена в каталог: 19.06.2005Операции: Положить на полку |
Скопировать ссылку для форума | Скопировать ID
Предметный указатель
Абстрактный тип данных (АТД) 21 31 Алгоритм 36 93 334 376 Алгоритм BFS (breadth-first search — поиск в ширину) 94 Алгоритм DFS (depth-first search — поиск в глубину) 69 93 117 Алгоритм DFS (depth-first search — поиск в глубину) по матрице смежности 108 Алгоритм DFS (depth-first search — поиск в глубину) по спискам смежных вершин 108 Алгоритм DFS (depth-first search — поиск в глубину) рекурсивный 93 Алгоритм Беллмана — Форда 347 Алгоритм Борувки 247 266 Алгоритм быстрого объединения см. «Метод: быстрого объединения» Алгоритм быстрого поиска см. «Метод: быстрого поиска» Алгоритм выталкивания избыточного потока 411 Алгоритм выталкивания избыточного потока, худший случай 411 Алгоритм выталкивания превосходящего потока 412 Алгоритм вычеркивания циклов 438 442 Алгоритм вычисления максимального потока 386 387 Алгоритм Габова 219 Алгоритм Дейкстры 294 Алгоритм динамический 36 Алгоритм интерактивный 36 Алгоритм Косарайю 214 Алгоритм Крускала 246 260 Алгоритм определения максимальных потоков 402 Алгоритм определения самого длинного аугментального пути 389 Алгоритм поиска кратчайшего маршрута 86 Алгоритм поиска максимального потока 376 Алгоритм поиска на графе 93 Алгоритм Прима 246 250 259 Алгоритм сетевой симплексный 86 444 449 Алгоритм сжатия пути см. «Метод: сжатия пути» Алгоритм Тарьяна 213 217 Алгоритм топологической сортировки 205 Алгоритм Уоршалла 180 Алгоритм Флойда 184 304 345 Алгоритм Форда — Фалкерсона 377; см. также «Метод: аугментального пути» Алгоритм Форда — Фалкерсона, худший случай 404 Алгоритм эффективный 334 Алгоритм Ярника 258 Арбитражная операция 343 Бахрома (fringe) 141 254 298; Библиотечное программирование 332 Бисвязность 124 Вектор ребер 37 Вершина (vertex) 23 128 162 255 Вершина (vertex) краевая 255 Вершина (vertex) отделимости (separation vertices) 128; см. также «Точка сочленения графа» Вершина (vertex) полустепени захода (indegree) 29 Вершина (vertex) полустепени исхода (outdegree) 29 Вершина (vertex) смежные (adjacent) 23 Вершина (vertex), исток (source) 162 Вершина (vertex), сток (sink) 162 Вершинная связность (vertex connectivity) 129 Вес 279 Вес пути 279 Вес ребера 340 Вес ребера отрицательный 340 Гамильтонов путь 72 Генератор случайных графов 59 Граф 18 22 124 157 160 244 379 Граф k-реберно-связный 130 Граф k-связный 129 Граф ациклический связный 26; см. также «Дерево (tree)» Граф взвешенный 30 Граф вызовов функций 63 Граф двусвязный 128 Граф двухдольный 28 Граф Де-Бруйна 66 Граф изоморфный 24 Граф интервальный 65 Граф насыщенность графа 27 Граф неориентированный 28 Граф неориентированный базовый 30 Граф ориентированный 28 157 160 Граф ориентированный ациклический (DAG) 30 158 164 193 Граф ориентированный двоичный 196 Граф ориентированный сильно связный (strongly connected) 164 Граф ориентированный, направленный цикл 30 Граф ориентированный, обращение (reverse) 162 Граф планарный 24 Граф полный 27 Граф простой 22 Граф разреженный 28 Граф реберно-отделимый 124 Граф связный 26 Граф сепарабельный (separable) 128 Граф случайный 60 Граф со степенями разделения 65 Граф статический 35 Граф точка сочленения (articulation point) 128 Граф транзакций 62 Граф триангуляция Делони 276 Граф Эвклидов 24 Граф Эвклидов с близкими связями 61 Граф, генератор случайных графов 59 Граф, дополнение графа 27 Граф, индуцированный подграф 23 Граф, матрица смежности 38 Граф, объединение двух графов 27 Граф, подграф 23 Граф, подграф индуцированный 23 Граф, подграф максимальный связный 26 Граф, свойство локальности 60 Граф, сечение (cut) графа 244 379 Граф, сечение (cut) графа минимальное 379 Граф, сечение (cut) графа, st-сечение 379 Граф, список смежных вершин 38 Дерево (tree) 26 231 289 Дерево (tree) кратчайших путей (SPT) 289 Дерево (tree) минимальное остовное (MST) 231 232 Дерево (tree) минимальное остовное (MST) Эвклидово 276 Дерево (tree) остовное 26 Дерево (tree) Фибоначчи 270 Диаграмма PERT 158 340 Длина пути 25 Дополнение графа 27 Дуга (arc) 29 Задача 314 360 Задача двудольного взвешенного сочетания 86 Задача двудольного сочетания 86 425 Задача динамической достижимости 228 Задача календарного планирования 474 Задача коммивояжера 88 Задача о Кенигсбергских мостах 75 Задача о кратчайшем пути с единственным источником 464 Задача о максимальном потоке 364 369 420 Задача о максимальном сочетании 473 Задача о минимальном сечении 379 Задача о многопродуктовом потоке 473 Задача о потоке минимальной стоимости 364 435 Задача о почтальоне 87 468 Задача о трудоустройстве 362 Задача обнаружения циклов 159 Задача обработки графов 83 Задача окраски 87 Задача определения кратчайших путей для всех пар вершин 184 Задача поиска наиболее длинных путей с несколькими источниками 314 Задача распределения 86 361 467 Задача составления расписаний 158 Задача сочетания с минимальными расстояниями 362 Задача топологической сортировки 158 159 Задача транспортная 360 Запрос (query) 35 Изоморфные графы 24 Интерфейс 52 Интерфейс насыщенный 52 Интерфейс «толстый» 52 Исследование Тремо 95 Календарное планирование 329 Карта (шар) 162 Классы эквивалентности 191 Клика (clique) 27; см. также «Подграф: полный» Контур (tour) 25 Коридор (passage) 94 Кратчайший путь (shortest path) 132 Лабиринт (maze) 94 Лес (forest) 26 Лес (forest) DFS 112 Лес (forest) остовный 26 Математическое программирование 338 Матрица 178 290 Матрица булева 178 Матрица путей 290 Матрица расстояний 290 Матрица смежности графа 21 38 Метод 99 376 Метод аугментального пути 376 Метод быстрого объединения см. «Алгоритм: быстрого объединения» Метод быстрого поиска см. «Алгоритм: быстрого поиска» Метод выталкивания превосходящего потока 402 413 Метод поиска в глубину 99 Метод Тремо 100 Метод Уоршалла 180 Метод Форда — Фалкерсона 376; см. также «Метод: аугментального пути» Минимальное остовное дерево (MST) 231 Модель линейного программирования (LP-модель) 364 Мост (bridge) 124 Мультиграф 22 Мультиграф с петлями 23 Набор соединений (connections) 18 Набор элементов (items) 18 Насыщенность графа 27 Номер предпорядка (preorder number) 110 Обращение орграфа 163 Объединение двух графов 27 Операция 47 146 254 321 Операция, decrease key (уменьшить ключ) 270 Операция, edge existence (проверка наличия ребра) 47 Операция, find edge (найти ребро) 53 Операция, find minimum (поиск минимального ребра) 254 Операция, remove edge (удалить ребро) 47 Операция, remove the minimum (удалить минимальное ребро) 254 270 Операция, reweighting (повторное взвешивание) 321 350 Операция, update (обновления ) 146 Операция, арбитражная 343 Орграф 29 157 279; Орграф взвешенный 279 Орграф, декомпозиция 175 Орграф, обращение (reverse) 162 Орграф, сильно связный (strongly connected) 164 Ослабление 287; см. также «Релаксация (relaxation)» Остаточная сеть (residual network) 382 Отделимость 123 Отношение (relation) 190 Отношение (relation) рефлексивное 190 Отношение (relation) симметричное 190 Отношение (relation) эквивалентности 191 ОЧЕРЕДЬ (QUEUE) 141 Очередь (queue) FIFO 132 Очередь (queue) LIFO 132 Очередь (queue) с приоритетами 146 Перекресток (intersection) 94 Петля (self-loop) 22 Планирование 329 Планирование календарное 329 Подграф 23 Подграф максимальный связный 26 Подграф полный 27 Подграф, индуцированный подграф 23 Поиск в глубину (DFS) 69 93 99 169 Поиск в глубину (DFS) на матрице смежности 169 Поиск в глубину (DFS) на списках смежных вершин 169 Поиск в ширину (BFS) 94 132 Поиск на графе 93 104 Поиск простого пути 70 Порядок 192 Порядок полный 192 Порядок частичный 191 Потенциал (potential) 445 Потенциал (potential), потенциалы вершин 448 Поток (flow) 368 Поток (flow) допустимый 423 436 Поток (flow) максимальный 369 419 Поток (flow) минимальной стоимости 435 437 Поток (flow) превосходящий (preflow) 403 Поток (flow), допустимое остовное дерево 449 Поток (flow), остаточная сеть (residual network) 437 Поток (flow), остовное дерево максимального потока 446 Поток (flow), стоимость потока (flow cost) 435 Приложение составления расписаний 194 Программирование 332 Программирование библиотечное 332 Программирование математическое 338 Путь (path) 25 69 132 161 165 231 384 Путь (path) аугментальный 384 Путь (path) аугментальный кратчайший 386 399 Путь (path) аугментальный с максимальной пропускной способностью 388 397 Путь (path) аугментальный самый длинный 389 Путь (path) Гамильтонов 72 Путь (path) кратчайший 132 231 281 Путь (path) кратчайший в ациклических сетях 311 Путь (path) кратчайший из нескольких источников 312 Путь (path) обходной 341 Путь (path) ориентированный 161 Путь (path) простой 69 Путь (path) циклический 25 165 Путь (path) Эйлеров 74 Путь (path), вес пути 279 Путь (path), длина пути 25 Путь (path), непересекающиеся пути 26 Путь (path), непересекающиеся пути по вершинам 26 Путь (path), непересекающиеся пути по ребрам 26 Ребро 23 244 379 Ребро инцидентно (incident on) 23 Ребро ориентированные ребра 29 Ребро случайное 59 Ребро, пересекающее ребро (crossing edge) 244 379 Ребро, реберная связность (edge connectivity) 130 Релаксация (relaxation) 287; см. также «Ослабление» Сведение 325 334 336 338 Сведение эффективное 334 Свойство сечения 244 Свойство цикличности 245 Связность 129 Связность вершинная 129 Связность реберная 130 Сеть (network) 279 382; Сеть (network) ациклическая 312 Сеть (network) транспортная 30 366 Сеть (network) транспортная, со случайными потоками 396 Сеть (network) Эвклидова 319 Сеть (network), st-сеть 368 Сеть (network), диаметр сети 305 Сеть (network), остаточная сеть (residual network) 382 410 437 Сеть (network), управление потоками в сети 368 Сечение (cut) графа 244 379 Сечение (cut) графа минимальное 379 Сечение (cut) графа, st-сечение 379 Сильная связность (strong connectivity) 212 Сортировка 199 Сортировка топологическая 194 199 Сортировка топологическая обратная 200 Список смежных вершин графа 21 38 44 Стандартная библиотека шаблонов (STL) 33 Степень (degree) вершины 23 Стоимость потока (flow cost) 435 Схема BDD (binary decision diagram) 196 Теорема 378 Теорема декомпозиции потоков 371 Теорема Куратовского 85 Теорема Менгера 130 429
Реклама
|
|
О проекте