Базовая рабочая программа дисциплины теория графов

 

УТВЕРЖДАЮ

Начальник

учебно-методического управления

___________ёв

«___»_____________2013 г.

 

БАЗОВАЯ РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ

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

 

Направление (специальность) 230100 Информатика и вычислительная техника

 

Профиль подготовки: система углубленной профессиональной подготовки Элитное техническое образование

Квалификация (степень): Бакалавр

 

Базовый учебный план приема 2011 г.

Курс 3 семестр 5,6

Количество кредитов 4

Код дисциплины Б3.В8.4

 

Виды учебной деятельности	Временной ресурс по очной форме обучения
Лекции, ч	70
Практические занятия, ч	70
Лабораторные занятия, ч	140
Аудиторные занятия, ч	140
Самостоятельная работа, ч	280
ИТОГО, ч	70

Вид промежуточной аттестации ЗАЧЕТ

Обеспечивающее подразделение Отдел элитного образования УМУ ТПУ

 

Руководитель ОП ЭТО

Преподаватель Преподаватель

2013 г.

1. ЦЕЛИ ОСВОЕНИЯ ДИСЦИПЛИНЫ

Дисциплина «Теория графов» является важной для подготовки бакалавров по направлению 230100 «Информационные системы и технологии». Методы теории графов широко применяются для решения различных прикладных задач, и знание этих методов необходимы для разработки современных программных средств.

Цели преподавания дисциплины – дать студенту систематические знания и навыки в области оптимизационных задач теории графов.

Поставленные цели полностью соответствуют целям (Ц1, Ц2, Ц3) ООП.

2.МЕСТО ДИСЦИПЛИНЫ В СТРУКТУРЕ ООП

Дисциплина «Теория графов» является базовой дисциплиной профессионального цикла. Дисциплина относится к дисциплинам по выбору.

Для её успешного усвоения необходимы базовые знания математики.

 

3.РЕЗУЛЬТАТЫ ОСВОЕНИЯ ДИСЦИПЛИНЫ

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

Таблица 1

Составляющие результатов обучения, которые будут получены
при изучении данной дисциплины

Результаты обучения (компетенции из ФГОС)	Составляющие результатов обучения
Код	Знания	Код	Умения	Код	Владение опытом
Р1 (ОК-1, ПК-2, ПК-16)	З1.2.2	понятия и теоретические основы теории графов, классические и обобщенные постановки оптимизационных задач теории графов; область использования методов теории графов в геоинформационных системах	У1.2.2	применять методы оптимизации к задачам теории графов; использовать классические алгоритмы решения оптимизационных задач теории графов, модифицировать алгоритмы для решения нестандартных задач.	В1.2.2	методами решения оптимизационных задач на графах; методами оценивания вычислительной сложности алгоритмов; навыками разработки алгоритмов и их обоснования.

 

В результате освоения дисциплины «Теория графов» студентами должны быть достигнуты следующие результаты (табл. 2):

 

Таблица 2

Планируемые результаты освоения дисциплины

№ п/п	Результат
РД1	Знать основные понятия теории графов, классификации и способы задания графов. Уметь использовать способы задания графов.
РД2	Знать основные задачи поиска оптимальных путей и задачи размещения. Уметь использовать классические алгоритмы решения этих задач и разрабатывать их модификации.
РД3	Знать понятия дерева и леса, свойства деревьев и лесов. Уметь построить остовное дерево минимального веса, остовный лес максимального веса. Знать принципы работы с деревом сортировки, уметь стоить различные типы деревьев сортировки.
РД4	Знать понятия покрытий и независимых множеств вершин и ребер. Уметь находить оптимальные паросочетания и покрытия, решать задачи о назначениях и транспортную задачу
РД5	Знать понятия эйлерова и гамильтонова цикла и условия их существования. Уметь решать задачу почтальона на ориентированном, неориентированном и смешанном графе, задачу коммивояжера.
РД6	Знать понятия планарного и плоского графов, необходимые и достаточные условия планарности графа, понятия и методы оценки хроматического числа графа. Уметь уложить планарный граф на плоскости, определить, является ли граф планарным, найти оптимальную раскраску графа.

