Тема 11. Циклы в графах, обходы графов
Учреждение образования
ВЫСШИЙ ГОСУДАРСТВЕННЫЙ КОЛЛЕДЖ СВЯЗИ
МЕТОДИЧЕСКИЕ УКАЗАНИЯ И КОНТРОЛЬНЫЕ ЗАДАНИЯ
по дисциплине
«ДИСКРЕТНАЯ МАТЕМАТИКА»
для студентов уровня ВО заочной формы обучения
специальности 1-45 01 03 «Сети телекоммуникаций»
МИНСК 2009
Составитель: Петрович А.В.
Рецензент: Колодная Е.М.
Издание утверждено на заседании кафедры М и Ф
12.04.2009г., протокол № 8
Зав. кафедрой Гладков Л.Л.
ВВЕДЕНИЕ
В соответствии с учебным планом студенты третьего курса ВГКС специальности 1-45 01 03 – Сети телекоммуникаций в шестом семестре выполняют контрольную работу по дискретной математике.
Для того, чтобы успешно ее выполнить, необходимо изучить сначала теоретический материал по одному из учебников, указанных в списке литературы, и конспекту обзорных лекций. При этом следует ориентироваться на рабочую программу, приведенную ниже. Затем внимательно разберите решения примеров из данной методической разработки и выполните задания для самопроверки.
При оформлении контрольной работы для замечаний преподавателя оставляются поля. Перед решением задачи полностью записывается ее условие. Решение следует сопровождать короткими пояснениями с указанием использованных формул и теорем. Рисунки должны быть выполнены аккуратно. В конце работы ставится дата ее завершения, приводится список проработанной литературы. Работа подписывается.
|
|
|
Выбор варианта контрольной работы определяется двумя последними цифрами номера зачетной книжки. Получив проверенную работу, студент обязан выполнить указания, сделанные рецензентом. Если работа не зачтена, следует сделать работу над ошибками в той же тетради и представить работу на повторную рецензию.
К сдаче экзамена или зачета допускаются студенты, имеющие на руках зачтенные контрольные работы.
Таблица 1
Варианты контрольных заданий
| № варианта | №№ задач | ||||||
| 1 | 1 | 11 | 21 | 31 | 41 | 51 | 61 |
| 2 | 2 | 12 | 22 | 32 | 42 | 52 | 62 |
| 3 | 3 | 13 | 23 | 33 | 43 | 53 | 63 |
| 4 | 4 | 14 | 24 | 34 | 44 | 54 | 64 |
| 5 | 5 | 15 | 25 | 35 | 45 | 55 | 65 |
| 6 | 6 | 16 | 26 | 36 | 46 | 56 | 66 |
| 7 | 7 | 17 | 27 | 37 | 47 | 57 | 67 |
| 8 | 8 | 18 | 28 | 38 | 48 | 58 | 68 |
| 9 | 9 | 19 | 29 | 39 | 49 | 59 | 69 |
| 10 | 10 | 20 | 30 | 40 | 50 | 60 | 70 |
| 11 | 1 | 12 | 23 | 34 | 45 | 56 | 67 |
| 12 | 2 | 13 | 24 | 35 | 46 | 57 | 68 |
| 13 | 3 | 14 | 25 | 36 | 47 | 58 | 69 |
| 14 | 4 | 15 | 26 | 37 | 48 | 59 | 70 |
| 15 | 5 | 16 | 27 | 38 | 49 | 60 | 61 |
| 16 | 6 | 17 | 28 | 39 | 50 | 51 | 62 |
| 17 | 7 | 18 | 29 | 40 | 41 | 52 | 63 |
| 18 | 8 | 19 | 30 | 31 | 42 | 53 | 64 |
| 19 | 9 | 20 | 21 | 32 | 43 | 54 | 65 |
| 20 | 10 | 11 | 22 | 33 | 44 | 55 | 66 |
| 21 | 10 | 19 | 28 | 37 | 46 | 55 | 64 |
| 22 | 9 | 18 | 27 | 36 | 45 | 54 | 63 |
| 23 | 8 | 17 | 26 | 35 | 44 | 53 | 62 |
| 24 | 7 | 16 | 25 | 34 | 43 | 52 | 61 |
| 25 | 6 | 15 | 24 | 33 | 42 | 51 | 70 |
| 26 | 5 | 14 | 23 | 32 | 41 | 60 | 69 |
| 27 | 4 | 13 | 22 | 31 | 50 | 59 | 68 |
| 28 | 3 | 12 | 21 | 40 | 49 | 58 | 67 |
| 29 | 2 | 11 | 30 | 39 | 48 | 57 | 66 |
| 30 | 1 | 20 | 29 | 38 | 47 | 56 | 65 |
РАБОЧАЯ ПРОГРАММА
|
|
|
Раздел 1. Множества
Тема 1. Дискретные множества
Дискретные множества. Способы задания и операции над множествами. Булеан. Мощность прямого произведения множеств.
Тема 2. Элементы комбинаторики
Число размещений, перестановок и сочетаний, число разбиений на множества заданной мощности.
Раздел 2. Булевые функции
Тема 3. Булевые переменные и функции
Булевые переменные и функции. Операции булевой алгебры. Задание булевых функций формулами и с помощью таблицы истинности. Эквивалентные формулы, основные эквивалентности.
Тема 4. Дизъюнктивная и конъюнктивная нормальные формы
Дизъюнктивная и конъюнктивная нормальные формы (ДНФ, КНФ) формул и их построение. Совершенные ДНФ, КНФ. Минимизация ДНФ, КНФ. Полиномиальное разложение: СПНФ, канонический полином Жегалкина, арифметический полином.
|
|
|
Раздел 3. Основы теории алгоритмов
Тема 5. Понятие алгоритма и сложность алгоритма
Понятие алгоритма и оценка сложности алгоритма. Эвристические алгоритмы. «Жадные» алгоритмы.
Раздел 4. Теория графов
Тема 6. Основные понятия теории графов
Граф как абстрактное математическое понятие. Вершины, рёбра, дуги. Понятие инцидентности. Способы задания графов. Матрицы графов и их свойства. Степени вершин графа. Теорема о вычислении вершин нечётной степени в графе (лемма о рукопожатиях).
Тема 7. Виды графов, операции над ними
Простой граф, мультиграф, псевдограф. Неориентированный и ориентированный графы (орграфы). Полный граф, звёздный граф и т.д. Двудольный граф, критерий двудольности. Понятие изоморфности графов. Инварианты.
Части графа. Подграфы. Дополнение графа. Реберный граф. Основные операции над графами.
Тема 8. Пути в графах, связность
Пути в графах. Меры графов (эксцентриситет, диаметр, радиус, сумма расстояний, центр и центр тяжести). Связность графов. Компоненты графов. Теорема Менгера.
Тема 9. Деревья и их свойства
|
|
|
Деревья и их свойства. Остовные (каркасные) деревья в графе, алгоритмы построения. Теорема Кирхгоффа о количестве всех остовных (каркасных) деревьев в графе.
Тема 10. Подструктуры графов
Подструктуры графов. Клика. Нахождение наибольшей клики с помощью «жадного» алгоритма. Независимое множество вершин. Паросочетания. Вершинные и реберные покрытия.
Тема 11. Циклы в графах, обходы графов
Циклы в графах. Базовые (фундаментальные) циклы в графах. Обходы графов: Эйлеров и Гамильтонов циклы в графе. Алгоритм Флери. Теоремы о существовании Эйлерова и Гамильтонова циклов в графе.
Понятие «почти все» графы. Теоремы о «почти всех» графах.
Тема 12.Планарные графы
Планарные графы. Теоремы Эйлера и Куратовского о планарных графах. Алгоритм определения планарности в гамильтоновом графе (метод цикла).
Тема 13. Раскраски графов
Раскраски. Хроматическое число. Теорема о четырех цветах. Алгоритмы раскраски (точные и приближённые).
Тема 14. Направленные, ориентированные графы
Направленные, ориентированные графы. Полустепени вершин. Способы задания. Операции над направленными графами. Связность, типы связности направленных графов. Достижимость. Матрица достижимости.
Тема 15. Взвешенные графы
Взвешенные графы. Взвешенные направленные графы (сети). Кратчайшее остовное дерево в графе. Деревья Штейнера.
Дата добавления: 2018-04-05; просмотров: 301; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!