Скачать 206.57 Kb.
|
Министерство образования и науки РФ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Уральский государственный педагогический университет» Математический факультет Кафедра геометрии РАБОЧАЯ УЧЕБНАЯ ПРОГРАММА по дисциплине «Теория графов» для ООП специальности «050201.65 – Математика» по циклу ДПП.В. – Дисциплины предметной подготовки (Курсы по выбору)
Екатеринбург 2012Рабочая учебная программа по дисциплине «Теория графов» ФГБОУ ВПО «Уральский государственный педагогический университет» Екатеринбург, 2012. – 13 с. Составители: Унегова Т.А., к. ф.-м. н., доцент, доцент каф. геометрии УрГПУ Рабочая учебная программа обсуждена на заседании кафедры геометрии УрГПУ Протокол от 7 апреля 2012 г. № 8 Зав. кафедрой _________________ Н.В. Дударева Декан математического факультета _________________ В.П. Толстопятов 1. Пояснительная записка 1.1. Цели и задачи изучения дисциплины «Теория графов» Цели Формирование знаний элементов теории графов. Задачи
1.2. Место дисциплины в структуре ПрОП Дисциплина «Теория графов» является дисциплиной цикла ДПП.В.00 – Дисциплины предметной подготовки (курсы по выбору). Требования к входным знаниям, умениям и компетенциям студента, необходимым для изучения дисциплины «Теория графов»: Знать:
Уметь:
Владеть:
1.3. Требования к результатам освоения дисциплины: В результате изучения дисциплины студент должен Знать:
Уметь:
Владеть:
1.4. Объем дисциплины и виды учебной работы Общая трудоемкость дисциплины составляет 148 часов. Виды учебной работы: лекции, практические занятия, самостоятельная работа студентов. 2. УЧЕБНО-ТЕМАТИЧЕСКОЕ ПЛАНИРОВАНИЕ2.1. Учебно-тематический план очной формы обучения
2.2. Учебно-тематический план заочной формы обучения
3. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ
Исторический обзор возникновения и развития теории графов. Задача о Кёнигсбергских мостах и некоторые другие задачи, где используются системы из точек и отрезков. Применения идей и методов теории графов. Определение графа порядка k. Вершины и ребра графа. Изолированные вершины. Нуль-граф и полный граф. Число ребер полного графа. Подграфы. Дополнение графа. Определение маршрута в графе. Цепи и простые цепи. Циклические маршруты. Определение связного графа. Определение дерева. Некоторые свойства деревьев. Определение степени вершины графа. Четные и нечетные вершины. Лемма о рукопожатиях и ее следствие о количестве нечетных вершин в графе. Теоремы о степенях вершин графа (о наличии в графе по крайней мере двух вершин одинаковой степени и др.).
Определения плоского и планарного графов. Теорема Эйлера для дерева и для связного плоского графа. Максимально плоские графы и их свойства. Доказательство непланарности «полного пятиугольника» Решение занимательных задач и задач олимпиадного характера. Доказательство непланарности графа «домики и колодцы». Формула Эйлера и система прямых линий на плоскости.
Маршруты в графе и их специальные виды. Теорема о существовании в связном графе циклического маршрута, содержащего все ребра графа в точности два раза. Описание алгоритмов поиска в ширину и поиска в глубину. Построение кратчайшего маршрута. Вес (стоимость) ребра. Графы со взвешенными ребрами. Построение циклического маршрута, соединяющего две избранные вершины, с помощью алгоритма Форда-Беллмана. Определение остовного дерева графа. Первый жадный алгоритм (алгоритм Прима) построения остовного дерева наименьшего суммарного веса. Второй жадный алгоритм (алгоритм Дийкстры) построения остовного дерева с кратчайшими путями от корня до любой вершины.
Определение эйлерова графа. Критерий эйлеровости графа. Алгоритм построения эйлерова цикла в эйлеровом графе. Критерий существования в графе эйлеровой цепи. Уникурсальные фигуры. Лабиринты в жизни и лабиринты в математике. Решение лабиринта. Использование структур, подобных лабиринтам, в технике.
Определение гамильтонова графа. Один из способов решения вопроса об отсутствии гамильтонова цикла (цепи) по недостатку числа ребер для его построения. Решение задачи Эйлера об обходе шахматной доски ходом шахматного коня и ее обобщения на прямоугольные доски любого размера.
Формулировка задачи коммивояжера. Решение задачи коммивояжера методом ветвей и границ (разбираются прямое ветвление и метод Катта-Мурти).
Определение ориентированного графа (орграфа). Основные понятия, связанные с орграфами. Связность орграфов. Признак сильносвязного графа. Задача об одностороннем движении транспорта. Перенос решения некоторых задач для неориентированных графов на орграфы. Определение транспортной сети. Поток в сети и его величина. Алгоритм Форда-Фалкерсона о построении в сети максимального потока. Основная теорема теории траспортных сетей (теорема Гейла о насыщении)
Двудольные графы. Паросочетания. Решение задачи построения максимального паросочетания методом чередующихся цепей. Задача о сватовстве. Теорема о свадьбах. Связь задачи построения максимального паросочетания в двудольном графе с задачей о максимальном потоке. Перечень тем лекционных занятий
Лекция 1. Определение графа и его элементов. Маршруты в графе. Связные графы. Деревья.
Лекция 1. Плоские и планарные графы. Теорема Эйлера для плоского графа
Лекция 1. Эйлеровы графы.
Лекция 1. Ориентированные графы. Перечень тем практических занятий
Вопросы для контроля и самоконтроля
Перечень тем занятий, реализуемых в активной и интерактивной формах Все лекционные и практические занятия реализуются в активной и интерактивной формах. Все лекции носят проблемный характер, стимулируют учебную исследовательскую деятельность студентов, поскольку изучение нового теоретического материала всегда строится как решение математической задачи, ранее для студентов не известной. На практических занятиях используются индивидуальные задания, поисковая исследовательская лабораторная работа, работа в группах. 4. САМОСТОЯТЕЛЬНАЯ РАБОТА И ОРГАНИЗАЦИЯ КОНТРОЛЬНО-ОЦЕНОЧНОЙ ДЕЯТЕЛЬНОСТИ
(примерные вопросы для курсового зачета)
Задачи
5. УЧЕБНО-МЕТОДИЧЕСКОЕ И ИНФОРМАЦИОННОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ 5.1. Рекомендуемая литература Основная
(91 экз.) Дополнительная
7. СВЕДЕНИЯ ОБ АВТОРАХ ПРОГРАММЫ Унегова Татьяна Александровна кандидат физико-математических наук доцент доцент кафедры геометрии УрГПУ Раб. телефон (8-343) 371-29-10 |
Программа вступительных испытаний по дисциплине Дисциплина «Теория графов» является дисциплиной цикла дпп. В. 00 – Дисциплины предметной подготовки (курсы по выбору) | Конспект занятия по факультативу Дисциплина «Теория графов» является дисциплиной цикла дпп. В. 00 – Дисциплины предметной подготовки (курсы по выбору) | ||
Методические рекомендации по организации математических Дисциплина «Теория графов» является дисциплиной цикла дпп. В. 00 – Дисциплины предметной подготовки (курсы по выбору) | Блок Основные этапы развития геометрии Дисциплина «Теория графов» является дисциплиной цикла дпп. В. 00 – Дисциплины предметной подготовки (курсы по выбору) | ||
Рабочая учебная программа по дисциплине «маркетинг» по направлению... Составитель: Толстых Анатолий Александрович, к и н., доцент кафедры менеджмента и социально-экономических дисциплин | Урок геометрии в 7 классе общеобразовательной школы по теме «Основные... Дисциплина «Теория графов» является дисциплиной цикла дпп. В. 00 – Дисциплины предметной подготовки (курсы по выбору) | ||
Рабочая учебная программа по дисциплине «л итературная критика эпохи... Рабочая учебная программа по дисциплине «Литературная критика эпохи классического реализма» | Программа дисциплины «Теория графов» Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки 231300.... | ||
Рабочая учебная программа по дисциплине «Возрастная физиология и здоровый образ жизни» Ооп «050100 – Педагогическое образование» профиль «Математика» по циклу – профессиональный цикл, вариативная часть | Программа по дисциплине «Зоология» разработана в соответствии с Государственным... Программа по дисциплине «Зоология» разработана в соответствии с Государственным образовательным стандартом высшего профессионального... | ||
Программа по дисциплине «Биологические основы сельского хозяйства»... Специальность — 050101. 65 «Химия с дополнительной специальностью 050102. 65 Биология» Форма подготовки (очная) | Основная образовательная программа (ооп) специалиста 050201. 65 «Математика» Основная образовательная программа (ооп) специалиста 050201. 65 «Математика» с дополнительной специальностью «Информатика» | ||
Учебно-методический комплекс дисциплины специальность: 050201. 65 «Математика» Специальность: 050201. 65 «Математика», специализация «Использование информатики в обучении математике» | Учебно-методический комплекс дисциплины специальность: 050201. 65 «Математика» Специальность: 050201. 65 «Математика» с дополнительной специальностью 050202. 65«Информатика», квалификация специалиста – Учитель... | ||
Учебно-методический комплекс дисциплины специальность: 050201. 65 «Математика» Специальность: 050201. 65 – «Математика» с дополнительной специальностью 050202. 65 «Информатика» | Рабочая учебная программа по дисциплине «Архитектура компьютера»... ... |