СОДЕРЖАНИЕ РАЗДЕЛОВ ДИСЦИПЛИНЫ
КАЗАНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ФАКУЛЬТЕТ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И КИБЕРНЕТИКИ
КАФЕДРА ТЕОРЕТИЧЕСКОЙ КИБЕРНЕТИКИ
Утверждаю
«___»_____________199___г. индекс
06.18.00/ДС.01./КТК
Декан _________________ проф. В.А.Чугунов
РАБОЧАЯ ПРОГРАММА
специального курса «ТЕОРИЯ ГРАФОВ»
График учебного процесса
| Специальность (специализация) | Семестр | Всего часов | Аудитор.занятия | Форма итогового контроля | |
| Лекции | Практика | ||||
| (по выбору) | 3 | 36 | 18 | экзамен | |
Составитель программы – доц. Кугураков В.С.
Обсуждена на заседании кафедры теоретической кибернетики
«___»_____________2009г.
Заведующий кафедрой
теоретической кибернетики ____________________________ проф. Аблаев В.М.
Одобрено учебно-методической комиссией факультета ВМК
«___»_____________199___г.
Председатель
учебно-методической комиссии
факультета ВМК ___________________________ доц. Панкратова О.В.
Предисловие
Дисциплина «Дискретная математика» ставит своей целью ознакомление студентов с важнейшими разделами дискретной математики и её применением в математической (и экономической) кибернетике. В процессе обучения прививаются навыки свободного обращения с такими дискретными объектами, как функции алгебры логики, автоматные функции, графы. Во всех разделах дисциплины большое внимание следует уделять построению алгоритмов решения задач дискретной математики. Это способствует более глубокому пониманию проблематики теории алгоритмов, помогает строить алгоритмы для решения задач, возникающих, в частности, в экономической кибернетике.
|
|
|
I. Введение. - 2 часа.
1. Место дискретной математики в системе математического образования.
2. Соотношение между дискретными и непрерывными подходами при изучении различных явлений.
II. Алгебра логики. - 12 часов.
1. Функции алгебры логики.
2. Реализация функций формулами.
3. Принцип двойственности.
4. Разложение функций по переменным.
5. Совершенные дизъюнктивная и конъюнктивная формы. Полиномы Жегалкина.
6. Полнота и замкнутость. Примеры полных систем.
7. Важнейшие замкнутые классы.
8. Теорема Поста о полноте.
III. Схемы из функциональных элементов (дискретные устройства без памяти). - 4 часа.
1. Задача анализа и синтеза схем из функциональных элементов (СФЭ).
2. Примеры построения СФЭ. Двоичный сумматор.
3. Оценки сложности СФЭ.
IV. Ограниченно - детерминированные функции (конечные автоматы с памятью). - 4 часа.
1. Детерминированные и ограниченно - детерминированные функции.
|
|
|
2. Способы описания ограниченно - детерминированных функций. Диаграммы Мура. Канонические таблицы и уравнения.
3. Построение дискретных устройств, реализующих ограниченно - детерминированные функции.
V. Теория графов. - 14 часов.
1. Терминология. Типы и способы задания графов. Операции над графами.
2. Изоморфизм графов и орграфов. Связность.
3. Реализация графов в трехмерном пространстве. Теорема об укладке планарного графа на сфере.
4. Планарность. Теорема Понтрягина – Куратовского о планарных графах. Теорема Эйлера о соотношении вершин, ребер и граней плоского графа.
5. Раскраски графов. Теорема о хроматических многочленах.
6. Деревья. Элементарные свойства деревьев. Построение минимального остовного дерева (алгоритм Краскала).
7. Обходы графов. Теорема Эйлера о чётных графах и её следствия.
8. Задача о кратчайших путях.
9. Потоки в транспортных сетях. Теорема Форда – Фалкерсона о максимальном потоке и минимальном разрезе. Алгоритм построения максимального потока в сети.
3.2. СОДЕРЖАНИЕ РАЗДЕЛОВ ДИСЦИПЛИНЫ
| № п/п | Название темы и ее содержание | Количество часов | |||
| лекции | семинарские (лаб.-практ.) занятия | ||||
| 1. | Введение. Теория графов как язык дискретной математики для описания структур данных и функционирования систем. История возникновения и развития теории графов. | ||||
| 2. | Основные понятия. | ||||
| Основные определения. Способы задания графов. Подграфы и дополнения. Маршруты, цепи, пути и циклы. Связность и компоненты графа. Операции над графами. Специальные графы. Точки сочленения и разделимые графы. Изоморфизм и 2- изоморфизм. | |||||
| 3. | Деревья, разрезающие множества и циклы.
Деревья, остовы и кодеревья. Элементарные свойства деревьев. Корневые деревья. Перечисление(оценки числа) деревьев. Ранг и цикломатическое число. Базисные циклы. Разрезающие множества. Разрез. Базисные разрезающие множества. Остовы, циклы и разрезающие множества. | ||||
| 4. | Эйлеровы и гамильтоновы графы. Эйлеровы (и полуэйлеровы) графы. Теорема Эйлера. Гамильтоновы (и полугамильтоновы) графы. Теорема Дирака. | ||||
| 5. | Графы и векторные пространства. Группы и поля. Векторное пространство графа. Размерность подпространств циклов и разрезов. Связь между подпространствами циклов и разрезов. Ортогональность подпространств циклов и разрезов. | ||||
| 6. | Ориентированные графы. Графы и отношения. Ориентированные и корневые деревья. Ориентированные эйлеровы графы. Ориентированные остовы и ориентированные эйлеровы цепи. Ориентированные гамильтоновы графы. Ациклические ориентированные графы. Турниры. Цепи Маркова. | ||||
| 7. | Матрицы графов.
Матрица инциденций. Матрица разрезов. Цикломатическая матрица. Соотношение ортогональности. Подматрицы матриц разрезов, инциденций и циклов. Унимодулярные матрицы. Число остовов. Теорема Кэли. Матрица смежности. | ||||
| 8. | Планарность и двойственность. Планарные (плоские) графы. Теорема Эйлера о плоских графах и её следствия о непланарности графов K3,3 и K5. Теорема Понтрягина-Куратовского и другие характеризации планарности. Графы на других поверхностях. Двойственные графы. Планарность и двойственность.. | ||||
| 9. | Связность и паросочетания. Связность или вершинная связность. Реберная связность. Теорема Менгера. Паросочетания в двудольных графах. Теорема Холла и её следствия. | ||||
| 10. | Покрытия и раскраски. Независимые множества и вершинные покрытия. Реберные покрытия. Реберная раскраска и хроматический индекс. Вершинная раскраска и хроматическое число. Хроматические многочлены. Теорема о пяти красках(доказательство). Раскрашивание карт. Теорема о четырех красках. | ||||
| 11. | Введение в теорию матроидов. Основные определения. Примеры матроидов. Фундаментальные свойства. Матроиды и теория графов. Матроиды и “жадный” алгоритм. | ||||
| 12. | Алгоритмы на графах. Транзитивное замыкание. ( Алгоритмы Уоршолла и Уоррена.) Обходы графов в глубину и ширину. Кратчайшие пути. (Алгоритм Дейкстры.) Алгоритм построения эйлерова цикла. (Алгоритм Флойда.) Вычисление хроматического числа графа. (Алгоритм перебора с возвратами.) Построение минимального остова графа. (Алгоритмы Крускала и Прима-Дейкстры.) Потоки в траспортных сетях. Теорема Форда-Фалкерсона о максимальном потоке в транспортной сети. Помечающий алгоритм нахождения максимального потока в транспортной сети. Нахождение максимальных внутренне устойчивых и минимальных внешне устойчивых множеств. (Алгоритмы Магу.) | ||||
РЕКОМЕНДОВАННАЯ ЛИТЕРАТУРА
Основная литература
- Свами М., Тхуласираман К. Графы, сети и алгоритмы. – М.: Мир, 1984.
- Уилсон Р. Введение в теорию графов. – М.: Мир, 1977.
Дополнительная литература
- Берж К. Теория графов и ее применения. – М.: ИЛ, 1962
- Белов В.В., Воробьёв Е.М., Шаталов В.Е. Теория графов. – М.: Высшая школа, 1976.
- Зыков А.А. Основы теории графов. – М.: Наука, 1987.
- Басакер Р., Саати Т. Конечные графы и сети. –М. : Наука, 1974.
- Харари Ф. Теория графов. – М.: Мир, 1973.
- Оре О. Теория графов. – М.: Наука, 1968.
- Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике. – М.: Наука, 1992.
- Яблонский С.В. Введение в дискретную математику. – М.: Наука, 1979, 1986.
- Дискретная математика и математические вопросы кибернетики. Т.1. – М.: Наука, 1968.
- Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. – М.: Мир, 1979.
- Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. – М.: Вильямс, 2000.
- Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы. Построение и анализ. – М.:МЦМНО, 2001.
- Вирт Н. Алгоритмы и структуры данных. – М.: Мир, 1989.
- Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. – М.: Мир, 1975.
- Кнут Д. Искусство программирования для ЭВМ. Т.1.Основные алгоритмы. – М.: Мир, 1976; Т.2; Получисленные алгоритмы. - М.: Мир, 1977; Т.3. Сортировка и поиск. – М.: Мир, 1978.
- Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика – М.: Мир, 1980.
- Липский В. Комбинаторика для программистов. – М.: Мир, 1988.
- Кофман А. Введение в прикладную комбинаторику. – М.: Наука, 1975.
- Тарьян Р.Э. Сложность комбинаторных алгоритмов. В кн: Кибернетический сборник, новая серия, вып.17. – М.: Мир, 1980, с.60 - 113.
- Форд Л.Р., Фалкерсон . Д.Л.Потоки в сетях. – М.: Мир, 1966.
- Ху Т. Целочисленное программирование и потоки в сетях. – М.: Мир, 1974.
- Кристофидес П. Теория графов. Алгоритмический подход.– М.: Мир, 1978.
- Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. – М.: Мир, 1982.
- Евстигнеев В.А. Применение теории графов программировании. .– М.: Мир, 1985.
- Математическая энциклопедия. Т.1. А-Г. – М.: Советская Энциклопедия, 1977. – Стб. 1105-1121.
СОДЕРЖАНИЕ РАЗДЕЛОВ ДИСЦИПЛИНЫ
Введение.
Теория графов как язык дискретной математики для описания структур данных и функционирования систем.
История возникновения и развития теории графов.
Дата добавления: 2018-05-12; просмотров: 195; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!