МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Томский государственный университет

УТВЕРЖДАЮ

Декан факультета информатики

"" декабря 2010 г.

Рабочая программа дисциплины

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

Направление подготовки

230700 Прикладная информатика

Квалификация выпускника

Бакалавр

Форма обучения

Очная

Томск

2010

1. Цели освоения дисциплины

Целями освоения дисциплины «Теория графов» являются получение теоретических знаний по основам теории графов.

2. Место дисциплины в структуре ООП бакалавриата

Раздел образовательной программы: Б.2.7. Математический и естественно-научный цикл. Вариативная часть.

Для изучения курса необходимо знание следующих дисциплин:

- дискретная математика.

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

- знать теорию множеств, теорию отношений, теорию булевых алгебр.

Знания и умения, полученные в ходе освоения данной дисциплины, понадобятся при изучении таких последующих дисциплин ООП, как:

- алгоритмы и анализ сложности;

- основы программирования;

- базы данных;

- методы оптимизации и исследование операций;

- интеллектуальные системы;

- теория автоматов и формальных языков;

- теория систем и системный анализ.

3. Компетенции обучающегося, формируемые в результате освоения дисциплины (модуля) Теория графов

Курс «Теория графов» способствует выработке у студента следующих компетенций:

- знание основных понятий и методов теории графов;

- умение применять на практике методы и алгоритмы теории графов.

НЕ нашли? Не то? Что вы ищете?

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

4. Структура и содержание дисциплины (модуля) «Теория графов»

Общая трудоемкость дисциплины составляет 3 зачетных единицы, 108 часов.

№

п/п

Раздел

Дисциплины

Семестр

Неделя семестра

Виды учебной работы, включая самостоятельную работу студентов и трудоемкость (в часах)

Формы текущего контроля успеваемости (по неделям семестра)

Форма промежуточной аттестации (по семестрам)

всего

лекции

сем

самостоятельная работа

1

Основные определения

2

1-2

12

4

8

2

Связность графов

2

3-4

12

4

8

3

Цикломатика графов

2

5-6

18

4

4

10

Тест

4

Потоки в сетях

2

7-8

14

4

10

5

Экстремальные части графов

2

9-10

18

4

4

10

Тест

6

Задачи раскраски вершин и ребер графа

2

11-12

12

4

8

Тест

7

Алгоритмы

2

13-14

11

4

7

8

Применение графов для задач программирования

2

15-16

11

4

7

Тест

ИТОГО

108

32

8

68

Экзамен

Лекционный курс

Тема 1. Основные определения.

Способы задания графов. Типы графов.

Тема 2. Связность графов.

Маршруты, цепи, циклы. Алгоритмы нахождения кратчайших цепей. Обходы графа. Эйлеровы цепи и циклы, гамильтоновы цепи и циклы.

Тема 3. Цикломатика графов.

Цикломатическое число. Деревья, каркасы. Алгоритмы нахождения каркасов. Нахождение фундаментальных циклов. Цикломатическая матрица, матрица разрезов.

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

Алгоритм Форда – Фалкерсона нахождения максимального потока в сети.

Тема 5. Экстремальные части графов.

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

Тема 6. Задачи раскраски вершин и ребер графа.

Проблема четырех красок. Алгоритмы минимальной раскраски.

Тема 7. Алгоритмы.

Алгоритмы решения задач на взвешенных графах.

Тема 8. Применение графов для задач программирования.

Графы как модели программ, процессов и информационных структур.

6. Учебно-методическое обеспечение самостоятельной работы студентов. Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины.

Самостоятельная работа студентов по дисциплине организуется в следующих формах:

- самостоятельное изучение основного теоретического материала, ознакомление с дополнительной литературой, Интернет-ресурсами;

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

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

7. Учебно-методическое и информационное обеспечение дисциплины «Теория графов»

а) основная литература:

Лекции по теории графов/ и др. – Наука, Гл. ред. физ-мат. лит., 1990. Зыков теории графов. – М., Наука, Гл. ред. физ-мат. лит., 1987. Теория графов. Алгоритмический подход. – М., Мир, 1978. Новиков математика для программистов. – СПб: Питер, 2000.

б) дополнительная литература:

Комбинаторика для программистов. – М., Мир, 1977. Графы, сети и алгоритмы. – М., Мир, 1984. . Теория графов и ее применения. – М., Изд-во иностр. лит., 1962.

8. Материально-техническое обеспечение дисциплины

Требуется обеспечение литературой, которую в достаточном объеме может предложить книжный фонд Научной библиотеки Томского госуниверситета и факультета информатики.

Программа составлена в соответствии с требованиями ФГОС ВПО с учетом рекомендаций и ООП ВПО по направлению подготовки 010300 Фундаментальная информатика и информационные технологии.

Автор: ст. преподаватель

Рецензент: д. физ-мат. н., профессор О. А. Змеев.

Программа одобрена на заседании Ученого Совета Факультета информатики
от «___»_________2010 г., протокол № ___.