4. СТРУКТУРА И СОДЕРЖАНИЕ ДИСЦИПЛИНЫ

Раздел 1. Основные понятия теории графов. Понятия графа, простого графа, орграфа, мультиграфа и орграфа. Типы графов: пустой, полный, регулярный, двудольный. Изоморфизм графов. Подграфы: остовный, собственный, правильный. Операции над графами: объединение, соединение, дополнение, стягивание подграфа в вершину. Способы задания графов: матрицы смежности вершин и ребер, матрица инцидентности, списки смежности.

Перечень практических занятий по разделу:

1. Графы, их классификация и способы задания.

Раздел 2. Связность графа. Маршрут, цепь, простая цепь, цикл, простой цикл. Длина маршрута и расстояние между вершинами, диаметр, радиус и центры графа. Связные вершины, связный граф, компоненты связности. Разделяющее множество, разрез, мост. Меры связности: вершинная и реберная связность. Теорема Менгера в вершинной форме. Оценка числа ребер в простом графе. Связность орграфов: сильная, односторонняя, слабая. Выделение компонент сильной связности. Построение матрицы достижимости: определение наличия путей заданной длины, алгоритм Уоршалла.

Перечень практических занятий по разделу:

1.      Связность неориентированных графов.

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

3.      Игра «Двух слонов преимущество».

Раздел 2. Поиск путей в графе. Стратегии обхода графа в глубину и в ширину. Алгоритм Тэрри поиска пути. Определение числа путей заданной длины. Кратчайший и минимальный пути в нагруженном графе. Поиск кратчайшего пути: волновой алгоритм. Поиск минимального пути: алгоритмы Дейкстра, Форда и Беллмана-Мура. Поиск минимальных путей между всеми парами вершин: алгоритмы Флойда и Данцига. Поиск k минимальных путей: алгоритм двойного поиска. Поиск k минимальных путей между всеми парами вершин: обобщенные алгоритмы Флойда и Данцига. Поиск k простых минимальных путей: алгоритм Йена. Модификация алгоритмов поиска для графа без контуров. Латинские свойства, поиск путей с заданными свойствами методом латинской композиции.

Перечень практических занятий по разделу:

1.      Поиск оптимальных путей от заданной вершины.

2.      Поиск оптимальных путей между всеми парами вершин.

3.      Поиск k минимальных путей.

4.      Игра «Поиск оптимальных путей».

Раздел 3. Деревья. Определения дерева и леса, теорема о шести эквивалентных утверждениях о дереве. Остовное дерево, циклический ранг, задача о соединении городов. Построение кратчайшего остова: алгоритмы Прима и Краскала. Задача Штайнера. Ориентированные и упорядоченные деревья. Построение ориентированного дерева и леса. Построение максимального ориентированного леса: алгоритм Эдмондса. Бинарные деревья и стратегии их обхода. Дерево сортировки, оптимальное дерево, сбалансированное дерево, красно-черное дерево: алгоритмы поиска, добавления и удаления вершины.

Перечень практических занятий по разделу:

1.      Построение кратчайшего остова и максимального ориентированного леса.

2.      Деревья сортировки.

Раздел 4. Задачи размещения. Расстояния в графе: вершина-вершина, вершина ребро, точка-вершина, точка-ребро. Центры и медианы графа, главные и абсолютные центры и медианы, методы их поиска. Обобщение задач размещения: задачи с усилениями, поиск кратных центров и медиан.

Перечень практических занятий по разделу:

1.      Поиск центров и медиан.

2.      Поиск кратных центров и медиан.

Раздел 5. Орграфы и сети. Бесконтурные графы, топологическая сортировка. Определение сети. Потоки в сетях, алгоритм построения потока. Теорема Форда–Фалкерсона и алгоритм построения максимального потока. Построение потока минимальной стоимости: алгоритм Форда-Фалкерсона, алгоритмы, основанные на выделении циклов отрицательного веса и на поиске минимального пути.

