Предметный указатель

Активный цикл tM. Маршрут замкнутый активный

Алгоритм <беспорядка1) [out-ot-kilt ] 339

- венгерский 405

--для задачи о назначениях 405-407

--- транспортной задачи 413

- двойственный решения задачи о потоке минимальной стоимости 351-353

- Дейкстры решения задачи о кратчайшем пути между двумя заданными вершинами S и г с неотрицательной матрицей весов 174-183

- Краскала построения кратчайшего остова графа 160-162

- направленного древовидного поиска для задачи о р-медиане 138

--поиска для задачи о р-медиане 139-

-нахождения абсолютного р-центра 114,

- основной для задачи о потоке минимальной стоимости 339-342

- поиска, использующего дерево решений для задачи о коммивояжере 285-295

- приближенный для задачи о р-меднане 139-141

- Прима построения кратчайшего остова графа 162-163

- расстановки пометок в задаче о максимальном потоке 314-315

- решения задачи китайского почтальона 331, 332

---о К кратчайших путях между

двумя заданными вершинами 195, 196

----кратчайшем пути между двумя

заданными вершинами s и t с общей матрицей весов 183-189

---- назначения 405

-----матричная форма 406, 407

----наибольшем паросочетаний

(ЗНПС) 381-383

----наименьшем покрытии (ЗНП),

использующий дерево поиска 55

--- - покрытии наименьшей мощности (ЗНПМ) 416

-----разбиении (ЗНР) 55

----потоке между каждой парой

вершин 331-334

---- раскраске и использованием

дерева поиска 88-90

- Робертса и Флореса порождения гамильтонова цикла 249-253

- Флёри построения эйлерова цикла 230

- Флойда решения задачи о кратчайшем пути между всеми парами вершин 189- 190

- Хакими нахождения абсолютного центра 104, 105

-- модифицированный 107-110

- штрафования вершин для задачи коммивояжера 285-295

Алгоритмы приближенные решения задачи

