Теория графов

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ТЮМЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

.

ТЕОРИЯ ГРАФОВ

Учебно-методический комплекс

Рабочая программа для студентов специальности 090301.65

«Компьютерная безопасность»

Тюмень 2008

1.  Пояснительная записка

1.1. Цели и задачи дисциплины

Дисциплина «Теория графов» ставит своей целью ознакомление студентов с важнейшими разделами теории графов и ее приложениями. К задачам курса относятся: ознакомление студентов с фундаментальными понятиями теории графов для последующего свободного их использования, изучение современной проблематики теории графов, усвоение постановок задач теории графов и методов их решения, овладение основными теоретико-графовыми алгоритмами, применение графовых моделей к различным областям науки.

1.2. Требования к уровню освоения содержания дисциплины

В результате изучения дисциплины студенты должны

иметь представление:

·  о месте и роли теории графов в системе математических наук;

знать:

·  основные методы и алгоритмы теории графов, связанные с моделированием и оптимизацией систем различной природы.

уметь:

·  употреблять специальную математическую символику для выражения количественных и качественных отношений между объектами;

·  решать оптимизационные задачи на графах.

иметь навыки:

·  применения языка и средств теории графов;

·  решения теоретико-графовых задач.

2.  Объем дисциплины и виды учебной работы

Вид занятий	Всего часов	Семестры
5
Общая трудоемкость	100	100
Аудиторные занятия	54	54
Лекции	36	36
Лабор. занятия	18	18
Самостоятельная работа	46	46
Контрольные работы	+
Вид итогового контроля	экзамен

3.  Тематический план изучения дисциплины

Тема	Лекции	Лаборат.	Самост.	Контроль
Введение	2
Деревья	4	2	4
Обходы. Элементы цикломатики	4	2	6
Раскраски	4	2	4
Метрические характеристики графов и экстремальные задачи	6	3	8
Глобальный анализ графов. Алгоритмы на графах.	6	4	10	К. р.
Перечислительные вопросы теории графов	6	3	6
Приложения графов для задач программирования	4	2	8	К. р.
Всего:	36	18	46

4.  Содержание программы курса по темам

1.  Введение. Основные понятия теории графов. Типы графов. Цепи, циклы, связность. Изоморфизм и инварианты. Способы задания графов. Некоторые свойства матриц смежности, инцидентности и степеней графов.

2.  Деревья. Свойства деревьев. Матричная теорема Кирхгофа о деревьях. Поиск минимального (максимального) остовного леса в графе.

3.  Обходы. Элементы цикломатики. Эйлеровы графы. Критерий эйлеровости связного графа. Пространство четных подграфов и множество фундаментальных циклов. Цикломатическое число. Гамильтоновы графы. Признак Хватала гамильтоновости графа.

4.  Раскраски. Вершинная раскраска графов. Критерий Кенига двураскрашиваемости графа. Оценки для хроматического числа. Хроматический многочлен графа. Реберная раскраска графов. Теорема Визинга.

5.  Метрические характеристики графов и экстремальные задачи. Независимость и покрытия. Оценки для числа независимости графа. Связь между числом независимости и числом вершинного покрытия графа. Связь между числом независимости графа и кликовым числом дополнительного графа. Связь между числом паросочетания и числом реберной независимости (теорема Галлаи). Числа вершинной и реберной связности. Понятие k-связного графа. Теорема о числе общих вершин в k-компонентах графа. Сепараторы и разрезы. Теорема Менгера. Теорема Холла.

6.  Глобальный анализ графов. Алгоритмы на графах. Поиск в глубину и в ширину в графе. Топологическая сортировка вершин бесконтурного орграфа. Задача о кратчайшем пути. Алгоритмы Форда-Беллмана и Дейкстры. Задача о расстояниях между всеми парами вершин графа. Алгоритм Флойда. Транзитивное замыкание. Алгоритм Уоршалла. Алгоритм построения наибольшего паросочетания и наименьшего вершинного покрытия.

7.  Перечислительные вопросы теории графов. Число помеченных простых графов и орграфов. Экспоненциальные производящие функции и трактовка операций над ними. Лемма о пересчете помеченных графов. Асимптотика числа связных помеченных графов. Число помеченных деревьев (теорема Кэли). Утверждение о производящей функции для помеченных блоков.

8.  Приложения графов для задач программирования. Графы как модели программ, процессов, информационных структур.

5.  Темы лабораторных работ, практических занятий и методические указания к их проведению

1.  Введение. Основные понятия теории графов. Типы графов. Подграфы. Матричное представление графов. Операции над графами.

2.  Деревья: основные понятия. Алгоритмы Краскала и Прима построения кратчайшего остова взвешенного графа.

3.  Обходы. Элементы цикломатики Определение эйлеровых и гамильтоновых циклов графа и использование данных задач в приложениях. Алгоритм Флёри. Решение задачи коммивояжера и его прикладное значение. Метод ветвей и границ.

