Партнерка на США и Канаду по недвижимости, выплаты в крипто
- 30% recurring commission
- Выплаты в USDT
- Вывод каждую неделю
- Комиссия до 5 лет за каждого referral
1. 
2.
3. 1. ЦЕЛИ ОСВОЕНИЯ ДИСЦИПЛИНЫ
Дисциплина «Теория графов» занимает в подготовке магистров по направлению 09.04.02 «Информационные системы и технологии» по профилю «Геоинформационные системы» одно из важнейших мест. Методы теории графов широко применяются в задачах геоинформатики, и знание этих методов необходимы для разработки современных геоинформационных систем.
Цели преподавания дисциплины – дать студенту систематические знания и навыки в области оптимизационных задач теории графов.
Поставленные цели полностью соответствуют целям (Ц1, Ц2, Ц3) ООП.
2.МЕСТО ДИСЦИПЛИНЫ В СТРУКТУРЕ ООП
Дисциплина «Теория графов» является базовой дисциплиной (М1.БМ2.3) модуля общепрофессиональных дисциплин.
Для её успешного усвоения необходимы базовые знания, полученные при изучении ООП бакалаврской подготовки по направлениям «Информатика и вычислительная техника», «Информационные системы и технологии» и родственным им направлениям.
В соответствии с учебным планом данная дисциплина читается в 1-ом семестре и не имеет пререквизитов в рамках ООП магистерской подготовки.
Кореквизитами являются дисциплины «Современные проблемы информационных систем и технологий» (М1.ВМ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 | Знать понятия планарного и плоского графов, необходимые и достаточные условия планарности графа, понятия и методы оценки хроматического числа графа. Уметь уложить планарный граф на плоскости, определить, является ли граф планарным, найти оптимальную раскраску графа. |
4. СТРУКТУРА И СОДЕРЖАНИЕ ДИСЦИПЛИНЫ
Раздел 1. Введение. Основные понятия теории графов. Связь теории графов с предметной областью.
Раздел 2. Поиск путей в графе. Стратегии обхода графа в глубину и в ширину. Алгоритм Тэрри поиска пути. Определение числа путей заданной длины. Кратчайший и минимальный пути в нагруженном графе. Поиск кратчайшего пути: волновой алгоритм. Поиск минимального пути: алгоритмы Дейкстра, Форда и Беллмана-Мура. Поиск минимальных путей между всеми парами вершин: алгоритмы Флойда и Данцига. Поиск k минимальных путей: алгоритм двойного поиска. Поиск k минимальных путей между всеми парами вершин: обобщенные алгоритмы Флойда и Данцига. Поиск k минимальных путей: алгоритм Йена. Модификация алгоритмов поиска для графа без контуров.
Перечень практических занятий по разделу:
1. Поиск оптимальных путей.
Раздел 3. Деревья. Определения дерева и леса, теорема о шести эквивалентных утверждениях о дереве. Остовное дерево, циклический ранг, задача о соединении городов. Построение кратчайшего остова: алгоритмы Прима и Краскала. Задача Штайнера. Ориентированные и упорядоченные деревья. Построение ориентированного дерева и леса. Построение максимального ориентированного леса: алгоритм Эдмондса.
Перечень практических занятий по разделу:
1. Построение кратчайшего остова и максимального ориентированного леса.
Раздел 4. Задачи размещения. Расстояния в графе: вершина-вершина, вершина ребро, точка-вершина, точка-ребро. Центры и медианы графа, главные и абсолютные центры и медианы, методы их поиска. Обобщение задач размещения: задачи с усилениями, поиск кратных центров и медиан.
Перечень практических занятий по разделу:
1. Поиск центров и медиан.
Раздел 5. Орграфы и сети. Бесконтурные графы, топологическая сортировка. Определение сети. Потоки в сетях, алгоритм построения потока. Теорема Форда–Фолкерсона и алгоритм построения максимального потока. Построение потока минимальной стоимости: алгоритм Форда-Фалкерсона, алгоритмы, основанные на выделении циклов отрицательного веса и на поиске минимального пути.
Перечень практических занятий по разделу:
1. Поиск максимального потока и потока минимальной стоимости.
Раздел 6. Паросочетания и покрытия. Независимые и покрывающие множества. Теорема о числах независимости и покрытий. Максимальные независимые множества вершин, их поиск. Кратчайшее вершинное покрытие, алгоритмы его поиска. Доминирующие множества. Паросочетание. Поиск паросочетания максимальной мощности. Поиск паросочетания максимального веса. Определение двудольного графа. Совершенное паросочетание. Задача о свадьбах, теорема Холла. Задача о назначениях и алгоритм ее решения. Транспортная задача и алгоритм ее решения.
Перечень практических занятий по разделу:
1. Поиск оптимальных паросочетаний и покрытий, задача о назначениях, транспортная задача.
Раздел 7. Эйлеровы графы. Определение эйлерова и полуэйлерова графов. Лемма о цикле, необходимое и достаточное условие эйлеровости графа. Алгоритм Флери поиска эйлерова цикла. Необходимое и достаточное условие эйлеровости орграфа. Задача почтальона и алгоритмы ее решения для неориентированного, ориентированного и смешанного графа.
Перечень практических занятий по разделу:
1. Поиск оптимального маршрута почтальона.
Раздел 8. Гамильтоновы графы. Определение гамильтонова и полугамильтонова графов, теорема Дирака. Задача коммивояжера. Метод ветвей и границ для решения задачи коммивояжера. Некоторые эвристические алгоритмы: ближайшего соседа, ближайшей вставки, локальной оптимизации, Эйлера, Кристофидеса.
Перечень практических занятий по разделу:
1. Поиск оптимального маршрута коммивояжера.
Раздел 9. Планарность графов. Укладка графа, теорема об укладке графа в трехмерном пространстве. Плоский и планарный графы, теорема о графах K5 и K3,3. Операции включения вершины в ребро и стягивания вершин, гомеоморфность графов. Необходимое и достаточное условие планарности графа. Толщина графа. Алгоритм укладки графа на плоскости.
Перечень практических занятий по разделу:
1. Укладка графо на плоскости.
Раздел 10. Раскраска графов. Постановка задачи раскраски графа. Хроматическое число произвольных графов. Теорема Брукса. Хроматическое число планарных графов. Теоремы о шести и о пяти красках, гипотеза о четырех красках. Точные и приближенные алгоритмы раскрашивания графа.
Перечень практических занятий по разделу:
1. Оптимальная раскраска графа.
5. Организация и учебно-методическое обеспечение
самостоятельной работы студентов
5.1 Виды и формы самостоятельной работы
Самостоятельная работа студентов включает текущую и творческую проблемно-ориентированную самостоятельную работу (ТСР).
Текущая СРС направлена на углубление и закрепление знаний студента, развитие практических умений и включает:
· работу с лекционным материалом и рекомендованной литературой;
· выполнение индивидуальных домашних заданий;
· изучение тем, вынесенных на самостоятельную проработку;
· подготовку к экзамену.
Творческая проблемно-ориентированная самостоятельная работа включает
- написание программ, реализующих изучаемые алгоритмы; модификация классических алгоритмов с учетом предметной области; подготовку докладов.
Темы, выносимые на самостоятельную проработку
1. Поиск k первых минимальных путей: алгоритм двойного описка, обобщенные алгоритмы Флойда и Данцига.
2. Поиск путей с заданными свойствами: метод латинской композиции.
3. Задача Штайнера, методы ее решения.
4. Модификации алгоритма Эдмондса для построения остовных лесов и деревьев.
5. Обобщение задач размещения: задачи с усилениями, поиск кратных центров и медиан. Методы приближенного решения обобщенных задач.
6. Сетевые графики.
7. Поиск паросочетаний в не двудольных графах.
8. Приближенные методы решения задачи почтальона для нечетного несимметричного графа.
9. Приближенные методы решения задачи коммивояжера.
10. Теорема о графах K5 и K3,3.
11. Теорема Брукса.
Задания для написания программ
1. Поиск оптимальных путей.
2. Построение остовных деревьев и лесов.
3. Поиск центров и медиан, кратных центров и медиан.
4. Поиск максимального потока.
5. Поиск потока минимальной стоимости.
6. Поиск минимального доминирующего множества.
7. Поиск кратчайших и минимальных покрытий.
8. Решение задачи о назначениях.
9. Решение транспортной задачи.
10. Поиск оптимальных паросочетаний.
11. Решение задачи почтальона.
12. Решение задачи коммивояжера.
13. Укладка графа на плоскости.
14. Поиск оптимальной раскраски графа.
Темы докладов.
1. Обобщение алгоритмов поиска минимального пути для решения задачи поиска k первых минимальных путей.
2. Латинские свойства, метод латинской композиции.
3. Методы решения задачи Штайнера.
4. Приближенные методы поиска кратных центров и медиан.
5. Венгерский алгоритм поиска оптимального паросочетания.
6. Приближенные методы решения задачи почтальона для нечетного несимметричного графа.
7. Приближенные методы решения задачи коммивояжера.
5.2 Контроль самостоятельной работы
Оценка результатов самостоятельной работы организуется следующим образом:
· защита отчетов по программам;
· выполнение и защита индивидуального домашнего задания;
· выступление с докладами.
6. Средства текущей и промежуточной оценки качества освоения дисциплины
Оценка качества освоения дисциплины производится по результатам следующих контролирующих мероприятий:
Контролирующие мероприятия | Результаты обучения по дисциплине |
Проверка индивидуальных домашних заданий | РД1–РД5 |
Проверка программ, реализующих изучаемые алгоритмы | РД1–РД5 |
Защита докладов. | РД1–РД5 |
Экзамен. | РД1–РД5 |
Для оценки качества освоения дисциплины при проведении контролирующих мероприятий предусмотрены следующие средства (фонд оценочных средств):
Вопросы входного контроля
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. Найти алгоритмом Эдмондса максимальный остовный лес.
Вопросы к экзамену
Алгоритм Тэрри поиска пути. Определение числа путей заданной длины. Поиск кратчайшего пути: волновой алгоритм. Поиск минимального пути: алгоритмы Дейкстра, Форда и Беллмана-Мура. Поиск минимальных путей между всеми парами вершин: алгоритмы Флойда и Данцига. Поиск k минимальных путей: алгоритм двойного поиска. Поиск k минимальных путей между всеми парами вершин: обобщенные алгоритмы Флойда и Данцига. Поиск k простых минимальных путей: алгоритм Йена. Модификация алгоритмов поиска для графа без контуров. Определения дерева и леса, теорема о шести эквивалентных утверждениях о дереве. Остовное дерево, циклический ранг, задача о соединении городов. Построение кратчайшего остова: алгоритмы Прима и Краскала. Задача Штайнера. Методы ее решения. Построение максимального ориентированного леса: алгоритм Эдмондса. Расстояния в графе: вершина-вершина, вершина ребро, точка-вершина, точка-ребро. Поиск центров графа. Поиск медиан графа. Поиск кратных центров. Поиск кратных медиан. Топологическая сортировка. Сетевые графики и их анализ. Потоки в сетях. Теорема о максимальном потоке и минимальном разрезе. Поиск максимального потока. Варианты задачи о максимальном потоке. Поиск потока минимальной стоимости: решение двойственной задачи линейного программирования. Поиск потока минимальной стоимости: выявление циклов отрицательного веса. Поиск потока минимальной стоимости: построение минимальных путей. Независимые и покрывающие множества. Максимальные независимые множества, их поиск. Вершинные покрытия, их поиск.28. Доминирующие множества, их поиск.
Паросочетания и реберные покрытия. Чередующиеся цепи и деревья. Теорема о паросочетании максимальной мощности. Цветки. Теорема о цветке. Венгерское дерево. Теорема о венгерском дереве. Поиск паросочетания максимальной мощности. Поиск паросочетания максимального веса. Совершенное паросочетание в двудольном графе. Теорема Холла. Трансверсаль. Задача о назначениях. Транспортная задача. Варианты транспортной задачи. Эйлеровы графы. Необходимые и достаточные условия эйлеровости. Поиск эйлерова цикла. Задача почтальона для не ориентированных графов. Задача почтальона для ориентированных графов. Задача почтальона для смешанных графов. Гамильтоновы графы. Достаточные условия гамильтоновости. Поиск гамильтонова цикла. Задача коммивояжера. Метод ветвей и границ. Задача коммивояжера. Эвристические методы ее решения. Плоские и планарные графы. Толщина графа. Укладка графа на плоскости. Хроматическое число произвольных графов. Хроматическое число планарных графов. Раскрашивание графов.7. Рейтинг качества освоения дисциплины
Оценка качества освоения дисциплины в ходе текущей и промежуточной аттестации обучающихся осуществляется в соответствии с «Руководящими материалами по текущему контролю успеваемости, промежуточной и итоговой аттестации студентов Томского политехнического университета», утвержденными приказом ректора № 77/од от 01.01.2001 г.
В соответствии с «Календарным планом изучения дисциплины»:
· текущая аттестация, направленная на оценку качества усвоения теоретического материала (тестирование) и результатов практической деятельности (выполнение и защита отчетов индивидуальных заданий), производится в течение семестра и оценивается в баллах (максимально 60 баллов), к моменту завершения семестра студент должен набрать не менее 33 баллов;
· промежуточная аттестация (экзамен) производится в конце семестра и так же оценивается в баллах (максимально 40 баллов), на экзамене студент должен набрать не менее 22 баллов.
Итоговый рейтинг по дисциплине определяется суммированием баллов, полученных в ходе текущей и промежуточной аттестаций. Максимальный итоговый рейтинг соответствует 100 баллам.
8. Учебно-методическое и информационное обеспечение дисциплины
· основная литература:
1. Б. Теория графов. Часть 1. – Томск: ТПУ, 2013.
2. А. Дискретная математика для бакалавров и магистров: учебник. – Санкт-Петербург: Питер, 2013.
· дополнительная литература:
1. И., Б. Логическое проектирование дискретных устройств. – Томск: ТПУ, 2011.
2. Дискретная математика: графы, матроиды, алгоритмы. – М.: Лань, 2010.
3. В., Э., Д. Структуры данных и алгоритмы. – М.: Вильямс, 2010.
4. Дискретная математика для программистов : учебное пособие. – М.: Бином ЛЗ, 2010.
9. Материально-техническое обеспечение дисциплины
Учебные занятия по дисциплине проводятся в аудитории, оснащенной мультимедийной техникой.
Программа составлена на основе Стандарта ООП (МП) ТПУ в соответствии с требованиями ФГОС ВО 3+ по направлению 09.04.02 «Информационные системы и технологии».
Программа одобрена на заседании кафедры ВТ (протокол № 29 от « 03 » 09 2013 г.).
Автор – доцент кафедры ВТ
Рецензент – профессор кафедры ВТ
Марков Николай Григорьевич
Основные порталы (построено редакторами)