Дискретная математика. Основы теории графов: учеб. пособие для студентов, обучающихся по направлениям подготовки 075000-"Специальности в обл. информ. безопасности", , 654600 (код по ОКСО 230100)-"Информатика и вычисл. техника"

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