4.  Раскраски Алгоритмы раскраски графа. Решение прикладных задач, сводящихся к задаче о раскраске.

5.  Метрические характеристики графов и экстремальные задачи. Достижимость и связность. Определение компонент связности неорграфов и сильных компонент орграфов. Независимость и покрытия.

6.  Глобальный анализ графов. Алгоритмы на графах. Поиск в глубину и в ширину в графе. Задача о кратчайшем пути. Алгоритмы Форда-Беллмана и Дейкстры. Задача о расстояниях между всеми парами вершин графа. Алгоритм Флойда. Транзитивное замыкание. Алгоритм Уоршалла.

7.  Перечислительные вопросы теории графов. Число помеченных простых графов и орграфов. Экспоненциальные производящие функции и трактовка операций над ними

8.  Приложения графов для задач программирования Представление графов с помощью динамических структур. Списки смежности. Ортогональные списки смежности. Структура Вирта. Модифицированная структура Вирта.

6.  Темы самостоятельных работ

1.  Реализовать граф как класс на основе структуры Вирта. Методы: добавление и удаление вершины; добавление и удаление ребра (дуги); ориентирование (неориентирование). Реализовать процедуры преобразования структуры Вирта во все динамические и матричные (смежность, инцидентность, достижимость) структуры. Реализовать интерфейс для всех представлений.

2.  С помощью обхода в глубину реализуйте алгоритм, который выясняет, можно ли так ориентировать рёбра связного неориентированного графа, чтобы получить сильно связный ориентированный граф.

3.  Граф называется двудольным, если можно разбить множество его вершин на два подмножества так, чтобы каждое ребро соединяло вершины из разных подмножеств. Граф является двудольным тогда и только тогда, когда все его циклы имеют четную длину. Проверьте при помощи данного утверждения, является ли заданный граф двудольным.

4.  Компонентой сильной связности в ориентированном графе называется такой его подграф, в котором любые две вершины взаимно достижимы и который не содержится в другом подграфе, удовлетворяющем этому условию. Постройте компоненты сильной связности для заданного ориентированного графа.

5.  Задан орграф G с неотрицательными весами, заданными матрицей A[u, v]. Найдите кратчайший путь от источника S до выделенной вершины T. Для этого найти по алгоритму Дейкстры расстояния D[v] от S до прочих вершин графа. Затем найти вершину V, такую, что D[t]=D[v]+A[v, t]. Это предпоследняя вершина пути. Предыдущая вершина пути u ищется из условия D[v]=D[u]+D[u, v] и т. д. до тех пор, пока не найдется первая вершина пути.

6.  Напишите программу, решающую следующую задачу: Построить минимальный остов графа G. Найти новый минимальный остов, если добавить к графу G новую вершину и инцидентные ей рёбра. (Реализовать оба алгоритма: Крускала и Прима).

7.  Сформулируем задачу, которая называется задачей китайского почтальона: Ребрам графа G приписаны положительные веса. Требуется найти цикл, проходящий через каждое ребро графа G по крайней мере один раз и такой, что для него общий вес (а именно сумма величин nj*c(aj), где числа nj показывают, сколько раз проходилось ребро aj, а c(aj) - вес ребра) минимален. Очевидно, что если граф G содержит эйлеров цикл, то любой такой цикл будет оптимальным, так как каждое ребро проходится только один раз и вес этого цикла равен тогда

Напишите программу, решающую задачу китайского почтальона для случая, когда граф обладает эйлеровым циклом.

8.  Написать программу для решения задачи коммивояжёра, используя Метод ветвей и границ.

7.  Контрольные вопросы к экзамену (зачету)

1.  Граф. Ориентированный граф. Неориентированный граф. Смежность и инцидентность. Способы задания графа. Матрицы графа. Степени вершины.

2.  Подграф. Часть графа. Виды графов. Изоморфизм графов. Теорема об изоморфизме графов.

3.  Маршруты в ориентированных и неориентированных графах. Связность. Достижимость.

4.  Дерево. Основные свойства деревьев. Ориентированное дерево. Бинарные деревья. Остов.

5.  Задача о построении кратчайшего остовного дерева. Алгоритм Прима. Проблема Штейнера.

6.  Задача о построении дерева кратчайших расстояний. Алгоритм Дейкстры.

7.  Задача о построении матрицы кратчайших расстояний. Алгоритм Флойда.

8.  Независимое множество вершин графа. Вершинная раскраска. Правильная раскраска. Хроматическое число графа. Доказать теорему о 5 красках.

9.  Эйлеров путь. Эйлеров граф. Алгоритм построения эйлерова пути в эйлеровом графе. Критерий эйлеровости графов.

10.  Гамильтонов граф. Теорема Дирака.

11.  Задача коммивояжёра. Метод ветвей и границ.

12.  Представление графов с помощью списков смежности. Описание типа.