Перечень практических занятий по разделу:

1.      Поиск максимального потока.

2.      Поиск потока минимальной стоимости.

Раздел 6. Паросочетания и покрытия. Независимые и покрывающие множества. Теорема о числах независимости и покрытий. Максимальные независимые множества вершин, их поиск. Кратчайшее вершинное покрытие, алгоритмы его поиска. Доминирующие множества. Паросочетание. Поиск паросочетания максимальной мощности. Поиск паросочетания максимального веса. Определение двудольного графа. Совершенное паросочетание. Задача о свадьбах, теорема Холла. Задача о назначениях и алгоритм ее решения. Транспортная задача и алгоритм ее решения.

Перечень практических занятий по разделу:

1.      Поиск оптимальных покрытий.

2.      Поиск оптимальных паросочетаний .

3.      Задача о назначениях, транспортная задача.

Раздел 7. Эйлеровы графы. Определение эйлерова и полуэйлерова графов. Лемма о цикле, необходимое и достаточное условие эйлеровости графа. Алгоритм Флери поиска эйлерова цикла. Необходимое и достаточное условие эйлеровости орграфа. Задача почтальона и алгоритмы ее решения для неориентированного, ориентированного и смешанного графа.

Перечень практических занятий по разделу:

1. Поиск оптимального маршрута почтальона.

Раздел 8. Гамильтоновы графы. Определение гамильтонова и полугамильтонова графов, теорема Дирака. Задача коммивояжера. Метод ветвей и границ для решения задачи коммивояжера. Некоторые эвристические алгоритмы: ближайшего соседа, ближайшей вставки, локальной оптимизации, Эйлера, Кристофидеса.

Перечень практических занятий по разделу:

1. Поиск оптимального маршрута коммивояжера.

Раздел 9. Планарность графов. Укладка графа, теорема об укладке графа в трехмерном пространстве. Плоский и планарный графы, теорема о графах K5 и K3,3. Операции включения вершины в ребро и стягивания вершин, гомеоморфность графов. Необходимое и достаточное условие планарности графа. Толщина графа. Алгоритм укладки графа на плоскости.

Перечень практических занятий по разделу:

1. Укладка графа на плоскости.

Раздел 10. Раскраска графов. Постановка задачи раскраски графа. Хроматическое число произвольных графов. Теорема Брукса. Хроматическое число планарных графов. Теоремы о шести и о пяти красках, гипотеза о четырех красках. Точные и приближенные алгоритмы раскрашивания графа.

Перечень практических занятий по разделу:

1. Оптимальная раскраска графа.

5. Образовательные технологии

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

Таблица 3.

Методы и формы организации обучения (ФОО)

ФОО   Методы	Лекц.	Практ. зан.	СРС
IT-методы
Работа в команде		+	+
Case-study		+
Игра		+
Методы проблемного обучения	+	+
Обучение на основе опыта		+
Опережающая самостоятельная работа			+
Проектный метод		+	+
Поисковый метод		+	+
Исследовательский метод			+
Другие методы

Для достижения поставленных целей преподавания дисциплины реализуются следующие средства, способы и организационные мероприятия:

-                        использование мультимедийного оборудования на лекциях, на лабораторных работах и СРС – компьютерного оборудования;

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

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

 

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

5.1       Виды и формы самостоятельной работы

Самостоятельная работа студентов включает текущую и творческую проблемно-ориентированную самостоятельную работу (ТСР).

Текущая СРС направлена на углубление и закрепление знаний студента, развитие практических умений и включает:

·         работу с лекционным материалом и рекомендованной литературой;

·         выполнение индивидуальных домашних заданий;

·         изучение тем, вынесенных на самостоятельную проработку;

·         подготовку к экзамену.

Творческая проблемно-ориентированная самостоятельная работа включает

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

 

Темы, выносимые на самостоятельную проработку

 

1.      Задача Штайнера, методы ее решения.

2.      Модификации алгоритма Эдмондса для построения остовных лесов и деревьев.

