Теория графов
Автор(ы): | Кристофидес Н.
06.10.2007
|
Год изд.: | 1978 |
Описание: | В книге впервые в мировой литературе достаточно полно представлены разнообразные алгоритмы, связанные с нахождением структурных и числовых объектов из теории графов. В частности, подробно рассматриваются различные алгоритмы поиска решения в задаче коммивояжера! Кроме того, книга содержит большой фактический материал по исследованию потоков в сетях. Разнообразная тематика и строгое представление алгоритмов сочетается с доходчивостью изложения. Книга будет интересна широкому кругу специалистов, столкнувшихся с теорией графов и ее приложениями. |
Оглавление: |
Обложка книги.
Предисловие редактора перевода [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. Нахождение К кратчайших путей между двумя заданными вершинами [198] 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 2. Гамильтоновы циклы в графе [245] 3. Сравнение методов поиска гамильтоновых циклов [259] 4. Простая задача планирования [262] ЧАСТЬ II 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. Задача о покрытии [41б] 7. Задачи [417] 8. Список литературы [420] Приложение 1. Методы поиска, использующие дерево решений [422] 1. Принцип поиска, использующий дерево решений [422] 2. Некоторые примеры ветвления [424] 3. Типы поиска, использующего дерево решений [424] 4. Применение границ [426] 5. Функции ветвления [426] Предметный указатель [427] |
Формат: | djvu |
Размер: | 5177862 байт |
Язык: | RUS |
Рейтинг: | 147 |
Открыть: | Ссылка (RU) |