МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ
федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
«Мурманский государственный гуманитарный университет»
(ФГБОУ ВПО «МГГУ»)
Учебно-методический комплекс
ФТД: УНИВЕРСАЛЬНАЯ АЛГЕБРА
Основная образовательная программа подготовки специалиста
по специальности
050201.65 Математика с дополнительной специальностью «Информатика»
Утверждено на заседании кафедры
математики и математических методов
в экономике факультета
физико-математического образования,
информатики и программирования
(протокол № 6 от 27 февраля 2013 г.)
Зав. кафедрой _______________О.М. Мартынов
Раздел 1. Программа учебной дисциплины.
Структура программы учебной дисциплины
1. 1 Автор программы: Зубова Ю.В., кандидат физ-мат. наук, доцент.
1.2 Рецензенты: к.п.н., доцент Иванчук Н.В., кандидат физ.-мат. наук, доцент кафедры Высшей математики и ПО ЭВМ МГТУ Беляев Владимир Яковлевич.
1.3 Пояснительная записка:
Цели: изучение понятий: бинарного отношения и его свойств, транзитивного замыкания, графа и его свойств, деревьев их свойств, коды Прюффера, Эйлеровы и Гамильтоновы графы, расстояния в графах.
Задачи: предлагаемый курс имеет естественные межпредметные связи с курсами математической логики и информатики. Успешное усвоение дискретной математики - залог более лёгкого и глубокого изучения этих курсов.
Требования к уровню освоения содержания дисциплины (должны знать, должны уметь):
должны знать: понятия и утверждения, входящие в содержание дисциплины, доказательства теорем.
должны уметь: решать задачи по разделам курса, применять теоретический материал, творчески подходить к решению профессиональных задач, ориентироваться в нестандартных условиях и ситуациях, анализировать возникающие проблемы.
1.4 Извлечение из ГОС ВПО
Дискретная математика
Рекуррентные соотношения. Задачи, приводящие к рекуррентным соотношениям. Числа Фибоначчи. Способы решения рекуррентных соотношений.
Суммы и рекуррентности. Преобразования сумм. Кратные суммы. Некоторые методы суммирования. Целочисленные функции. Введение в асимптотические методы. Символы ~, о, О. Основные правила использования этих символов. Асимптотические решения рекуррентных соотношений. Формула суммирования Эйлера.
Основные понятия теории графов. (псевдограф, мультиграф, граф и их ориентированные аналоги). Степень вершины графа. Теорема о сумме степеней вершин графа и ее следствие. Подграф. Путь, цепь, простая цепь, цикл, простой цикл.
Связные графы. Компоненты связности графа, их число. Число различных графов с p вершинами. Изоморфные графы. Эйлеровы графы. Критерий эйлеровости. Гамильтоновы графы.
Деревья. Характеризационная теорема. Укладка графа. Планарные графы. Плоские графы. Теорема Эйлера и ее следствия. Непланарность графов K5 и K3,3. Раскраска вершин и ребер графа. Двудольные графы. Теорема Кенига. Раскрашиваемость вершин планарного графа пятью красками. Гипотеза четырех красок.
1.5 Объем дисциплины и виды учебной работы
(для всех специальностей, на которых читается данная дисциплина):
№ п/п
|
Шифр и наименование специальности
|
Курс
|
Семестр
|
Виды учебной работы в часах
|
Вид итогового контроля
|
Трудо-емкость
|
Всего аудит.
|
ЛК
|
ПР/
СМ
|
ЛБ
|
Сам.
работа
|
|
032100 Математика с дополнительной специальностью
|
3
|
7
|
72
|
39
|
25
|
14
|
-
|
33
|
Экзамен
|
1.6 Содержание дисциплины.
1.6.1. Разделы дисциплины и виды занятий (в часах). Примерное распределение учебного времени:
№
|
Наименование раздела темы
|
Количество часов
|
Форма отчета
|
всего
|
ЛК
|
ПР
|
КР
|
СР
|
КОЛ
|
Зачет
|
Экзамен
|
|
§1. Бинарные отношения.
Бинарные отношения и его свойства.
Отношения эквивалентности и порядка.
§2. Теория графов
Понятие графов.
Операции с графами.
Степени вершин графов.
Способы задания графов.
Маршруты, цепи, циклы.
Эйлеровы графы.
Гамильтоновы графы.
Двудольные графы и жесткость ферм.
Деревья.
Коды Прюфера.
Задача об остове минимального веса.
Мультиграфы.
Расстояния в графах.
|
92,9
|
25
2
23
|
14
2
12
|
13,2
|
33
4
29
|
|
-
|
7,7
|
1.6.2. Содержание разделов дисциплины.
§1. Бинарные отношения.
1. Бинарные отношения и его свойства.
Бинарное отношение, тернарное отношение,  -арное отношение, булеан, свойства отношений рефлективность, симметричность, транзитивность. Транзитивное замыкание.
2. Отношения эквивалентности и порядка.
Отношение эквивалентности, классы эквивалентности. Отношение порядка, отношение частичного порядка.
§2. Теория графов
Понятие графов.
Понятие графа, примеры графов. Изоморфные графы.
Операции с графами.
Дополнение графов, объединение графов, соединение графов. Теорема о рукопожатиях.
Степени вершин графов.
Понятие степени вершин графа. Теоремы о сумме степеней вершин в графе, числе нечетных вершин, о числе вершин с одинаковыми степенями.
Способы задания графов.
Изображение графов, список ребер и вершин, матрицы смежности и инцидентности для ориентированных и неориентированных графов.
Маршруты, цепи, циклы.
Понятие маршрута, цикла, цепи.
Эйлеровы графы.
Понятие Эйлерова графа. Теорема Эйлера. Следствие.
Гамильтоновы графы.
Гамильтонов графы. Связь между гамильтоновостью и эйлеровостью графа. Точки сочленения и мосты. Свойства гамильтоновых графов.
Двудольные графы и жесткость ферм.
Понятие двудольного графа. Теорема о двудольном графе. Фермы. Теорема о жесткости ферм.
Деревья.
Понятие дерева. Свойства деревьев.
Коды Прюфера.
Построении кода Прюфера. Число деревьев с вершинами.
Задача об остове минимального веса.
Понятие остова дерева. Алгоритм Прима. Минимальный и максимальный остов графа.
Мультиграфы.
Понятие взвешенного графа (сети). Матрица расстояний.
Расстояния в графах.
Алгоритм Дейкстры и Форда-Беллмана нахождения минимального и максимального расстояния в графе.
1.6.3. Темы для самостоятельного изучения.
№ п/п
|
Наименование раздела
дисциплины.
Тема.
|
Форма самостоятельной работы
|
Кол-во часов
|
Форма контроля выполнения самостоятельной работы
|
|
§1. Бинарные отношения.
1. Бинарные отношения и его свойства.
2. Отношения эквивалентности и порядка.
§2. Теория графов
Понятие графов.
Операции с графами.
Степени вершин графов.
Способы задания графов.
Маршруты, цепи, циклы.
Эйлеровы графы.
Гамильтоновы графы.
Двудольные графы и жесткость ферм.
Деревья.
Коды Прюфера.
Задача об остове минимального веса.
12. Мультиграфы.
13. Расстояния в графах.
|
- вопросы для самостоятельного изучения,
- домашние работы
- контрольная работа
|
30
|
- проверка домашних работ,
- проверка контрольной работы,
- доп. вопросы на зачете
|
1.7. Методические рекомендации по организации изучения дисциплины.
1.7.1. Тематика и планы аудиторной работы студентов по изученному материалу:
Практические занятия.
Практическое занятие по теме «Бинарные отношения и их свойства» (2 часа)
Бинарное отношение, тернарное отношение, -арное отношение, булеан, свойства отношений рефлективность, симметричность, транзитивность. Транзитивное замыкание. Отношение эквивалентности, классы эквивалентности. Отношение порядка, отношение частичного порядка.
Литература:
Новиков Ф. А.Дискретная математика для программистов : учеб. пособие для студ. вузов, обуч. по направл. подготовки дипломир. специалистов "Информатика и вычисл. техника" / Ф. А. Новиков. - 2-е изд. - СПб. : Питер, 2006. Гриф
Яблонский С. В. Введение в дискретную математику : учеб. пособие для студ. вузов, обуч. по спец. "Прикладная математика" / С. В. Яблонский ; Моск. гос. ун-т им. М. В. Ломоносова. - 4-е изд., стер. - М. : Высшая школа, 2006. Гриф
Судоплатов, С.В. Дискретная математика: учебник для вузов/ С. В. Судоплатов, Е. В. Овчинникова - М.: Новосибирск; ИНФРА-М: НГТУ, 2005. гриф.
Белов В. В. и др. Теория графов. – М.: Высш. Школа, 1976.
Басакер Р., Саати Т. Конечные графы и сети. – М.: Наука, 1974.
Берж К. Теория графов и ее применения. – М.: ИЛ, 1962.
Зыков А. А. Теория конечных графов. – Новосибирск: Наука, 1969.
Оре О. Теория графов. – М.: Наука,1968.
Практическое занятие по теме «Графы, их вершины, рёбра и дуги» (2 часа).
Литература:
Новиков Ф. А.Дискретная математика для программистов : учеб. пособие для студ. вузов, обуч. по направл. подготовки дипломир. специалистов "Информатика и вычисл. техника" / Ф. А. Новиков. - 2-е изд. - СПб. : Питер, 2006. Гриф
Яблонский С. В. Введение в дискретную математику : учеб. пособие для студ. вузов, обуч. по спец. "Прикладная математика" / С. В. Яблонский ; Моск. гос. ун-т им. М. В. Ломоносова. - 4-е изд., стер. - М. : Высшая школа, 2006. Гриф
Судоплатов, С.В. Дискретная математика: учебник для вузов/ С. В. Судоплатов, Е. В. Овчинникова - М.: Новосибирск; ИНФРА-М: НГТУ, 2005. гриф.
Белов В. В. и др. Теория графов. – М.: Высш. Школа, 1976.
Басакер Р., Саати Т. Конечные графы и сети. – М.: Наука, 1974.
Берж К. Теория графов и ее применения. – М.: ИЛ, 1962.
Зыков А. А. Теория конечных графов. – Новосибирск: Наука, 1969.
Оре О. Теория графов. – М.: Наука,1968.
Практическое занятие по теме «Изоморфные графы.» (2 часа).
Литература:
Новиков Ф. А.Дискретная математика для программистов : учеб. пособие для студ. вузов, обуч. по направл. подготовки дипломир. специалистов "Информатика и вычисл. техника" / Ф. А. Новиков. - 2-е изд. - СПб. : Питер, 2006. Гриф
Яблонский С. В. Введение в дискретную математику : учеб. пособие для студ. вузов, обуч. по спец. "Прикладная математика" / С. В. Яблонский ; Моск. гос. ун-т им. М. В. Ломоносова. - 4-е изд., стер. - М. : Высшая школа, 2006. Гриф
Судоплатов, С.В. Дискретная математика: учебник для вузов/ С. В. Судоплатов, Е. В. Овчинникова - М.: Новосибирск; ИНФРА-М: НГТУ, 2005. гриф.
Белов В. В. и др. Теория графов. – М.: Высш. Школа, 1976.
Басакер Р., Саати Т. Конечные графы и сети. – М.: Наука, 1974.
Берж К. Теория графов и ее применения. – М.: ИЛ, 1962.
Зыков А. А. Теория конечных графов. – Новосибирск: Наука, 1969.
Оре О. Теория графов. – М.: Наука,1968.
Практическое занятие по теме «Операции над графами. » (2 часа).
Литература:
Новиков Ф. А.Дискретная математика для программистов : учеб. пособие для студ. вузов, обуч. по направл. подготовки дипломир. специалистов "Информатика и вычисл. техника" / Ф. А. Новиков. - 2-е изд. - СПб. : Питер, 2006. Гриф
Яблонский С. В. Введение в дискретную математику : учеб. пособие для студ. вузов, обуч. по спец. "Прикладная математика" / С. В. Яблонский ; Моск. гос. ун-т им. М. В. Ломоносова. - 4-е изд., стер. - М. : Высшая школа, 2006. Гриф
Судоплатов, С.В. Дискретная математика: учебник для вузов/ С. В. Судоплатов, Е. В. Овчинникова - М.: Новосибирск; ИНФРА-М: НГТУ, 2005. гриф.
Белов В. В. и др. Теория графов. – М.: Высш. Школа, 1976.
Басакер Р., Саати Т. Конечные графы и сети. – М.: Наука, 1974.
Берж К. Теория графов и ее применения. – М.: ИЛ, 1962.
Зыков А. А. Теория конечных графов. – Новосибирск: Наука, 1969.
Оре О. Теория графов. – М.: Наука,1968.
Практическое занятие по теме «Эйлеровы и гамильтоновы графы. » (2 часа).
Литература:
Новиков Ф. А.Дискретная математика для программистов : учеб. пособие для студ. вузов, обуч. по направл. подготовки дипломир. специалистов "Информатика и вычисл. техника" / Ф. А. Новиков. - 2-е изд. - СПб. : Питер, 2006. Гриф
Яблонский С. В. Введение в дискретную математику : учеб. пособие для студ. вузов, обуч. по спец. "Прикладная математика" / С. В. Яблонский ; Моск. гос. ун-т им. М. В. Ломоносова. - 4-е изд., стер. - М. : Высшая школа, 2006. Гриф
Судоплатов, С.В. Дискретная математика: учебник для вузов/ С. В. Судоплатов, Е. В. Овчинникова - М.: Новосибирск; ИНФРА-М: НГТУ, 2005. гриф.
Белов В. В. и др. Теория графов. – М.: Высш. Школа, 1976.
Басакер Р., Саати Т. Конечные графы и сети. – М.: Наука, 1974.
Берж К. Теория графов и ее применения. – М.: ИЛ, 1962.
Зыков А. А. Теория конечных графов. – Новосибирск: Наука, 1969.
Оре О. Теория графов. – М.: Наука,1968.
Практическое занятие по теме «Способы задания псевдографов. » (1 часа).
Литература:
Новиков Ф. А.Дискретная математика для программистов : учеб. пособие для студ. вузов, обуч. по направл. подготовки дипломир. специалистов "Информатика и вычисл. техника" / Ф. А. Новиков. - 2-е изд. - СПб. : Питер, 2006. Гриф
Яблонский С. В. Введение в дискретную математику : учеб. пособие для студ. вузов, обуч. по спец. "Прикладная математика" / С. В. Яблонский ; Моск. гос. ун-т им. М. В. Ломоносова. - 4-е изд., стер. - М. : Высшая школа, 2006. Гриф
Судоплатов, С.В. Дискретная математика: учебник для вузов/ С. В. Судоплатов, Е. В. Овчинникова - М.: Новосибирск; ИНФРА-М: НГТУ, 2005. гриф.
Белов В. В. и др. Теория графов. – М.: Высш. Школа, 1976.
Басакер Р., Саати Т. Конечные графы и сети. – М.: Наука, 1974.
Берж К. Теория графов и ее применения. – М.: ИЛ, 1962.
Зыков А. А. Теория конечных графов. – Новосибирск: Наука, 1969.
Оре О. Теория графов. – М.: Наука,1968.
Практическое занятие по теме «Деревья и их свойства. » (1 часа).
Литература:
Новиков Ф. А.Дискретная математика для программистов : учеб. пособие для студ. вузов, обуч. по направл. подготовки дипломир. специалистов "Информатика и вычисл. техника" / Ф. А. Новиков. - 2-е изд. - СПб. : Питер, 2006. Гриф
Яблонский С. В. Введение в дискретную математику : учеб. пособие для студ. вузов, обуч. по спец. "Прикладная математика" / С. В. Яблонский ; Моск. гос. ун-т им. М. В. Ломоносова. - 4-е изд., стер. - М. : Высшая школа, 2006. Гриф
Судоплатов, С.В. Дискретная математика: учебник для вузов/ С. В. Судоплатов, Е. В. Овчинникова - М.: Новосибирск; ИНФРА-М: НГТУ, 2005. гриф.
Белов В. В. и др. Теория графов. – М.: Высш. Школа, 1976.
Басакер Р., Саати Т. Конечные графы и сети. – М.: Наука, 1974.
Берж К. Теория графов и ее применения. – М.: ИЛ, 1962.
Зыков А. А. Теория конечных графов. – Новосибирск: Наука, 1969.
Оре О. Теория графов. – М.: Наука,1968.
Практическое занятие по теме «Расстояния в графах. » (2 часа).
Литература:
Новиков Ф. А.Дискретная математика для программистов : учеб. пособие для студ. вузов, обуч. по направл. подготовки дипломир. специалистов "Информатика и вычисл. техника" / Ф. А. Новиков. - 2-е изд. - СПб. : Питер, 2006. Гриф
Яблонский С. В. Введение в дискретную математику : учеб. пособие для студ. вузов, обуч. по спец. "Прикладная математика" / С. В. Яблонский ; Моск. гос. ун-т им. М. В. Ломоносова. - 4-е изд., стер. - М. : Высшая школа, 2006. Гриф
Судоплатов, С.В. Дискретная математика: учебник для вузов/ С. В. Судоплатов, Е. В. Овчинникова - М.: Новосибирск; ИНФРА-М: НГТУ, 2005. гриф.
Белов В. В. и др. Теория графов. – М.: Высш. Школа, 1976.
Басакер Р., Саати Т. Конечные графы и сети. – М.: Наука, 1974.
Берж К. Теория графов и ее применения. – М.: ИЛ, 1962.
Зыков А. А. Теория конечных графов. – Новосибирск: Наука, 1969.
Оре О. Теория графов. – М.: Наука,1968.
1.8 Учебно-методическое обеспечение дисциплины.
1.8.1. Рекомендуемая литература:
Основная
Новиков Ф. А.Дискретная математика для программистов : учеб. пособие для студ. вузов, обуч. по направл. подготовки дипломир. специалистов "Информатика и вычисл. техника" / Ф. А. Новиков. - 2-е изд. - СПб. : Питер, 2006. Гриф
Яблонский С. В. Введение в дискретную математику : учеб. пособие для студ. вузов, обуч. по спец. "Прикладная математика" / С. В. Яблонский ; Моск. гос. ун-т им. М. В. Ломоносова. - 4-е изд., стер. - М. : Высшая школа, 2006. Гриф
Судоплатов, С.В. Дискретная математика: учебник для вузов/ С. В. Судоплатов, Е. В. Овчинникова - М.: Новосибирск; ИНФРА-М: НГТУ, 2005. гриф.
Дополнительная
Белов В. В. и др. Теория графов. – М.: Высш. Школа, 1976.
Басакер Р., Саати Т. Конечные графы и сети. – М.: Наука, 1974.
Берж К. Теория графов и ее применения. – М.: ИЛ, 1962.
Зыков А. А. Теория конечных графов. – Новосибирск: Наука, 1969.
Оре О. Теория графов. – М.: Наука,1968.
1.9 Материально-техническое обеспечение дисциплины.
1.9.1. Перечень используемых технических средств: компьютеры, лаборатории вычислительной математики.
1.9.2. Перечень используемых пособий - электронная библиотека кабинетов №11, №13.
1.9.3.Перечень видео- и аудиоматериалов программного обеспечения. Математические пакеты Maple, Mathematica 5.
1.10 Примерные зачетные тестовые задания.
1.11 Примерный перечень вопросов к зачету (экзамену).
1.12 Комплект экзаменационных билетов.
1.13 Примерная тематика рефератов.
1.15 Примерная тематика квалификационных (дипломных) работ.
1.16 Методика(и) исследования (если есть).
1.17 Бально-рейтинговая система, используемая преподавателем для оценивания знаний студентов по данной дисциплине.
РАЗДЕЛ 2. Методические указания по изучению дисциплины (или ее разделов) и контрольные задания для студентов заочной формы обучения.
РАЗДЕЛ 3. Содержательный компонент теоретического материала.
Лекция № 1. Бинарные отношения.
Бинарное отношение, тернарное отношение, -арное отношение, булеан, свойства отношений рефлективность, симметричность, транзитивность. Транзитивное замыкание. Отношение эквивалентности, классы эквивалентности. Отношение порядка, отношение частичного порядка.
Литература:
Судоплатов С. В., Овчинникова Е. В. Дискретная математика: Учебник. – М.: ИНФРА – М; Новосибирск: НГТУ, 2005.
Белов В. В. и др. Теория графов. – М.: Высш. Школа, 1976.
Басакер Р., Саати Т. Конечные графы и сети. – М.: Наука, 1974.
Берж К. Теория графов и ее применения. – М.: ИЛ, 1962.
Зыков А. А. Теория конечных графов. – Новосибирск: Наука, 1969.
Оре О. Теория графов. – М.: Наука,1968.
Лекция № 2. Понятие графа.
Понятие графа, примеры графов. Изоморфные графы.
Литература:
Судоплатов С. В., Овчинникова Е. В. Дискретная математика: Учебник. – М.: ИНФРА – М; Новосибирск: НГТУ, 2005.
Белов В. В. и др. Теория графов. – М.: Высш. Школа, 1976.
Басакер Р., Саати Т. Конечные графы и сети. – М.: Наука, 1974.
Берж К. Теория графов и ее применения. – М.: ИЛ, 1962.
Зыков А. А. Теория конечных графов. – Новосибирск: Наука, 1969.
Оре О. Теория графов. – М.: Наука,1968.
Лекция № 3. Операции с графами.
Дополнение графов, объединение графов, соединение графов. Теорема о рукопожатиях.
Литература:
Судоплатов С. В., Овчинникова Е. В. Дискретная математика: Учебник. – М.: ИНФРА – М; Новосибирск: НГТУ, 2005.
Белов В. В. и др. Теория графов. – М.: Высш. Школа, 1976.
Басакер Р., Саати Т. Конечные графы и сети. – М.: Наука, 1974.
Берж К. Теория графов и ее применения. – М.: ИЛ, 1962.
Зыков А. А. Теория конечных графов. – Новосибирск: Наука, 1969.
Оре О. Теория графов. – М.: Наука,1968.
Лекция № 4. Степени вершин графов.
Понятие степени вершин графа. Теоремы о сумме степеней вершин в графе, числе нечетных вершин, о числе вершин с одинаковыми степенями.
Литература:
Судоплатов С. В., Овчинникова Е. В. Дискретная математика: Учебник. – М.: ИНФРА – М; Новосибирск: НГТУ, 2005.
Белов В. В. и др. Теория графов. – М.: Высш. Школа, 1976.
Басакер Р., Саати Т. Конечные графы и сети. – М.: Наука, 1974.
Берж К. Теория графов и ее применения. – М.: ИЛ, 1962.
Зыков А. А. Теория конечных графов. – Новосибирск: Наука, 1969.
Оре О. Теория графов. – М.: Наука,1968.
Лекция № 5. Способы задания графов.
Изображение графов, список ребер и вершин, матрицы смежности и инцидентности для ориентированных и неориентированных графов.
Литература:
Судоплатов С. В., Овчинникова Е. В. Дискретная математика: Учебник. – М.: ИНФРА – М; Новосибирск: НГТУ, 2005.
Белов В. В. и др. Теория графов. – М.: Высш. Школа, 1976.
Басакер Р., Саати Т. Конечные графы и сети. – М.: Наука, 1974.
Берж К. Теория графов и ее применения. – М.: ИЛ, 1962.
Зыков А. А. Теория конечных графов. – Новосибирск: Наука, 1969.
Оре О. Теория графов. – М.: Наука,1968.
Лекция № 6. Маршруты, цепи, циклы.
Понятие маршрута, цикла, цепи.
Литература:
Судоплатов С. В., Овчинникова Е. В. Дискретная математика: Учебник. – М.: ИНФРА – М; Новосибирск: НГТУ, 2005.
Белов В. В. и др. Теория графов. – М.: Высш. Школа, 1976.
Басакер Р., Саати Т. Конечные графы и сети. – М.: Наука, 1974.
Берж К. Теория графов и ее применения. – М.: ИЛ, 1962.
Зыков А. А. Теория конечных графов. – Новосибирск: Наука, 1969.
Оре О. Теория графов. – М.: Наука,1968.
Лекция №7. Эйлеровы графы.
Понятие Эйлерова графа. Теорема Эйлера. Следствие.
Литература:
Судоплатов С. В., Овчинникова Е. В. Дискретная математика: Учебник. – М.: ИНФРА – М; Новосибирск: НГТУ, 2005.
Белов В. В. и др. Теория графов. – М.: Высш. Школа, 1976.
Басакер Р., Саати Т. Конечные графы и сети. – М.: Наука, 1974.
Берж К. Теория графов и ее применения. – М.: ИЛ, 1962.
Зыков А. А. Теория конечных графов. – Новосибирск: Наука, 1969.
Оре О. Теория графов. – М.: Наука,1968.
Лекция № 8. Гамильтоновы графы.
Гамильтонов графы. Связь между гамельтоновостью и эйлеровостью графа. Точки сочленения и мосты. Свойства гамильтоновых графов.
Литература:
Судоплатов С. В., Овчинникова Е. В. Дискретная математика: Учебник. – М.: ИНФРА – М; Новосибирск: НГТУ, 2005.
Белов В. В. и др. Теория графов. – М.: Высш. Школа, 1976.
Басакер Р., Саати Т. Конечные графы и сети. – М.: Наука, 1974.
Берж К. Теория графов и ее применения. – М.: ИЛ, 1962.
Зыков А. А. Теория конечных графов. – Новосибирск: Наука, 1969.
Оре О. Теория графов. – М.: Наука,1968.
Лекция № 9. Двудольные графы и жесткость ферм.
Понятие двудольного графа. Теорема о двудольном графе. Фермы. Теорема о жесткости ферм.
Литература:
Судоплатов С. В., Овчинникова Е. В. Дискретная математика: Учебник. – М.: ИНФРА – М; Новосибирск: НГТУ, 2005.
Белов В. В. и др. Теория графов. – М.: Высш. Школа, 1976.
Басакер Р., Саати Т. Конечные графы и сети. – М.: Наука, 1974.
Берж К. Теория графов и ее применения. – М.: ИЛ, 1962.
Зыков А. А. Теория конечных графов. – Новосибирск: Наука, 1969.
Оре О. Теория графов. – М.: Наука,1968.
Лекция № 10. Деревья. Коды Прюфера.
Понятие дерева. Свойства деревьев. Построении кода Прюфера. Число деревьев с вершинами.
Литература:
Судоплатов С. В., Овчинникова Е. В. Дискретная математика: Учебник. – М.: ИНФРА – М; Новосибирск: НГТУ, 2005.
Белов В. В. и др. Теория графов. – М.: Высш. Школа, 1976.
Басакер Р., Саати Т. Конечные графы и сети. – М.: Наука, 1974.
Берж К. Теория графов и ее применения. – М.: ИЛ, 1962.
Зыков А. А. Теория конечных графов. – Новосибирск: Наука, 1969.
Оре О. Теория графов. – М.: Наука,1968.
Лекция № 11. Задача об остове минимального веса.
Понятие остова дерева. Алгоритм Прима. Минимальный и максимальный остов графа.
Литература:
Судоплатов С. В., Овчинникова Е. В. Дискретная математика: Учебник. – М.: ИНФРА – М; Новосибирск: НГТУ, 2005.
Белов В. В. и др. Теория графов. – М.: Высш. Школа, 1976.
Басакер Р., Саати Т. Конечные графы и сети. – М.: Наука, 1974.
Берж К. Теория графов и ее применения. – М.: ИЛ, 1962.
Зыков А. А. Теория конечных графов. – Новосибирск: Наука, 1969.
Оре О. Теория графов. – М.: Наука,1968.
Лекция № 12. Мультиграфы. Расстояния в графах.
Понятие взвешенного графа (сети). Матрица расстояний.
Алгоритм Дейкстры и Форда-Беллмана нахождения минимального и максимального расстояния в графе.
Литература:
Судоплатов С. В., Овчинникова Е. В. Дискретная математика: Учебник. – М.: ИНФРА – М; Новосибирск: НГТУ, 2005.
Белов В. В. и др. Теория графов. – М.: Высш. Школа, 1976.
Басакер Р., Саати Т. Конечные графы и сети. – М.: Наука, 1974.
Берж К. Теория графов и ее применения. – М.: ИЛ, 1962.
Зыков А. А. Теория конечных графов. – Новосибирск: Наука, 1969.
Оре О. Теория графов. – М.: Наука,1968.
РАЗДЕЛ 4. Словарь терминов (глоссарий).
РАЗДЕЛ 5. Практикум по решению задач по темам лекций.
РАЗДЕЛ 6. Изменения в рабочей программе, которые произошли после утверждения программы.
Характер изменений в программе
|
Номер и дата протокола заседания кафедры, на котором было принято данное решение
|
Подпись заведующего кафедрой, утверждающего внесенное изменение
|
Подпись декана факультета (проректора по учебной работе), утверждающего данное изменение
|
|
|
|
|
РАЗДЕЛ 7. Учебные занятия по дисциплине ведут:
Ф.И.О., ученое звание и степень преподавателя
|
Учебный год
|
Факультет
|
Специальность
|
Зубова Ю.В., кандидат физ-мат. наук, доцент.
|
2010-2011
|
ФМОИиП
|
052100.00 Математика с дополнительной специальностью
|
Зубова Ю.В., кандидат физ-мат. наук, доцент.
|
2011-2012
|
ФМОИиП
|
052100.00 Математика с дополнительной специальностью
|
Богомолова И.В., кандидат физ-мат. наук, доцент.
|
2012-2013
|
ФМОИиП
|
052100.00 Математика с дополнительной специальностью
| |
