Теория графов, Алгоритмы на графах, Дольников В.Л., Полякова О.П., 2003

Теория графов, Алгоритмы на графах, Дольников В.Л., Полякова О.П., 2003.

   В учебном пособии излагаются основы теории графов, приводятся примеры сведения прикладных задач к задачам теории графов и алгоритмы их решения.
Предназначено для студентов ЯрГУ, изучающих курс ”Теория графов” и ”Алгоритмы на графах”.




Независимые множества.
Независимое множество называется максимальным, если оно не является собственным подмножеством некоторого другого независимого множества. Максимальное по мощности независимое множество называется наибольшим. Ясно, что наибольшее независимое множество является максимальным. Обратное, в общем случае, неверно.

К отысканию наибольшего независимого множества вершин в графе сводится, например, известная задача о восьми ферзях, которую связывают с именем К. Гаусса: требуется так расставить на шахматной доске наибольшее число ферзей, чтобы они не атаковали друг друга.

ОГЛАВЛЕНИЕ.
1. Начальные понятия.
1.1. Основные определения.
1.2. Операции над графами.
1.3. Степени вершин графа.
1.4. Матрица смежности и матрица инцидентности.
Задачи и упражнения.
2. Связность.
2.1. Маршруты и связность.
2.2. Вершинная связность и реберная связность.
2.3. Двусвязные графы Задачи и упражнения.
3. Деревья.
3.1. Определение дерева.
3.2. Остов минимального веса.
Задачи и упражнения.
4. Независимые множества, клики, доминирующие множества.
4.1. Независимые множества.
4.2. Шенноновская емкость графов.
4.3. Задача. Рамсея. Функция неплотности.
4.4. Доминирование и покрытия.
4.5. Паросочетания.
4.6. Паросочетания в двудольном графе.
4.7. Паросочетания и покрытия.
4.8. Наибольшие паросочетания и задача о назначениях.
Задачи и упражнения.
5. Планарность.
5.1. Плоские и планарные графы.
5.2. Алгоритм укладки графа на плоскости.
Задачи и упражнения.
6. Обходы.
6.1. Эйлеровы графы.
6.2. Гамильтоновы графы.
6.3 Задача коммивояжера и понятие NP—полноты.
Задачи и упражнения.
7. Раскраски.
7.1. Правильная раскраска.
7.2. Оценки хроматического числа.
7.3. Раскраска ребер.
7.4. Раскраска планарных графов.
7.5. Проблема четырех красок.
Задачи и упражнения.
Список литературы.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Теория графов, Алгоритмы на графах, Дольников В.Л., Полякова О.П., 2003 - fileskachat.com, быстрое и бесплатное скачивание.

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


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




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