Учебное пособие. — М.: Изд-во РУДН, 2013. — 179 с. — ISBN
5-209-01493-2
В пособии излагаются основы теории графов и алгоритмов на графах.
Книга является продолжением курса дискретной математики: «Часть I.
Комбинаторика» и «Часть II. Математическая логика».
Теория графов является частью науки дискретной математики. Дискретная математика состоит из следующих разделов: комбинаторика, математическая логика, общая теория графов, теория множеств и общая алгебра, теория алгоритмов, теория автоматов и теория кодирования.
Подготовлено на кафедре «Системы телекоммуникаций». Предназначено для студентов I, II курсов математических и компьютерных специальностей высших учебных заведений. Содержание.
Интерактивное оглавление
Конспект лекций по дисциплине (всего 14 лекций):
Графы. Неориентированные графы: основные понятия; маршруты, цепи, циклы; связность; деревья и леса. Ориентированные графы: основные понятия; ориентированные маршруты, пути, контуры; сильная связность. Ориентированные деревья. Метрические характеристики графов. Матричное представление графов: матрица инцидентности для неорграфа, матрица смежности для неорграфа, матрица инцидентности для орграфа, матрица смежности для орграфа. Список смежности. Построение покрывающих деревьев. Алгоритм Краскала. Построение покрывающего дерева для связного графа. Построение минимального покрывающего дерева по алгоритму Краскала. Построение максимального покрывающего дерева по алгоритму Краскала. Построение минимального покрывающего дерева для связного взвешенного графа по алгоритму Прима. Построение максимального покрывающего дерева по алгоритму Прима. Поиск пути наименьшей длины в графе. Алгоритм Дейкстры. Эйлеровы графы. Алгоритм поиска эйлерова цикла в графе. Гамильтоновы графы. Сходство и различия гамильтоновых и эйлеровых графов. Достаточные условия существования гамильтоновых циклов. Способы поиска гамильтонова цикла. Алгоритм поиска гамильтонова цикла в графе. Поиск расстояния между всеми парами вершин. Алгоритм Уоршалла-Флойда. Задача построения транзитивного замыкания бинарного отношения. Алгоритм построения транзитивного замыкания бинарного отношения. Потоки. Условия существования потока. Увеличивающая цепь. Алгоритм поиска увеличивающей цепи. Увеличение потока вдоль найденной цепи по правилам. Потоки. Поиск максимального потока. Поиск потока минимальной стоимости. Задача почтальона для орграфов. Алгоритм поиска оптимального маршрута почтальона для орграфов. Фонды оценочных средств.
Словарь (глоссарий) основных терминов и понятий.
Методические указания для преподавателя, студента, слушателя.
Сборник задач и упражнений.
Лабораторный практикум по дисциплине.
Описание балльно-рейтинговой системы.
Вопросы для самопроверки и обсуждений по темам.
Задания для самостоятельной работы по темам.
Перечень рефератов и/или курсовых работ по темам.
Тестовые задания по темам (для текущего и промежуточного самоконтроля).
Тренинговые задания.
Перечень вопросов итоговой аттестации по курсу. Учебно-методический комплекс по дисциплине.
Литература © Российский университет дружбы народов, Издательство, 2013
© Э.Р. Зарипова, М.Г. Кокотчикова, 2013.
Теория графов является частью науки дискретной математики. Дискретная математика состоит из следующих разделов: комбинаторика, математическая логика, общая теория графов, теория множеств и общая алгебра, теория алгоритмов, теория автоматов и теория кодирования.
Подготовлено на кафедре «Системы телекоммуникаций». Предназначено для студентов I, II курсов математических и компьютерных специальностей высших учебных заведений. Содержание.
Интерактивное оглавление
Конспект лекций по дисциплине (всего 14 лекций):
Графы. Неориентированные графы: основные понятия; маршруты, цепи, циклы; связность; деревья и леса. Ориентированные графы: основные понятия; ориентированные маршруты, пути, контуры; сильная связность. Ориентированные деревья. Метрические характеристики графов. Матричное представление графов: матрица инцидентности для неорграфа, матрица смежности для неорграфа, матрица инцидентности для орграфа, матрица смежности для орграфа. Список смежности. Построение покрывающих деревьев. Алгоритм Краскала. Построение покрывающего дерева для связного графа. Построение минимального покрывающего дерева по алгоритму Краскала. Построение максимального покрывающего дерева по алгоритму Краскала. Построение минимального покрывающего дерева для связного взвешенного графа по алгоритму Прима. Построение максимального покрывающего дерева по алгоритму Прима. Поиск пути наименьшей длины в графе. Алгоритм Дейкстры. Эйлеровы графы. Алгоритм поиска эйлерова цикла в графе. Гамильтоновы графы. Сходство и различия гамильтоновых и эйлеровых графов. Достаточные условия существования гамильтоновых циклов. Способы поиска гамильтонова цикла. Алгоритм поиска гамильтонова цикла в графе. Поиск расстояния между всеми парами вершин. Алгоритм Уоршалла-Флойда. Задача построения транзитивного замыкания бинарного отношения. Алгоритм построения транзитивного замыкания бинарного отношения. Потоки. Условия существования потока. Увеличивающая цепь. Алгоритм поиска увеличивающей цепи. Увеличение потока вдоль найденной цепи по правилам. Потоки. Поиск максимального потока. Поиск потока минимальной стоимости. Задача почтальона для орграфов. Алгоритм поиска оптимального маршрута почтальона для орграфов. Фонды оценочных средств.
Словарь (глоссарий) основных терминов и понятий.
Методические указания для преподавателя, студента, слушателя.
Сборник задач и упражнений.
Лабораторный практикум по дисциплине.
Описание балльно-рейтинговой системы.
Вопросы для самопроверки и обсуждений по темам.
Задания для самостоятельной работы по темам.
Перечень рефератов и/или курсовых работ по темам.
Тестовые задания по темам (для текущего и промежуточного самоконтроля).
Тренинговые задания.
Перечень вопросов итоговой аттестации по курсу. Учебно-методический комплекс по дисциплине.
Литература © Российский университет дружбы народов, Издательство, 2013
© Э.Р. Зарипова, М.Г. Кокотчикова, 2013.