|
|
 |
| Авторизация |
|
|
|
| Поиск по указателям |
|
|
|
|
|
|
|
 |
|
|
|
| Кристофидес Н. — Теория графов. Алгоритмический подход. |
|
|
|
| Предметный указатель |
 -оптимальность 140—141
(s-t)-разрез 202—206
p-кратный внешний центр [p-outcentre] 112
p-кратный внутренний центр [p-incentre] 112
p-медиана 129
p-медиана абсолютная 130
p-медиана внешняя 130
p-медиана внутренняя 130
p-медиана обобщенная 132 139
p-центр (кратный центр) 41 111 112
p-центр абсолютный 112 113
p-центр абсолютный, нахождение 113—123
r-подграф 80
r-подграф максимальный 80—84
Активный цикл см. «Маршрут замкнутый активный»
Алгоритм венгерский 405
Алгоритм венгерский для задачи о назначениях 405—407
Алгоритм венгерский для транспортной задачи 413
Алгоритм двойственный решения задачи о потоке минимальной стоимости 351—353
Алгоритм Дейкстры решения задачи о кратчайшем пути между двумя заданными вершинами s и t с неотрицательной матрицей весов 174—183
Алгоритм Краскала построения кратчайшего остова графа 160—162
Алгоритм направленного древовидного поиска для задачи о p-медиане 138
Алгоритм направленного поиска для задачи о р-медиане 139—144
Алгоритм нахождения абсолютного p-центра 114 115
Алгоритм основной для задачи о потоке минимальной стоимости 339—342
Алгоритм поиска, использующего дерево решений для задачи о коммивояжере 285—295
Алгоритм приближенный для задачи о р-медиане 139—141
Алгоритм Прима построения кратчайшего остова графа 162—163
Алгоритм расстановки пометок в задаче о максимальном потоке 314—315
Алгоритм решения задачи китайского почтальона 331 332
Алгоритм решения задачи о K кратчайших путях между двумя заданными вершинами 195 196
Алгоритм решения задачи о кратчайшем пути между двумя заданными вершинами s и t с общей матрицей весов 183—189
Алгоритм решения задачи о назначениях 405
Алгоритм решения задачи о назначениях, матричная форма 406 407
Алгоритм решения задачи о наибольшем паросочетании (ЗНПС) 381—383
Алгоритм решения задачи о наименьшем покрытии (ЗНП), использующий дерево поиска 55
Алгоритм решения задачи о наименьшем разбиении (ЗНР) 55
Алгоритм решения задачи о покрытии наименьшей мощности (ЗПНМ) 416
Алгоритм решения задачи о потоке между каждой парой вершин 331—334
Алгоритм решения задачи о раскраске с использованием дерева поиска 88—90
Алгоритм Робертса и Флореса порождения гамильтонова цикла 249—253
Алгоритм Флёри построения эйлерова цикла 230
Алгоритм Флойда решения задачи о кратчайшем пути между всеми парами вершин 189—190
Алгоритм Хакими модифицированный 107—110
Алгоритм Хакими нахождения абсолютного центра 104 105
Алгоритм штрафования вершин для задачи коммивояжера 285—295
Алгоритм «беспорядка» [«out-of-kilt»] 339
Алгоритмы приближенные решения задачи о раскраске 90—91
Антибаза [contrabasis] 38
База сильная [power] 39
База [basis] 37—40
Булевское (логическое) выражение 64
Вершина внешняя [outer] 374—378
Вершина внутренняя [inner] 374—375
Вершина конечная [final] 11
Вершина концевая [terminal] 11
Вершина начальная [initial] 11
Вершина несущественная, избыточная [inessential] 33
Вершина существенная, неотъемлемая [essential] 33
Вершина экспонированная [exposed] 371
Вершина [vertex] 11
Вершина, пропускная способность 326
Внешне устойчивое множество см. «Доминирующее множество вершин»
Внутреннее произведение вершин 245
Выбор места для склада 129
Выбор проекта 45
Гипотеза четырех красок 79
Граф r-хроматический [r-chromatic] 75
Граф антисимметрический 20
Граф взвешенный 15
Граф двудольный неориентированный 21
Граф двудольный ориентированный 21
Граф двудольный [bipartite] 21 405 412
Граф инкрементальный [incremental] 321 339 350 352 360
Граф Куратовского 23
Граф Муна — Мозера 70
Граф неориентированный [nondirected] 11
Граф неориентированный, двойник 11
Граф непланарный [nonplanar] 23
Граф несвязный [disconnected] 23
Граф односторонне связный или односторонний [unilateral] 23
Граф ориентированный [directed] 11
Граф остовов [tree graph] 157
Граф планарный [planar] 22 79
Граф полный антисимметрический 20
Граф полный симметрический 20
Граф полный [complete] 19
Граф реберный [line] 237
Граф редуцированный [reduced] 254
Граф симметрический [simmetric] 20
Граф со взвешенными вершинами [vertex-weighted] 15
Граф со взвешенными дугами [arc-weighted] 15
Граф транзитивный [transitive] 33
Граф унитарный [unitary] 323
Граф [graph] 11
Граф, дополнение 46
Граф, сильно связный или сильный [strong] 23
Граф, слабо связный или слабый [weak] 23
Густота см. «Кликовое число»
Дерево альтернирующее 374
Дерево аугментальное [augmenting] 375
Дерево венгерское 380—382
Дерево ориентированное [directed] 145—147 240
Дерево остовное длиннейшее 163
Дерево остовное [spanning tree] 145—224 (см. «Остов»)
Дерево остовное, процедура порождения 149—157
Дерево остовное, расщепление [division] 153
Дерево решения для поиска по глубине 425
Дерево решения для поиска по ширине 425
Дерево решения для поиска [search tree] 422—427
Дерево решения, ветвление 422 424
Дерево решения, висячая вершина 423
Дерево решения, границы 426
Дерево решения, разбиение 424
Дерево решения, функции ветвления 426—427
Дерево цветущее [blossomed] 376
Дерево Штейнера наикратчайшее 167—169
Дерево [tree] 145—172
Дерево, сращивание [merging] 153
Дерево, элементарное преобразование 149
Диаметр графа 11 125
Доминирующее множество вершин 40 50
Доминирующее множество вершин минимальное [minimal] 50
Доминирующее множество вершин наименьшее [minimum] 50
Достижимое множество 29
Достижимость [reachability] 23
Дуга обратная 313 356
Дуга прямая 313 356
Дуга [arc] 11
Дуга, вес [weight], длина [length], стоимость или цена [cost] 15 201
Дуга, надежность [reliability] 201
Дуга, нижняя граница потока 310
Дуга, поток, входящий в 354
Дуга, поток, выходящий из 354
Дуга, пропускная способность 202 282 313
Задача государственного районирования [political districting] 65
Задача китайского почтальона 231—237
Задача нахождения допустимого потока минимальной стоимости 310
Задача о K кратчайших путях между двумя заданными вершинами 195
Задача о K ферзях на шахматной доске 70
Задача о доставке молока или почты [delivery of post] 231
Задача о кёнигсбергских мостах 228
Задача о коммивояжере 242—309
Задача о коммивояжере минимаксная 244
Задача о коммивояжере минисуммная 244
Задача о коммивояжере, нижняя граница из задачи о кратчайшем остове 266 279
Задача о коммивояжере, нижняя граница из задачи о назначениях 265 297—303
Задача о кратчайшем пути между заданными вершинами s и t 175—189
Задача о кратчайшем пути между заданными вершинами s и t с неотрицательной матрицей весов 177—183
Задача о максимальном паросочетании (ЗМП) 368—371
| Задача о максимальном потоке (от s к t) 310—325
Задача о минимальном покрытии (ЗНПО) 369
Задача о многопродуктовом потоке [multicommodity] 311 325
Задача о назначениях (ЗН) [assignment problem] 284 404—411
Задача о наибольшем паросочетании (ЗНПС) 370 375
Задача о наименьшем покрытии 43 53—68
Задача о наименьшем покрытии, вычисление нижней границы 60
Задача о наименьшем покрытии, приложения 63—68
Задача о наименьшем покрытии, упрощение 54
Задача о покрытии наименьшей мощности (ЗПНМ) [minimum cardinality covering problem] 370 416
Задача о потоках с выигрышами 311 353—364
Задача о потоке минимальной стоимости от s к t 310 339
Задача о раскраске 375
Задача о раскраске, решение методом 0-1 программирования 84—86
Задача о раскраске, решение методом динамического программирования 80—84
Задача о раскраске, сведение к ЗНП 86—88
Задача о распределении ресурсов 94
Задача об остовном графе с предписанными степенями [degree-constrained partial graph problem] 368 411—414
Задача размещения минимаксная 98 127
Задача размещения минисуммная 98 127
Задача сетевого планирования [network planning] 65
Задача синхронизации линии сборки [assembly line balancing] 65
Задача теории расписаний 94
Задача транспортная (ТЗ) 371 412—416
Задача Штейнера 166—169
Задача Штейнера евклидова 167
Задача Штейнера линейная 169
Задача Штейнера на графах 166 167
Информационный поиск [retrieval information] 63
Исследование структуры организации 39
Источник [source] 310
Клика графа [clique] 46
Кликовое число [clique number] 43
Компонента графа односторонняя 24
Компонента графа сильная 24 33—36
Компонента графа слабая 24
Компрессия [compression] матрицы 297
Константа «проникновения» [penetration] 114
Контрадостижимое множество [reaching set] 30
Контур 17 (см. «Орцепь замкнутая простая»)
Контур гамильтонов 17 157 237 242—309
Контур гамильтонов, алгебраический метод нахождения 245—249
Контур независимый [independent] 218
Корень ориентированного дерева 146
Корень ориентированного дерева, замена 193
Корень [root] дерева 374
Коцикломатическое число 218
Кратные центры [multiple centres] 111
Кратчайшее дерево Штейнера 166—167
Кратчайший остов графа [shortest spanning tree] 158—161
Критический путь [critical path] 197—200
Максимальный полный подграф 46 (см. «Клика»)
Маршрут аугментальный [augmenting] 356
Маршрут аугментальный, инкрементальная пропускная способность [incremental capacity] 356
Маршрут замкнутый активный [active cycle] 358—364
Маршрут замкнутый [cycle] 17
Маршрут [chain] 4
Маршрут, выигрыш 356
Маршруты полетов самолетов 64
Матрица достижимостей [reachability matrix] 29 30 31
Матрица инциденций [incidence matrix] 26 148 155 170 226 239 379
Матрица контрадостижимостей [reaching] 30 31
Матрица ограниченных достижимостей 33
Матрица редуцированная 406
Матрица смежности модифицированная 245
Матрица смежности [adjacency matrix] 25
Медиана абсолютная 130
Медиана внешне-внутренняя 129
Медиана внешняя 128
Медиана внутренняя 128
Медиана кратная 129 (см. «p-медиана»)
Медиана [median] 98 127—143
Метод критического пути (МКП) [critical path method] 197
Наименьшее доминирующее множество ребер см. «Наименьшее покрытие»
Независимое множество вершин максимальное [maximal] 44—48 80 86 87
Независимое множество вершин наибольшее [maximum] 45 65
Независимое множество вершин [independent vertex set] 44
Независимое множество ребер наибольшее 66
Независимое множество ребер [independent link set] 66
Область 114
Обход лабиринта 240
Орцепь 14 (см. «Цепь ориентированная»)
Орцепь замкнутая 17
Орцепь замкнутая простая [elementary circuit] 17
Остов [spanning tree] 145 224
Остов, число 148
Отображение [mapping] 11
Паросочетание максимальное [maximal] 389
Паросочетание наибольшее [maximum] 66 368
Паросочетание совершенное [perfect] 389
Паросочетание [matching] 66 368—420
Передаточное число внешнее [out] 128
Передаточное число внутреннее [in] 128
Передаточное число [transmission number] 127—128
ПЕРТ 197
Петля [loop] 16
Плотность см. «Кликовое число»
Подграф максимальный [maximal subgraph] 23 24
Подграф остовный [partial graph] 18
Подграф порожденный [subgraph] 18
Подграф [partial subgraph] 19
Покрытие минимальное [minimal] 369
Покрытие наименьшее [minimum] 66 67
Покрытие [covering] 66 67 369
Полустепень захода [indegree] 18
Полустепень исхода [outdegree] 18
Пометка предшествования 153
Пометка предшествования, изменение 153
Поток в графах с выигрышами 356
Поток в графах с выигрышами в вершинах 364
Поток в графах с пропускными способностями дуг и вершин 326
Поток в графах со многими источниками и стоками 325
Поток допустимый максимальный 354
Поток допустимый оптимально-максимальный 354
Поток допустимый оптимальный 354
Поток допустимый [feasible flow] 310 353—358
Поток конформальный [conformal] 325
Поток [flow] 310
Поток, аугментальная цепь [flow-augmenting chain] 313
Потоковая эквивалентность 330
Проверка электрических, телефонных или железнодорожных линий 231
Псевдовершина [pseudovertex] 375
Пустое множество 11
Путь замкнутый элементарный 17
Путь замкнутый [path] 16
Путь кратчайший 173 189—193
Путь с наибольшей приведенной пропускной способностью 206—211
Путь самый длинный 198
Путь [path] 13
Путь, вес, длина или стоимость [length] 15
Путь, длина или мощность [cardinality] 16
Путь, надежность 201 202
Путь, ответвление [deviation] 195
Путь, пропускная способность 202
Радиус 101
Радиус абсолютный внешний 103
Радиус абсолютный внутренний 101
Радиус внешне-внутренний 102
Радиус внешний 101
Радиус внутренний 101
Разделение внешнее [out] 100
Разделение внутреннее [in] 100
Разделение [separation] 99—101
Размещение аварийных служб и пунктов обслуживания 101—102 106 107
Размещение нескольких центров обслуживания 112
Размещение центров 51 52 98—125
Размещение [location] 98
Разрез для ориентированного графа 223 224
Разрез правильный [proper] 222 223
Разрез фундаментальный 224 225
|
|
|
| Реклама |
|
|
|
|
|
О проекте