Теория графов

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