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

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




Сильно связные графы и компоненты графа.
Ориентированный граф называется сильно связным или сильным, если для любых двух различных вершин xi и xj существует по крайней мере один путь, соединяющий xi с xj. Это определение означает также, что любые две вершины такого графа взаимно достижимы.

Ориентированный граф называется односторонне связным или односторонним, если для любых двух различных вершин xi и xj существует по крайней мере один путь из xi в хj или из хj в xi (или оба одновременно).
Ориентированный граф называют слабо связным или слабым, если для любых двух различных вершин графа существует по крайней мере один маршрут, соединяющий их.

Если для некоторой пары вершин орграфа не существует маршрута, соединяющего их, то такой орграф называется несвязным.

Оглавление.
Предисловие редактора перевода.
Предисловие.
Глава 1. Введение.
1. Графы. Определение.
2. Пути и маршруты.
3. Петли, ориентированные циклы и циклы.
4. Степени вершины.
5. Подграфы.
6. Типы графов.
7. Сильно связные графы и компоненты графа.
8. Матричные представления.
9. Задачи.
10. Список литературы.
Глава 2. Достижимость и связность.
1. Введение.
2. Матрица достижимостей и контрадостижимостей.
3. Нахождение сильных компонент.
4. Базы.
5. Задачи, связанные с ограниченной достижимостью.
6. Задачи.
7. Список литературы.
Глава 3. Независимые и доминирующие множества. Задача о покрывающих множествах.
1. Введение.
2. Независимые множества.
3. Доминирующие множества.
4. Задача о наименьшем покрытии.
5. Приложения задачи о покрытии.
6. Задачи.
7. Список литературы.
Глава 4. Раскраски.
1. Введение.
2. Некоторые теоремы и оценки, относящиеся к хроматическим числам.
3. Точные алгоритмы раскраски.
4. Приближенные алгоритмы раскрашивания.
5. Обобщения и приложения.
6. Задачи.
7. Список литературы.
Глава 5. Размещение центров.
1. Введение.
2. Разделения.
3. Центр и радиус.
4. Абсолютный центр.
5. Алгоритмы нахождения абсолютных центров.
6. Кратные центры (р-центры).
7. Абсолютные р-центры.
8. Алгоритм нахождения абсолютных р-центров.
9. Задачи.
10. Список литературы.
Глава 6. Размещение медиан в графе.
1. Введение.
2. Медиана графа.
3. Кратные медианы (р-медианы) графа.
4. Обобщенная р-медиана графа.
5. Методы решения задачи о р-медиане.
6. Задачи.
7. Список литературы.
Глава 7. Деревья.
1. Введение.
2. Построение всех остовных деревьев графа.
3. Кратчайший остов (SST) графа.
4. Задача Штейнера.
5. Задачи.
6. Список литературы.
Глава 8. Кратчайшие пути.
1. Введение.
2. Кратчайший путь между двумя заданными вершинами s и t.
3. Кратчайшие пути между всеми парами вершин.
4. Обнаружение циклов отрицательного веса.
5. Нахождение К кратчайших путей между двумя заданными вершинами.
6. Кратчайший путь между двумя заданными вершинами. в ориентированном ациклическом графе.
7. Задачи, близкие к задаче о кратчайшем пути.
8. Задачи.
9. Список литературы.
Глава 9. Циклы, разрезы и задача Эйлера.
1. Введение.
2. Цикломатическое число и фундаментальные циклы.
3. Разрезы.
4. Матрицы циклов и разрезов.
5. Эйлеровы циклы и задача китайского почтальона.
6. Задачи.
7. Список литературы.
Глава 10. Гамильтоновы циклы, цепи и задача коммивояжера.
1. Введение.
ЧАСТЬ I.
2. Гамильтоновы циклы в графе.
3. Сравнение методов поиска гамильтоновых циклов.
4. Простая задача планирования.
ЧАСТЬ II.
5. Задача коммивояжера.
6. Задача коммивояжера и задача о кратчайшем остове.
7. Задача коммивояжера и задача о назначениях.
8. Задачи.
9. Список литературы.
10. Приложение.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Теория графов, Алгоритмический подход, Кристофидес Н., 1978 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать pdf
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.Купить эту книгу


Скачать - pdf - Яндекс.Диск.




Теги: учебник по математике :: математика :: Кристофидес