3.      Обобщение задач размещения: задачи с усилениями, поиск кратных центров и медиан. Методы приближенного решения обобщенных задач.

4.      Сетевые графики.

5.      Поиск паросочетаний в не двудольных графах.

6.      Приближенные методы решения задачи почтальона для нечетного несимметричного графа.

7.      Приближенные методы решения задачи коммивояжера.

8.      Теорема о графах K5 и K3,3.

9.      Теорема Брукса.

 

Задания для написания программ

 

1.      Поиск оптимальных путей.

2.      Построение остовных деревьев и лесов.

3.      Поиск центров и медиан, кратных центров и медиан.

4.      Поиск максимального потока.

5.      Поиск потока минимальной стоимости.

6.      Поиск минимального доминирующего множества.

7.      Поиск кратчайших и минимальных покрытий.

8.      Решение задачи о назначениях.

9.      Решение транспортной задачи.

10.  Поиск оптимальных паросочетаний.

11.  Решение задачи почтальона.

12.  Решение задачи коммивояжера.

13.  Укладка графа на плоскости.

14.  Поиск оптимальной раскраски графа.

 

Темы докладов.

 

1.    Обобщение алгоритмов поиска минимального пути для решения задачи поиска k первых минимальных путей.

2.    Латинские свойства, метод латинской композиции.

3.    Методы решения задачи Штайнера.

4.    Приближенные методы поиска кратных центров и медиан.

5.    Приближенные методы решения задачи почтальона для нечетного несимметричного графа.

7. Приближенные методы решения задачи коммивояжера.

 

5.2       Контроль самостоятельной работы

 

Оценка результатов самостоятельной работы организуется следующим образом:

·         защита отчетов по программам;

·         выполнение и защита индивидуального домашнего задания;

·         выступление с докладами.

 

6. Средства текущей и промежуточной оценки качества освоения дисциплины

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

 

Контролирующие мероприятия	Результаты обучения по дисциплине
Проверка индивидуальных домашних заданий	РД1–РД6
Проверка программ, реализующих изучаемые алгоритмы	РД1–РД6
Защита докладов.	РД1–РД6
Зачет.	РД1–РД6

Для оценки качества освоения дисциплины при проведении контролирующих мероприятий предусмотрены следующие средства (фонд оценочных средств):

Вопросы входного контроля

1.      Определения графа, псевдографа, мультиграфа и орграфа.

2.      Смежность вершин и ребер.

3.      Связность, компоненты связности.

4.      Маршруты, цепи, циклы.

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

6.      Изоморфизм графов.

7.      Вершинно- и реберно-непересекающиеся цепи.

8.      Подграфы.

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

10.  Операции над графами.

 

Индивидуальные домашние задания

Основные понятия теории графов. Вариант 2.

 

1. Перечислить все неизоморфные связные графы с пятью вершинами.

2. Предложить алгоритм поиска простого цикла по матрице инциденций графа.

3. Доказать, что среди любых 6 человек есть 3 либо попарно знакомых, либо попарно незнакомых.

 

4. Доказать, что любой граф без циклов является двудольным.

5. Как выглядит матрица смежности дополнения соединения двух графов ?

6. Сколько различных правильных подграфов есть у графа с p вершинами?

 

Связность. Вариант 1.

 

1. Найти диаметр, радиус и центры графа.

2. Определить числа вершинной и реберной связности графа.

3. Найти минимальное разделяющее множество вершин для b, h.

4. Найти максимальное множество вершинно-непересекающихся цепей для b, h.

5. Построить фактор-граф орграфа. Определить тип связности.

6. С помощью операций над булевыми матрицами определить, между какими вершинами существуют пути длины 3.

7. С помощью алгоритма Уоршалла определить, между какими вершинами существую пути, проходящие только через вершины {b,c,e}.

Поиск путей. Вариант 1.

 

1. Найти волновым алгоритмом кратчайшие пути от вершины a до остальных вершин.

2. Найти алгоритмом Дейкстра минимальные пути от вершины a до остальных вершин.

