Элементы теории графов, Домнин Л.Н., 2007

Элементы теории графов, Домнин Л.Н., 2007.

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




Неориентированные деревья.
На рис. 3.1 даны три изображена одного и того же неориентированного дерева. Наиболее соответствует названию вариант в, по обычно при изображении деревьев используют варианты а и 6. Из рисунка становятся попятными термины корень и лист, употребляемые при рассмотрении подобных графов. Листом (висячей вершиной) называют вершину, степень которой равна 1, если она не рассматривается как корень. В качестве корпя в неориентированном дереве можно принять любую вершину.

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

Оглавление.
Предисловие.
1. Введение.
1.1. Определение графа.
1.2. Подграфы.
1.3. Виды графов.
1.4. Матрицы графов.
1.5. Диаметр, радиус и центр графа.
1.6. Ориентированные графы.
1.7. Маршруты, цепи и простые цепи.
2. Связность в орграфах.
2.1. Основные понятия.
2.2. Компоненты связности.
2.3. Конденсация орграфа.
2.4. Отыскание сильных компонент.
2.5. Матрицы достижимостей.
2.6. Получение матрицы достижимостей.
2.7. Алгоритм Уоршолла.
2.8. База графа.
3. Деревья.
3.1. Основные понятия.
3.2. Описание деревьев.
3.3. Задачи с деревьями.
3.3.1. Перечисление остовных деревьев.
3.3.2. Пересчет остовных деревьев.
3.4. Задача о кратчайшем остове графа.
3.4.1. Алгоритм Краскала.
3.4.2. Алгоритм Прима.
4. Пути и маршруты и графах.
4.1. Существование путей.
4.2. Пересчет маршрутов и путей.
4.3. Перечисление маршруток и путей.
4.4. Задачи о кратчайших путях.
4.4.1. Графы с дугами единичной длины.
1.4.2. Графы со взвешенными дугами (ребрами).
4.4.3. Ациклические орграфы.
5. Циклы.
5.1. Фундаментальные циклы и разрезы.
5.2. Эйлеровы циклы.
5.2.1. Определение и условия существовании.
5.2.2. Алгоритм поиска эйлерова цикла.
5.2.3. О количество эйлеровых графов.
5.2.4. Задача почтальона.
5.3. Гамильтоновы циклы.
5.3.1. Определение и условия существования.
5.3.2. Методы поиска гамильтоновых циклов.
5.4. Задача коммивояжёра.
5.4.1. Применение и методы решения задачи.
5.4.2. Метод ветвей и границ.
Список литературы.
Указатель обозначений.
Предметный указатель.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Элементы теории графов, Домнин Л.Н., 2007 - fileskachat.com, быстрое и бесплатное скачивание.

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


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




Теги: учебник по математике :: математика :: Домнин :: теория графов