о раскраске 90-91 Антибаза [contrabasisl 38 База [basis! 37-40

- сильная [power] 39

Булевское (логическое) выражение 64

Вершина [vertex! И

- внешняя [outer! 374 - 378

- внутренняя [inner! 374-375

- конечная [final! И

- концевая [terminal! И

- начальная [initial! 11

Вершина несущественная, избыточная [inessential! 33

- пропускная способность 326

- существенная, неотъемлемая [essential!

- экспонированная [exposed! 371 Внешне устойчивое множество см. Доминирующее множество вершин

Внутреннее произведение вершин 245 Выбор места для склада 129

- проекта 45

Гипотеза четырех красок 79 Граф [graph! II

- антисимметрнческий 20

- взвешенный 15

- двудольный [bipartite! 21, 405, 412 -- неориентированный 21

-- ориентированный 21

- дополнение 46

- инкрементальный [incremental! 321, 339, 350, 352, 360

- Куратовского 23

- Муна-Мозера 70

- неориентированный [nondirected! И -- двойник 11

- непланарны{) [nonplanar! 23

- несвязный [disconnected] 23

- односторонне связный или односторонний [unilateral] 23

- ориентированный [directed! И

- остовов [tree graph! 157

- планарный [planar! 22, 79

- полный [complete! 19

--антисимметрнческий 20

--симметрический 20

- реберный [line! 237

- редуцированный [reduced! 254

- г-хроматический [7-chromatic! 75

- сильно связный или сильный [strong! 23

- симметрический [simmetric! 20

- слабо связный или слабый [weak! 23

- со взвешенными вершинами [vertex-weighted] 15

---дугами [arc-weighted! 15

- транзитивный [transitive] 33

- унитарный [unitary! 323 Густота см. Кликовое число

Дерево [tree! 145 - 172

- альтернирующее 374

- аугментальное [augmenting! 375

- венгерское 380-382

- ориентированное [directed! 145-147, 240

- остовное [spanning tree! (см. Остов) 145-224

--длиннейшее 163

--процедура порождения 149-157

--расщепление [division! 153

- решения для поиска [search tree! 422- 427

-- ветвление 422, 424

-- границы 426

-- для поиска по глубине 425

-----ширине 425

--висячая вершина 423

-- разбиение 424

--функции ветвления 426-427

- сращивание [merging! 153

- цветущее [blossomed! 376

- Штейнера наикратчайшее 167-169

- элементарное преобразование 149 Диаметр графа И, 125

Доминирующее множество вершин 40, 40

---минимальное [minimal] 50

---наименьшее [minimum] 50

Достижимое множество 29 Достижимость [reachability] 23 Дуга [arc] 11

- вес [weight] (длина [length], стоимость или цена [cost] 15, 201

- надежность [reliability] 201

- нижняя граница потока через 310

- обратная 313, 356

- поток, входящий в 354 --выходящий из 354

- пропускная способность 202, 282, 313

- прямая 313, 356

Задача государственного районирования [political districting] 65

- об остовном графе с предписанными степенями [degree-constrained partial graph problem] 368, 411-414

- китайского почтальона 231-237

- нахождения допустимого потока минимальной стоимости 310

- о доставке молока или почты [delivery о1 post] 231

--Кёнигсбергских мостах 228

--коммивояжере 242-309

--- минимаксная 244

---минисуммная 244

---нижняя граница из задачи о

кратчайшем остове 266, 279 -------- назначениях 265,

297-303

--К кратчайших путях между двумя

заданными вершинами 195

---кратчайшем пути между заданными

вершинами s и ( 175-189

----------с неотрицательной матрицей весов 177-183

--К ферзях на шахматной доске 70

--максимальном паросочетании (ЗМП)

368-371

---потоке (от S к () 310-325

--минимальном покрытии (ЗНПО) 369

--многопродуктовом потоке [multicom-

modity] 311, 325 --назначениях (ЗН) [assignment problem] 284, 404-411

--наибольшем паросочетании (ЗНПС)

370, 375

--наименьшем покрытии 43, 53-68

----вычисление нижней границы 60

----приложения 63-68

---- упрощение 54

--покрытии наименьшей мощности

(ЗПНМ) [minimum cardinality covering

problem] 370, 416

- - потоке минимальной стоимости от г к t 310, 339

--потоках с выигрышами 311, 353-364

-- раскраске 375

---решение методом динамического

программирования 80-84 -----0-1 программирования 84-

---сведние к ЗНП 86-88

- - распределении ресурсов 94

- размещения минимаксная 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 пшпЬег] 43 Компонента графа односторонняя 24 --сильная 24, 33-36

- - слабая 24

Компрессия [compression] матрицы 297 Константа проникновения [penetration! 114

Контрадостижимое множество [reaching set] 30

Контур см Орцепь замкнутая простая 17

- гамильтонов 17, 157, 237, 242-309 --алгебраический метод нахождения

245-249

- независимый [independent] 218 Корень [root] дерева 374

- ориентированного дерева 146

---замена 193

Коцикломатическое число 218 Кратные центры [multiple centres] 111 Кратчайшее дерево Штейнера 166-167 Кратчайший остов графа [shortest spanning

tree] 158-161 Критический путь [critical path] 197-200

.-оптимальность 140-141

Максимальный полный подграф см Клика 46 Маршрут [chain] 4

- аугментальный [augmenting] 356 -- инкрементальная пропускная способность [incremental capacity] 356

- выигрыш 356

- замкнутый [cycle] 17

--активный [active cycle] 358-364

Маршруты полетов самолетов 64 Матрица достижимостей [reachability matrix] 29, 30, 31

- инциденций [incidence matrix] 26, 148, 155, 170, 226, 239, 379

- контрадостижимостей [reaching] 30, 31

- ограниченных достижимостей 33

- редуцированная 406

- смежности [adjacency matrix] 25

- - модифицированная 245 Медиана [median] 98, 127-143

- абсолютная 130

- внешняя 128

- внешне-внутренняя 129

- внутренняя 128

- кратная см р-медиана 129

Метод критического пути (МКП) Icritical path method] 197

Наименьшее доминирующее множество ребер см Наименьшее покрытие

Независимое множество вершин [independent vertex set] 44

---максимальное [maximal] 44-48,

80, 86, 87

---наибольшее [maximum] 45, 65

--ребер [independent link set] 66

--- наибольшее 66

Область 114

Обход лабиринта 240

Эрцепь см. Цепь ориентированная 14

- замкнутая 17

--простая [elementary circuit] 17

Эстов [spanning tree] 145, 224

- число 148

Отображение [mapping] 11

Паросочетание [matching] 66, 368-420

- максимальное [maximal] 389

- наибольшее [maximum] 66, 368

- совершенное [perfect] 389 Передаточное число [transmission number]

127-128

--внешнее [out] 128

--внутреннее [in] 128

ПЕРТ 197

Петля [loop] <6

Плотность см Кликовое число

Подграф [partial subgraph] 19

- максимальный [maximal subgraph] 23,

- остовный [partial graph] 18

- порожденный [subgraph] 18 Покрытие [covering] 66, 67, 369

- минимальное [minimal] 369

- наименьшее [minimum] 66, 67 Полустепень захода [indegree] 18

- исхода [outdegree] 18 Пометка предшествования 153 -- изменение 153

Потоь [flow] 310

- аугментальная цепь [flow-augmenting chain] 313

- в графах с выигрышами 356

-----в вершинах 364

----многими источниками и стоками 325

.----пропускными способностями

дуг и вершин 326

- допустимый [feasible flow] 310, 353-358 -- максимальный 354

--оптимально-максимальный 354

-- оптимальный 354

- конформальный [conformal] 325 Потоковая эквивалентность 330 Проверка электрических, телефонных или

железнодорожных линий 231 Псевдовершина [pseudovertex] 375 Пустое множество И Путь [path] 13

- вес, длина или стоимость [length] 15

- длина или мощность [cardinality] 16

- замкнутый [path] 16 -- элементарный 17

- кратчайший 173, 189-193

- надежность 201, 202

- ответвление [deviation] 195

- пропускная способность 202

- самый длинный 198

- с наибольшей приведенной пропускной способностью 206-211

р-кратный внешний центр [p-outcentre] 112

- внутренний центр [p-incentre] 112 р-медиана 129

- абсолютная 130

- внешняя 130

- внутренняя 130

- обобщенная 132, 139

р-центр (кратный центр) 41, 111, 112

- абсолютный 112, 113 --нахождение 113-123

Радиус 101

- абсолютный внешний 103 -- внутренний 101

- внешне-внутренний 102

- внешний 101

Радиус в нутренний 101 Разделение [separation] 99-101 внешнее [out] 100

- внутреннее [щ] 100 Размещение [location] 98

- аварийных служб и пунктов обслуживания 101-102, 106, 107

- нескольких центров обслуживания 112

- центров 51, 52, 98-125 Разрез [cut-set] 221-225, 312, 313

- величина 312

- для ориентированного графа 223, 224

- правильный [proper] 222, 223

- фундаментальный 224, 225

-- матрица 225, 226, 239

Раскраска [colouring] 75-96

- оптимальная независимая 80, 84 Ребро [link] И

- искусственное 232 г-подграф 80

- максимапьный 80-84

Смежные дуги 14

- вершины 14 Соответствие И

- обратное 13

Специальный остовный подграф [equally

partial] 391 Степень вершины [degree] 18 --fe-шаговая 91

Строгое пересечение (SI) [strict intersection] 117-118 Сток [sink] 310 (8-*)-разрез 202-206

Теорема Кенига 418 --и Холла 417

- о максимальном потоке и минимальном разрезе 312, 313

-- пяти красках 79

Точка Штейнера 168, 169 Транзитивное замыкание графа 33 Турнир [tournament] 21

Хроматическое число [chromatic number] 75

--верхняя оценка 78

--нижняя оценка 77, 78

Цветок [blossom] 375-379

- крайний [outermost] 375

- срезание [shrinking] 375-379 центр графа 98-103

цепь альтернирующая [alternating path] 371

- аугментальная [augmenting path] 372, 372

- ориентированная (орцепь) [simple path] 14

- простая [elementary path] 14

- эйлерова см Эйлеров цикл цикл гамильтонов 17, 242-309

- ориентированный (орцикл) 17 -- матрица 225, 239

--мультицепной метод нахождения

253-259

-- сравнение методов поиска 259-262

- фундаментальный 220, 221

- эйлеров 227-240

Цикломатическое число [cyclomatic number] 217, 218

Число Бетти см Цикломатическое число

- внешнего разделения 100

- внутреннего разделения 100

- доминирования 43

- независимости [independence number] 43, 44