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