Рекомендуется для направления (ий) подготовки (специальности (ей))
080500 «Бизнес-информатика»
(указываютсякодинаименованиянаправления(ий)
подготовки (специальности (ей) и/или профилей (специализаций)
Квалификация (степень) выпускника бакалавр
(указывается квалификация (степень) выпускника в соответствии с ФГОС)
1. Цели и задачи дисциплины:
Основнойцельюосвоениядисциплиныявляется изучение классической теории конечных графов, а также применение методов теории конечных графов в прикладных задачах. Курс «Теория конечных графов» носит теоретический и практический характер.
Задачейдисциплиныявляется развитие навыков формализации и описания математических объектов, оперирование основными характеристиками графов и применение алгоритмов по основным темам дисциплины.
2. Место дисциплины в структуре ООП:
(указывается цикл, к которому относится дисциплина; формулируются требования к входным знаниям, умениям и компетенциям студента, необходимым для ее изучения; определяются дисциплины, для которых данная дисциплина является предшествующей)
Цикл, к которому относится дисциплина: вариативнаячасть профессионального циклаБ.3.
Требования к входным знаниям и умениям:необходимаматематическаяподготовкавпределахшкольнойпрограммы.
ЗнатьОсновныепонятияиметодытеориимножеств.
Уметь:Анализироватьвыводы,полученныеприрешениизадач. Дисциплины, для которых данная дисциплина является предшествующей: Моделинагиперграфах,Введениевуправлениеинфокоммуникациями,Проектированиекорпоративныхсистем,ПрикладныезадачиТМО. 3. Требования к результатам освоения дисциплины: Процесс изучения дисциплины «Теория конечных графов» направлен на формирование следующих компетенций: ОК: 1, ПК: 19, 20
(указываются в соответствии с ФГОС ВПО)
владеет культурой мышления, способен к обобщению, анализу, восприятию информации, постановке цели и выбору путей ее достижения (ОК-1)
использовать соответствующий математический аппарат и инструментальные средства для обработки, анализа и систематизации информации по теме исследования (ПК-19)
готовить научно-технические отчеты, презентации, научные публикации по результатам выполненных исследований (ПК-20)
В результате изучения дисциплины «Теория конечных графов» студент должен: Знать:
концепции дисциплины: Теория конечных графов.
основные законы теоретического исследования.
Уметь:
использовать основные законы теоретического исследования; решать прикладные задачи по дисциплине «Теория конечных графов»,
применять методы моделирования, теоретического и экспериментального исследования,
понимать и применять в исследовательской и прикладной деятельности современный математический аппарат
Владеть:
современным математическим аппаратом;
вычислительными средствами;
базовыми математическими знаниями.
4. Объем дисциплины и виды учебной работы
Общая трудоемкость дисциплины составляет ____4_______ зачетных единиц.
Вид учебной работы
Всего часов
Семестры
3
Аудиторные занятия (всего)
54
54
-
В том числе:
-
Лекции
36
36
-
Практические занятия (ПЗ)
-
-
-
Семинары (С)
-
-
-
Лабораторные работы (ЛР)
18
18
-
Самостоятельная работа (всего)
90
90
-
В том числе:
-
-
-
Курсовой проект (работа)
-
-
-
Расчетно-графические работы
-
-
-
Реферат
-
-
-
Другие виды самостоятельной работы
-
-
-
Самостоятельная проработка дополнительного материала
90
90
-
Вид промежуточной аттестации (зачет, экзамен)
экзамен
-
Общая трудоемкость час
144
144
-
зач. ед.
4
4
-
5. Содержание дисциплины
5.1. Содержание разделов дисциплины
№ п/п
Наименование раздела дисциплины
Содержание раздела
1.
Элементы теории графов
Введение в теорию графов: основные понятия и определения. Матричные представления графов. Маршруты, цепи, циклы. Нахождение связных компонент. Метрические характеристики графов. Подграфы. Операции над графами. Двудольные графы. Поиск в ширину. Деревья. Эйлеровы графы. Гамильтоновы графы. Эйлеровы пути и циклы. Гамильтоновы пути и циклы. Связь между наличием в связном графе гамильтоновых циклов и длиной максимальных простых путей в нем. Нахождение кратчайших путей в ориентированном графе.
2.
Алгоритмы на графах
Алгоритм Краскала. Алгоритм Прима. Алгоритм Дейкстры. Алгоритм нахождения эйлерова цикла в графе. Алгоритм построения кратчайшего пути от фиксированной вершины до всех остальных вершин в ориентированном графе, случай неотрицательных весов ребер.
3.
Потоки в сетях
Прикладные модели и задачи, примеры применения методов теории графов. Оценки структурных компонент графа. Задача о максимальном потоке и о минимальном разрезе в сети. Максимальный поток в транспортной сети. Задача на нахождение «узких» мест в сети. Задача о потоке минимальной стоимости.
5.2 Разделы дисциплины и междисциплинарные связи с обеспечиваемыми (последующими) дисциплинами
№ п/п
Наименование обеспе-чиваемых (последую-щих) дисциплин
№ № разделов данной дисциплины, необходимых для изучения обеспечиваемых (последующих) дисциплин
1
2
3
1.
Модели на гиперграфах
+
+
+
2.
Введение в управление инфокоммуникациями
+
+
+
3.
Моделирование информационных процессов
+
4.
Прикладные задачи ТМО
+
+
5.
Курсовая работа
+
+
+
5.3. Разделы дисциплин и виды занятий
№ п/п
Наименование раздела дисциплины
Лекц.
Практ.
зан.
Лаб.
зан.
Семин
СРС
Все-го
час.
1.
Элементы теории графов
12
0
6
0
30
48
2.
Алгоритмы на графах
12
0
6
0
30
48
3.
Потоки в сетях
12
0
6
0
30
48
36
18
90
144
6. Лабораторный практикум
№ п/п
№ раздела дисциплины
Наименование лабораторных работ
Трудо-емкость
(час.)
1.
Элементы теории графов
Разбор основных понятий и определений на неориентированных и ориентированных графах. Матрицы смежности и матрицы инцидентности для неориентированных и ориентированных графов. Поиск маршрутов, цепей и циклов для графов. Нахождение связных компонент в графе. Метрические характеристики графов. Эйлеровы графы. Эйлеровы пути и циклы. Нахождение кратчайших путей в ориентированном графе
6
2.
Алгоритмы на графах
Алгоритм Краскала. Алгоритм Прима. Алгоритм Дейкстры. Алгоритм нахождения эйлерова цикла в графе. Алгоритм построения кратчайшего пути от фиксированной вершины до всех остальных вершин в ориентированном графе, случай неотрицательных весов ребер. Построение матрицы связности (достижимости для графа). Алгоритм Уоршалла-Флойда.
6
3.
Потоки в сетях
Прикладные модели и задачи. Оценка структурных компонент графа. Задача о максимальном потоке и о минимальном разрезе в сети. Максимальный поток в транспортной сети. Задача на нахождение «узких» мест в сети. Задача о потоке минимальной стоимости.
9. Учебно-методическое и информационное обеспечение дисциплины:
а) основная литература
Гайдамака Ю.В., Зарипова Э.Р., Кокотчикова М.Г., Севастьянов Л.А. «Лекции по дискретной математике. Часть II. Комбинаторика. Теория конечных графов». Учебное пособие. // М.: Изд-во РУДН, 2008.
Харари Фрэнк.Теория графов / Харари Фрэнк ; Пер. с англ. В.П.Козырева; Под ред. Г.П.Гаврилова. - 4-е изд. - М. : URSS : Либроком, 2009. - 296 с.
Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. «Лекции по теории графов». Изд.2, испр., Изд-во Либроком, 2009.
Муромцев В.В. «Некоторые алгоритмы на графах». Учебное пособие, Белгород: Изд. БелГТАСМ, 2000.- 64 с.
б) дополнительная литература
Зыков А. А. Основы теории графов. — М.: «Вузовская книга», 2004. — С. 664
Кирсанов М.Н. «Графы в MAPLE» Пособие по дискретной математике для студентов университетов. М: Физматлит, 2007.
в) программное обеспечение Maple,MatLab,SciLab,MathCad,Mathematica
г) базы данных, информационно-справочные и поисковые системы____________________http://vuz.exponenta.ru/PDF/book/GrMaple.pdf
ауд. 110: проектор DMS800 с интерактивной доской Board 1077, ноутбук Toshiba Satellite 17/300GB Intel Core2 2.4 GHz (10 шт.)
ауд. 114: проектор DMS800 с интерактивной доской Board 1077ноутбук Toshiba Satellite 17/300GB Intel Core2 2.4 GHz (10 шт.)
ауд. 116: проектор DMS800 с интерактивной доской Board 1077, HP xw7800, Intel Core2 2.4 GHz (8 шт. )
11. Методические рекомендации по организации изучения дисциплины:
На освоение дисциплины отводится 1 семестр. В качестве итогового контроля знаний предусмотрен экзамен.
Для текущего контроля успеваемости и промежуточной аттестации студентов рекомендуется использовать вопросы и задания подобные перечисленным ниже:
Типовые задачи для промежуточного контроля знаний:
Найти эксцентриситет, диаметр и радиус графа.
Составить матрицу смежности и матрицу инцидентности для графа.
Построить минимальное покрывающее дерево для графа по алгоритму Краскала.
Задача на применение алгоритма Дейкстры.
Задача на применение алгоритма Уоршалла-Флойда.
Поиск эйлерова цикла в графе.
Типовые вопросы для итогового контроля знаний:
Неориентированный граф. Определение. Смежность ребер и вершин. Инцидентность. Изоморфизм.
Теорема о четности вершин в конечном графе. Определения полного графа и подграфа.
Определение маошрута, замкнутого маршрута. Определение цепи и простой цепи. Определение дерева. Теорема о количестве ребер в дереве с n вершинами.
Связный неориентированный граф. Теорема о связности графа.
Определение орграфа. Смежность в орграфе. Положительная и отрицательная инцидентность в орграфе. Положительная и отрицательная степени вершин в орграфе.
Определение пустого графа. Определение изолированной вершины. Определение ормаршрута и замкнутого ормаршрута. Определение пути и простого пути. Определение контура.
Определение сильносвязного графа. Определение орграфа. Определение симметричного и смешанного графов.
Определение эксцентриситета, диаметра и радиуса в графе. Центр графа.
Матрица смежности и инцидентности для неорграфа. Список смежности. Матрица весов.
Матрица смежности и инцидентности для орграфа.
Теорема о числе ормаршрутов длины n между двумя вершинами орграфа.
Построение минимального покрывающего дерева по алгоритму Краскала. Алгоритм.
Построение максимального покрывающего дерева по алгоритму Краскала. Алгоритм.
Определение псевдографа и мультиграфа. Определение плоского графа.
Построение минимального покрывающего дерева по алгоритму Прима. Алгоритм.
Построение максимального покрывающего дерева по алгоритму Прима. Алгоритм
Поиск маршрута и наименьшей длины по алгоритму Дейкстры. Алгоритм.
Задача о кенигсбергских мостах. Определение эйлерова цикла и эйлерова графа. Определение эйлерова пути и способ получения эйлерова пути из эйлерова цикла.
Теорема о четности степеней в эйлеровом графе.
Поиск эйлерова цикла в графе. Алгоритм.
Поиск минимальных расстояний между всеми парами вершин по алгоритму Уоршалла-Флойда. Алгоритм.
Сравнение алгоритмов Дейкстры и Уоршалла-Флойда. Сходства и различия алгоритмов.
Задача построения транзитивного замыкания бинарного отношения. Определение бинарного отношения. Определение транзитивного замыкания. Матрица достижимости (связности).
Построение транзитивного замыкания для графа. Алгоритм.
Особенности i-той строки и i-столбца для Алгоритма Уоршалла-Флойда. Доказательство.
Особенности i-той строки и i-столбца для Алгоритма поиска транзитивного замыкания. Доказательство.
Определение потока в графе. Условия существования потока в графе. Правила расскрашивания дуг графа для поиска увеличивающей цепи. Определение прямых и обратных дуг.
Увеличение потока в графе по увеличивающей цепи. Алгоритм.
Поиск максимального потока в графе. Алгоритм.
Поиск потока минимальной стоимости. Алгоритм.
Поиск оптимального маршрута почтальона для орграфа. Алгоритм.
Определение гамильтонова цикла и гамильтоновой цепи.
Гамильтоновы и эйлеровы графы. Сходства и различия гамильтонова и эйлерова циклов.
Три достаточных критерия существования гамильтоновых циклов в неорграфе.
Поиск гамильтонова цикла в орграфе. Алгоритм с упрощением
Программа дисциплины «теория графов» Таким образом, теория графов стала существенной частью математического аппарата кибернетики, языком дискретной математики. В значительной...
