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

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

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




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

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

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

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



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

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


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




Теги: учебник по математике :: математика :: Алексеев :: Захарова