Дискретная математика. Основы теории графов

Красноярск: ИПЦ КГТУ, 2005. - 82 с. - ISBN 5-7636-0708-2
Рассмотрена теория графов, предлагающая большой набор алгоритмов для программистов.
Приведена система специальных терминов и обозначений, представляющая собой удобный математический аппарат для формализованной постановки множества задач на дискретных структурах.
Предназначено для студентов направлений подготовки специалистов 075000 - «Специальности в области информационной безопасности (075200), 654600 - «Информатика и вычислительная техника» (специальности 220100-220400), бакалавров и магистров направлении 552800 - «Информатика и вычислительная техника».СодержаниеВведение
Основные понятия и определения
Понятие графа
Способы представления графов
Две теоремы о свойствах степеней вершин
Маршруты, цепи, циклы. Связность графа
Расстояния в графах
Части графа и операции над графами
Графы и бинарные отношения
Изоморфизм графов
Контрольные вопросы и задачи
Задачи о маршрутах
Эйлеровы циклы и цепи
Задачи в лабиринтах и обходы графов
Нахождение кротчайших путей
Контрольные вопросы и задачи
Задачи о деревьях
Деревья и их свойства
Бинарные деревья и способы нумерации их вершин
Каркасные деревья
Контрольные вопросы и задачи
Задачи о раскрасках
Графы с помеченными вершинами и задачи о раскраска
Проблема четырёх красок
Задачи с двудольными графами
Двудольные графы
Паросочетания в двудольных графах
Задачи на ориентированных графах
Особенности ориентированных графов
Задача о максимальном потоке
Применение графов для анализа программ
Анализ основных алгоритмов на графах
Базисные алгоритмы
Алгоритм Прима
Нахождение кратчайших путей
Заключение
Библиографический список