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