3. Найти алгоритмом Йена 3 первых простых минимальных пути <a,h>.

4. Пользуясь алгоритмом Форда, найти минимальные пути от вершины a до остальных вершин или показать, что задача не имеет решения.

5. Пользуясь алгоритмом Флойда, найти минимальные пути между всеми парами вершин или показать, что задача не имеет решения.

6. Выполнить одну итерацию алгоритма двойного поиска, применив его для нахождения 3 минимальных путей от вершины a до остальных вершин.

7. Найти обобщенным алгоритмом Данцига 2 минимальных пути между всеми парами вершин.

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

9. Предложить алгоритм поиска самого длинного простого пути между заданными вершинами. Обосновать алгоритм и получить оценку его вычислительной сложности.

Задачи размещения. Вариант 1.

1.      Найти все типы центров и медиан графа.

2.      Предложить алгоритм поиска кратного центра графа.

Деревья. Вариант 1.

1. Доказать, что следующие утверждения эквивалентны:

1) граф G ­– дерево, то есть связный граф без циклов;

2) граф G связный, и любое ребро есть мост;

3) граф G не содержит циклов, и q=p–1;

4) граф G не содержит циклов, но добавление к нему любого нового ребра приводит к образованию ровно одного простого цикла, проходящего через это ребро.

2. Доказать, что ордерево обладает следующими свойствами:

1) q=p–1;

2) если в ордереве отменить ориентацию ребер, то получится свободное дерево;

3) в ордереве нет контуров.

3. Нарисовать диаграммы всех неизоморфных деревьев с шестью вершинами.

4. Найти алгоритмом Краскала кратчайший остов в графе, полученном из исходного отменой ориентации ребер.

5. Найти алгоритмом Эдмондса максимальный остовный лес.

 

6. Последовательно построить дерево сортировки из букв своей фамилии, имени и отчества (всего 10 различных букв). Удалить корень левого поддерева.

7. Последовательно построить сбалансированное дерево из букв своей фамилии, имени и отчества (всего 10 различных букв). Удалить букву, добавленную четвертой.

8. Последовательно построить черно-красное дерево из букв своей фамилии, имени и отчества (всего 10 различных букв). Удалить букву, добавленную четвертой.

 

Эйлеровы графы. Вариант 1.

Решить задачу почтальона для не ориентированного и смешанного графов.

 

 

Вопросы к зачету

Понятия графа, орграфа, мультиграфа и псевдографа. Смежность вершин и ребер. Лемма Эйлера. Теорема о числе вершин нечетной степени. Подграфы. Изоморфизм. Способы задания графов. Маршруты в графе. Расстояния в графе. Диаметр, радиус и центры графа. Связность неориентированных графов, меры связности. Теорема Менгера в вершинной форме. Оценка числа ребер в графе. Связность орграфов. Поиск компонент сильной связности. Алгоритм Тэрри поиска пути. Определение числа путей заданной длины. Поиск кратчайшего пути: волновой алгоритм. Поиск минимального пути: алгоритмы Дейкстра, Форда и Беллмана-Мура. Поиск минимальных путей между всеми парами вершин: алгоритмы Флойда и Данцига. Поиск k минимальных путей: алгоритм двойного поиска. Поиск k минимальных путей между всеми парами вершин: обобщенные алгоритмы Флойда и Данцига. Поиск k простых минимальных путей: алгоритм Йена. Модификация алгоритмов поиска для графа без контуров. Определения дерева и леса, теорема о шести эквивалентных утверждениях о дереве. Остовное дерево, циклический ранг, задача о соединении городов. Построение кратчайшего остова: алгоритмы Прима и Краскала. Построение максимального ориентированного леса: алгоритм Эдмондса. Деревья сортировки. Поиск, добавление и удаление вершин. Сбалансированные деревья. Поиск, добавление и удаление вершин. Красно-черные деревья. Поиск, добавление и удаление вершин. Расстояния в графе: вершина-вершина, вершина-ребро, точка-вершина, точка-ребро. Поиск центров графа. Поиск медиан графа. Поиск кратных центров. Поиск кратных медиан. Топологическая сортировка. Потоки в сетях. Теорема о максимальном потоке и минимальном разрезе. Поиск максимального потока. Варианты задачи о максимальном потоке. Поиск потока минимальной стоимости: решение двойственной задачи линейного программирования. Поиск потока минимальной стоимости: выявление циклов отрицательного веса. Поиск потока минимальной стоимости: построение минимальных путей. Независимые и покрывающие множества. Максимальные независимые множества, их поиск. Вершинные покрытия, их поиск.

