1. Элементы теории графов Введение в теорию графов: основные понятия и определения. Матричные представления графов. Маршруты, цепи, циклы. Нахождение связных компонент. Метрические характеристики графов. Подграфы. Операции над г

Вид материала

Лекции

Содержание Содержание курса Тема 2. Алгоритмы на графах Тема 3. Потоки в сетях Тема 2. Алгоритмы на графах Тема 3. Потоки в сетях Темы контрольных работ

Подобный материал:

• Программа вступительного экзамена в аспирантуру по специальностям 05. 13. 05 - "Элементы, 88.59kb.
• Спецкурс «Теория графов» пм 4 курс История возникновения и развития теории графов., 13.97kb.
• Задача является np-полной для кубических планарных графов, реберных графов, ориентированных, 39.45kb.
• Вопросы к экзамену, 14.82kb.
• «Применение информационный технологий в теории графов», 272.84kb.
• Программа дисциплины Комбинаторные алгоритмы Семестры, 18.74kb.
• Задание графов соответствием 9 > Матричное представление графов 10 Вопросы применения, 230.14kb.
• Спецкурс проходит по вторникам с 18: 30 до 19: 50 в ауд. 301 лк. Первая лекция состоится, 20.89kb.
• Технологический Институт Южного Федерального Университета e-mail: lbk@tsure ru Введение, 145.03kb.
• Лекция 12: Алгоритмы на графах и деревьях, 395.7kb.

ТЕория конечных графов

Кафедра систем телекоммуникаций, факультет физико-математических и естественных наук.

Обязательная дисциплина, привязанная к первому семестру второго курса.

Трудоемкость – 3 кредита, 2 часа лекций и 2 часа лабораторных занятий в неделю

Цель курса

Целью курса является изучение классической теории графов, а также применение методов теории графов в прикладных задачах. В процессе обучения студент учится оперировать основными характеристиками графов и составлять алгоритмы по основным темам дисциплины.
^

Содержание курса

Лекции

Тема 1. Элементы теории графов

Введение в теорию графов: основные понятия и определения. Матричные представления графов. Маршруты, цепи, циклы. Нахождение связных компонент. Метрические характеристики графов. Подграфы. Операции над графами. Двудольные графы. Поиск в ширину. Деревья. Эйлеровы графы. Гамильтоновы графы. Эйлеровы пути и циклы. Гамильтоновы пути и циклы. Связь между наличием в связном графе гамильтоновых циклов и длиной максимальных простых путей в нем. Нахождение кратчайших путей в ориентированном графе.

^ Тема 2. Алгоритмы на графах

Алгоритм Краскала. Алгоритм Прима. Алгоритм Дейкстры. Алгоритм нахождения эйлерова цикла в графе. Алгоритм построения кратчайшего пути от фиксированной вершины до всех остальных вершин в ориентированном графе, случай неотрицательных весов ребер.

^ Тема 3. Потоки в сетях

Прикладные модели и задачи, примеры применения методов теории графов. Оценки структурных компонент графа. Задача о максимальном потоке и о минимальном разрезе в сети. Максимальный поток в транспортной сети. Задача на нахождение «узких» мест в сети. Задача о потоке минимальной стоимости.

Лабораторные занятия

Тема 1. Введение в теорию графов

Разбор основных понятий и определений на неориентированных и ориентированных графах. Матрицы смежности и матрицы инцидентности для неориентированных и ориентированных графов. Поиск маршрутов, цепей и циклов для графов. Нахождение связных компонент в графе. Метрические характеристики графов. Эйлеровы графы. Эйлеровы пути и циклы. Нахождение кратчайших путей в ориентированном графе.

^ Тема 2. Алгоритмы на графах

Алгоритм Краскала. Алгоритм Прима. Алгоритм Дейкстры. Алгоритм нахождения эйлерова цикла в графе. Алгоритм построения кратчайшего пути от фиксированной вершины до всех остальных вершин в ориентированном графе, случай неотрицательных весов ребер. Построение матрицы связности (достижимости для графа). Алгоритм Уоршалла-Флойда.

^ Тема 3. Потоки в сетях

Прикладные модели и задачи. Оценка структурных компонент графа. Задача о максимальном потоке и о минимальном разрезе в сети. Максимальный поток в транспортной сети. Задача на нахождение «узких» мест в сети. Задача о потоке минимальной стоимости.

^

Темы контрольных работ

Промежуточный контроль знаний

Контрольная работа № 1. Нахождение метрических характеристик графа.

Типовые задачи

1. Найти эксцентриситет, диаметр и радиус графа.
   
2. Составить матрицу смежности и матрицу инцидентности для графа.
   
3. Построить минимальное покрывающее дерево для графа по алгоритму Краскала.
   

Контрольная работа № 2. Прикладные задачи на применение методов теории графов.

Типовые задачи

1. Задача на применение алгоритма Дейкстры.
   
2. Задача на применение алгоритма Уоршалла-Флойда.
   
3. Поиск эйлерова цикла в графе.
   

Итоговый контроль знаний

Контрольная работа № 3. Применение методов теории графов.

Теоретические вопросы по темам:

1. Операции над графами.
   
2. Алгоритмы на графах.
   
3. Потоки в сетях: Задача о максимальном потоке и о минимальном разрезе в сети. Задача о максимальном потоке в транспортной сети. Задача на узкие места. Задача о потоке минимальной стоимости.
   

Литература

Обязательная

1. Иванов Б.Н. «Дискретная математика. Алгоритмы и программы». // М.: Изд-во «Лаборатория базовых знаний», 2007.
   
2. Грэхем Р., Кнут Д., Паташник О. «Конкретная математика». // М.: "Мир", 1998.
   
3. Харари Ф. «Теория графов». // М.: "Мир", 2005.
   

Дополнительная

1. Ю.В. Гайдамака, К.Е. Самуйлов, Л.А. Севастьянов, С.С. Спесивов «Комбинаторика. Алгоритмы на графах». Учебно-методическое пособие. // М.: Изд-во РУДН, 2002.
   

Программу составила

Зарипова Эльвира Ринатовна,

старший преподаватель кафедры систем телекоммуникаций,

факультет физико-математических и естественных наук.