Теория графов, Алексеев В.Е., Захарова Д.В., 2012

Теория графов, Алексеев В.Е., Захарова Д.В., 2012.

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

Теория графов, Алексеев В.Е., Захарова Д.В., 2012


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

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

Очередной шаг обхода начинается с выбора какой-либо вершины x из множества открытых, она становится активной. Если среди инцидентных ей ребер имеются неисследованные, то выбирается такое ребро (х, у). Если вершина у новая, то она посещается, ребро (x, у) при этом классифицируется как прямое. Если же у не новая, то ребро (x, у) считается обратным (ведущим в уже посещенную вершину.

Оглавление.
Предисловие.
1. Начальные понятия.
Определение графа.
Способы задания графов.
Окрестности и степени.
Некоторые специальные графы.
Изоморфизм.
Подграфы.
Операции над графами.
Пути, циклы, связность.
Расстояния и метрические характеристики.
Графы пересечений.
Задачи.
2. Перечисление графов.
Помеченные графы.
Непомеченные графы.
Задачи.
3. Важнейшие классы графов.
Деревья.
Двудольные графы.
Планарные графы.
Задачи.
4. Методы обхода графа.
Поиск в ширину.
Поиск в глубину.
Задачи.
5. Циклы.
Эйлеровы циклы.
Гамильтоновы циклы.
Пространство циклов.
Задачи.
6. Независимые множества, клики, вершинные покрытия.
Задачи.
7. Паросочетания.
Паросочетания и реберные покрытия.
Метод увеличивающих путей.
Паросочетания в двудольных графах.
Независимые множества в двудольных графах.
Задачи.
8. Раскраски.
Раскраска вершин.
Раскраска ребер.
Задачи.
9. Оптимальные каркасы и пути.
Алгоритм Прима.
Алгоритм Краскала.
Кратчайшие пути.
Задачи.
10. Потоки.
Задачи.
Литература.



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

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



Скачать - pdf - Яндекс.Диск.
Дата публикации:





Теги: :: :: ::


Следующие учебники и книги:
Предыдущие статьи:


 


 

Книги, учебники, обучение по разделам




Не нашёл? Найди:





2020-02-21 09:37:18