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

Description

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