Теория графов, Часть 1, Буркатовская Ю.Б., 2014

Теория графов, Часть 1, Буркатовская Ю.Б., 2014.

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




Поиск k минимальных путей.
В предыдущем подразделе рассмотрена задача поиска минимальных путей между вершинами графа, при этом на пути не накладываются никакие дополнительные условия. Но во многих приложениях требуется минимальный путь из обладающих какими-либо дополнительными свойствами (например, проходить через определенное подмножество вершин или ребер, содержать определенное число дуг и т. д.). Можно рассматривать подобную задачу как задачу поиска минимального пути с дополнительными ограничениями, но в ряде случаев это приводит к значительному увеличению вычислительных затрат. Другой подход состоит в том, чтобы найти некоторое множество минимальных путей и выбрать их них те, которые обладают необходимыми свойствами.

Заметим, что k минимальных путей не обязательно, вообще говоря, будут простыми. Задача поиска k минимальных путей без требования их простоты является значительно менее сложной, и для ее решения достаточно модифицировать изученные ранее алгоритмы. Модификация будет состоять в том, что операции сложения и сравнения чисел заменяются на операции сложения и сравнения векторов (т. е. наборов чисел), т. к. теперь мы имеем дело с весами нескольких путей.

ОГЛАВЛЕНИЕ.
Введение.
1. Основные понятия теории графов.
1.1. Определение графов и родственных объектов.
1.2. Смежность вершин и ребер.
1.3. Подграфы.
1.4. Типы графов.
1.5. Изоморфизм графов.
1.6. Операции над графами.
1.7. Способы задания графов.
1.8. Упражнения.
2. Связность графов.
2.1. Маршруты, цепи, циклы.
2.2. Расстояния в графе.
2.3. Связность неориентированных графов.
2.4. Оценка числа ребер в графе.
2.5. Деревья.
2.6. Система фундаментальных циклов.
2.7. Система фундаментальных разрезов.
2.8. Теорема Менгера.
2.9. Связность орграфов.
2.10. Упражнения.
3. Поиск путей в графе.
3.1. Стратегии обхода графа.
3.2. Поиск кратчайших путей.
3.3. Поиск минимальных путей.
3.3.1. Поиск минимальных путей от заданной вершины.
3.3.2. Поиск минимальных путей между всеми парами вершин.
3.4. Поиск к минимальных путей.
3.4.1. Пространство Rk.
3.4.2. Поиск k произвольных минимальных путей от заданной вершины.
3.4.3. Поиск k произвольных минимальных путей между всеми парами вершин.
3.4.4. Поиск k простых минимальных путей от заданной вершины
3.5. Поиск путей с заданными свойствами.
3.6. Упражнения.
4. Задачи размещения.
4.1. Расстояния во взвешенном графе.
4.2. Поиск центров графа.
4.3. Поиск медиан графа.
4.4. Обобщения задач размещения.
4.5. Поиск кратных центров.
4.6. Поиск кратных медиан.
4.7. Упражнения.
5. Деревья.
5.1. Свободные деревья.
5.2. Задача о соединении городов.
5.3. Ориентированные, упорядоченные и бинарные деревья.
5.4. Построение ориентированного дерева и леса.
5.5. Способы задания деревьев.
5.6. Деревья сортировки.
5.6.1. Выровненные деревья.
5.6.2. Сбалансированные деревья.
5.6.3. Красно-черные деревья.
5.7. Упражнения.
Приложение. Поиск покрытий булевой матрицы.
П1. Поиск всех безызбыточных покрытий.
П2. Поиск минимальных и кратчайших покрытий с использованием КНФ функции покрытия.
П3. Поиск минимальных и кратчайших покрытий методом ветвей и границ.
Список литературы.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Теория графов, Часть 1, Буркатовская Ю.Б., 2014 - fileskachat.com, быстрое и бесплатное скачивание.

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


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




Теги: учебник по математике :: математика :: Буркатовская :: подграфы :: теорема Менгера