13.  Представление графов с помощью структуры Вирта. Описание типа.

14.  Обход графа в глубину. Рекурсивная процедура обхода графа в глубину для графа, представленного в памяти структурой Вирта. Нерекурсивный алгоритм.

15.  Обход графа в ширину. Процедура нерекурсивного обхода графа в ширину для графа, заданного структурой Вирта.

16.  Связность. Использование обхода графа в глубину для нахождения всех его связных компонент (граф моделируется структурой Вирта).

7.  Литература

1.  Теория графов. - М.:Мир, 197с.

2.  Введение в теорию графов. - М.:Мир,197с.

3.  Комбинаторные алгоритмы. Теория и практика. - М.:Мир,198с.

4.  Графы, сети и алгоритмы. - М.:Мир, 198с.

5.  Алгоритмы оптимизации на сетях и графах. - М.: Мир, 19с.

6.  Евстигнеев теории графов в программирова-нии. - М.:Наука, 19с.

7.  Новиков математика для программистов. - СПб.:Питер, 20с.

Дополнения и изменения к программе на учебный год

В рабочую учебную программу по дисциплине «Теория графов» для специальности «Компьютерная безопасность» вносятся следующие изменения:

1.  Добавлена балльно-рейтинговая система оценки успеваемости студентов;

2.  Внесены изменения в список литературы – основной и дополнительной.

Рабочая программа пересмотрена и одобрена на заседании кафедры от 01.01.2001 г., протокол №1.

Заведующий кафедрой

программного обеспечения

2. Тематический план изучения дисциплины

2.1. Распределение часов курса дисциплины по темам и видам работ

№	Тема	Лекции час.	Лабораторные занятия, час.	Самостоятельная и инд. работа, час	Итого часов по теме	Итого количество баллов
1	2	3	4	5	6	7
1.	Введение	2			2
2.	Деревья	4	2	4	10	7
3.	Обходы. Элементы цикломатики	4	2	6	12	10
4.	Раскраски	4	2	4	10	10
5.	Метрические характеристики графов и экстремальные задачи	6	3	8	17	8
6.	Глобальный анализ графов. Алгоритмы на графах.	6	4	10	20	30
7.	Перечислительные вопросы теории графов	6	3	6	15	10
8.	Приложения графов для задач программирования	4	2	8	14	25
	Итого по дисциплине за 5 семестр (часов, баллов)	36	18	46	100	100

2.2. ОЦЕНКА РАБОТЫ СТУДЕНТОВ В РЕЙТИНГОВЫХ БАЛЛАХ

Распределение рейтинговых баллов по видам работ и нормам контроля

5 семестр

Виды работ и контроля	Максимальное количество баллов
Тема 1	Тема 2	Тема 3	Тема 4	Тема 5	Тема 6	Тема 7	Тема 8	Итого
Лекции	-	-	-	-	-	-	-	-	-
Лабораторные работы	-	3	5	5	4	10	5	10	42
Контрольная работа	-	-	-	-	-	10	-	7	17
Самостоятельная работа	-	4	5	5	4	10	5	8	41
Итого по дисциплине	-	7	10	10	8	30	10	25	100

Виды контроля деятельности студентов, применяемые на аудиторных занятиях, их оценка в рейтинговых баллах

№ п/п	Вид контроля	Максимальное количество баллов
1.	Посещение лекционных занятий	В случае пропуска лекции без уважительной причины текущий рейтинг снижается на 1 балл
2.	Посещение лабораторных занятий	В случае пропуска занятия без уважительной причины текущий рейтинг снижается на 1 балла
3.	Выполнение лабораторных работ	За защиту лабораторной работы позже установленного срока количество баллов снижается на 2 балла.
4.	Выполнение индивидуальных заданий в процессе самостоятельной работы	0-5 баллов
5.	Выполнение факультативных творческих заданий	За выполнение по инициативе студента факультативных творческих заданий текущий рейтинг может быть повышен на величину баллов за задание
6.	Экзамен по дисциплине	0 - 5 баллов за ответ на вопрос экзаменационного билета

8.  Литература

Основная:

1.  Зайцева,  математика: учеб. пособие/ - Тюмень: Изд-во ТюмГУ, 20с..

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

1.  Кузнецов, О. П.. Дискретная математика для инженера: [учеб. пособие]/ . - 5-е изд., стер.. - Санкт-Петербург: Лань, 20с

2.  Новиков, Ф. А..Дискретная математика для программистов: учеб. пособие для студ. вузов, обуч. по спец. "Информатика и вычислительная техника"/ . - 3-е изд. - Санкт-Петербург: Питер, 20с

3.  Хаггарти, Р. Дискретная математика для программистов: учеб. пособие для студентов вузов, обуч. по напр. подгот. "Прикл. мат." : пер. с англ./ Р. Хаггарти. - 2-е изд., доп.. - Москва: Техносфера, 20с