Теория графов (Кристофидес Н.)

Теория графов

Автор(ы):Кристофидес Н.
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
Рейтинг: 383 Рейтинг
Открыть: Ссылка (RU)