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

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

blank
blank
blank
Красота
blank
Кристофидес Н. — Теория графов. Алгоритмический подход.
Кристофидес Н. — Теория графов. Алгоритмический подход.



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



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


Название: Теория графов. Алгоритмический подход.

Автор: Кристофидес Н.

Аннотация:

В книге впервые в мировой литературе достаточно полно представлены разнообразные алгоритмы, связанные с нахождением структурных и числовых характеристик объектов из теории графов. В частности, подробно рассматриваются различные алгоритмы поиска решения в задаче коммивояжера. Кроме того, книга содержит большой фактический материал по исследованию потоков в сетях. Многочисленные примеры иллюстрируют работу конкретных алгоритмов. Приводятся оценки сложности соответствующих процедур. Разнообразная тематика и строгое представление алгоритмов сочетаются с доходчивостью изложения.
Книга будет интересна широкому кругу специалистов, сталкивающихся с теорией графов и ее приложениями. Она доступна студентам университетов и втузов соответствующих специальностей.


Язык: ru

Рубрика: Математика/Алгебра/Комбинаторика/

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

ed2k: ed2k stats

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

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

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

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