40.  Доминирующие множества, их поиск.

Паросочетания и реберные покрытия. Чередующиеся цепи и деревья. Теорема о паросочетании максимальной мощности. Цветки. Теорема о цветке. Венгерское дерево. Теорема о венгерском дереве. Поиск паросочетания максимальной мощности. Поиск паросочетания максимального веса. Совершенное паросочетание в двудольном графе. Теорема Холла. Трансверсаль. Задача о назначениях. Транспортная задача. Варианты транспортной задачи. Эйлеровы графы. Необходимые и достаточные условия эйлеровости. Поиск эйлерова цикла. Задача почтальона для не ориентированных графов. Задача почтальона для ориентированных графов. Задача почтальона для смешанных графов. Гамильтоновы графы. Достаточные условия гамильтоновости. Поиск гамильтонова цикла. Задача коммивояжера. Метод ветвей и границ. Задача коммивояжера. Эвристические методы ее решения. Плоские и планарные графы. Толщина графа. Укладка графа на плоскости. Хроматическое число произвольных графов. Хроматическое число планарных графов. Раскрашивание графов.

 

7. Рейтинг качества освоения дисциплины

Оценка качества освоения дисциплины в ходе текущей и промежуточной аттестации обучающихся осуществляется в соответствии с «Руководящими материалами по текущему контролю успеваемости, промежуточной и итоговой аттестации студентов Томского политехнического университета», утвержденными приказом ректора № 77/од от 01.01.2001 г.

В соответствии с «Календарным планом изучения дисциплины»:

·      текущая аттестация, направленная на оценку качества усвоения теоретического материала (тестирование) и результатов практической деятельности (выполнение и защита отчетов индивидуальных заданий), производится в течение семестра и оценивается в баллах (максимально 60 баллов), к моменту завершения семестра студент должен набрать не менее 33 баллов;

·      промежуточная аттестация (экзамен) производится в конце семестра и так же оценивается в баллах (максимально 40 баллов), на экзамене студент должен набрать не менее 22 баллов.

Итоговый рейтинг по дисциплине определяется суммированием баллов, полученных в ходе текущей и промежуточной аттестаций. Максимальный итоговый рейтинг соответствует 100 баллам.

8. Учебно-методическое и информационное обеспечение дисциплины

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

1.    Э. Майника. Оптимизационные задачи на сетях и графах.

2.    . Дискретная математика для программистов. – Питер, 2001.

3.    Р.Уилсон. Введение в теорию графов. – М.: Мир, 1977.

4.    Н.Кристофидес. Теория графов. Алгоритмический подход. – М.: Мир, 1977.

5.    Ф. Харари. Теория графов. – М.: Мир, 1973.

6.    К. Берж. Теория графов.

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

7.    , . Курс дискретной математики. – М.: МАИ, 1992.

8.    . Программирование в алгоритмах. – М.: БИНОМ, Лаборатория знаний, 2002.

9.    , . Дискретная математика. – М., изд-во МГТУ им. Баумана, 2002.

10.              . Дискретная математика: алгоритмы и программы. – М.: Лаборатория базовых знаний, 2002.

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

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

 

Программа составлена на основе Стандарта ООП (МП) ТПУ в соответствии с требованиями ФГОС по направлению 230100 «Информатика и вычислительная техника».

Программа одобрена на заседании кафедры ВТ

(протокол № 29 от « 03 » 09  2013 г.).

Автор – доцент кафедры ВТ

Рецензент – профессор кафедры ВТ