Главная    Ex Libris    Книги    Журналы    Статьи    Серии    Каталог    Wanted    Загрузка    ХудЛит    Справка    Поиск по индексам    Поиск    Форум   
blank
Авторизация

       
blank
Поиск по указателям

blank
blank
blank
Красота
blank
Седжвик Р. — Фундаментальные алгоритмы на C++. Часть 5. Алгоритмы на графах
Седжвик Р. — Фундаментальные алгоритмы на C++. Часть 5. Алгоритмы на графах



Обсудите книгу на научном форуме



Нашли опечатку?
Выделите ее мышкой и нажмите Ctrl+Enter


Название: Фундаментальные алгоритмы на C++. Часть 5. Алгоритмы на графах

Автор: Седжвик Р.

Аннотация:

Эта книга посвящена глубокому исследованию всех основополагающих концепций и алгоритмов, которые, несомненно, относятся к категории «вечных». Тщательным образом проштудировав их, вы получите знания, которые никогда не устареют и которыми вы будете пользоваться всегда.

Краткость, точность, выверенность, актуальность, изобилие примеров и учебных заданий - вот лишь небольшой перечень очевидных достоинств книги. Иллюстрация алгоритмов на одном из наиболее эффективных языков программирования С лишний раз подчеркивает их популярность и «вечность». Подробно рассматривается широчайший спектр фундаментальных алгоритмов на графах, в числе которых: поиск в орграфах, неорграфах и сетях; построение минимальных остовных деревьев и кратчайших путей; вычисление потоков в сетях с различными характеристиками. Большое внимание уделяется рабочим характеристикам алгоритмов, а также их математическому выводу.

Книгу можно использовать в качестве курса лекций (как студентами, так и преподавателями), справочного пособия или просто «романа», получая при этом ни с чем не сравнимое удовольствие.


Язык: ru

Рубрика: Computer science/Алгоритмы/

Статус предметного указателя: Готов указатель с номерами страниц

ed2k: ed2k stats

Год издания: 2002

Количество страниц: 496

Добавлена в каталог: 19.06.2005

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID
blank
Предметный указатель
Абстрактный тип данных (АТД)      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
1 2
blank
Реклама
blank
blank
HR
@Mail.ru
       © Электронная библиотека попечительского совета мехмата МГУ, 2004-2024
Электронная библиотека мехмата МГУ | Valid HTML 4.01! | Valid CSS! О проекте