- •Содержание
- •Введение
- •Часть 1. Элементы теории множеств и отношений § 1. Понятие множества. Операции над множествами
- •Примеры
- •Операции над множествами
- •Основные тождества алгебры множеств
- •Упражнения
- •§ 2. Декартово произведение двух или нескольких множеств. Понятие отношения. Бинарные отношения
- •Упражнения
- •§ 3. Специальные бинарные отношения. Отношения эквивалентности
- •Упражнения
- •§ 4. Отношения порядка
- •Упражнения
- •§ 5. Функциональные отношения (отображения). Виды отображений
- •Виды отображений:
- •Упражнения
- •Часть 2. Теория графов
- •§ 1. Основные понятия теории графов
- •Способы задания графов. Матричное задание графов.
- •Свойства матриц смежности и инцидентности
- •Упражнения
- •§ Б 2. Булевы матрицы
- •Дизъюнкция (конъюкция)
- •§ 3. Связность графа. Компоненты связности. Матрица связности
- •Выделение компонент связности
- •Алгоритм выделения компонент сильной связности
- •Упражнения
- •§ 4. Полные графы. Двудольные графы. Однородные и реберные графы
- •Упражнения
- •§ 5. Поиск путей (маршрутов) с минимальным числом дуг (ребер)
- •Упражнения
- •§ 6. Расстояние в графах
- •Упражнения
- •§ 7. Нагруженные графы. Расстояния в нагруженном графе
- •Нахождение минимального пути в нагруженном орграфе
- •Алгоритм Форда-Беллмана нахождения минимального пути в нагруженном орграфе из v1 в vi1 (i1≠1)
- •Упражнения
- •§ 8. Эйлеровы цепи и циклы в графах. Эйлеровы графы. Гамильтоновы цепи и циклы в графах. Гамильтоновы графы
- •Упражнения
- •§ 9. Деревья. Остов графа. Цикловой базис графа
- •Алгоритм нахождения кратчайшего остова в нагруженном графе
- •Упражнения
- •§ 10. Раскраска графов. Планарные графы Раскраска вершин графа
- •Одноцветные классы образуют независимые множества вершин.
- •Существуют и приближенные алгоритмы раскрашивания:
- •Упражнения
- •Варианты контрольных работ Часть 1. Элементы теории множеств и отношений Вариант № 1.
- •Вариант № 2.
- •Вариант № 3.
- •Вариант № 4.
- •Вариант № 5.
- •Вариант № 6.
- •Часть 2. Теория графов Вариант № 1.
- •Вариант № 2.
- •Вариант № 3.
- •Вариант № 4.
- •Вариант № 5.
- •Вариант № 6.
- •Ответы Часть 1
- •Часть 2
- •Тест по теории множеств и отношений
- •Тест по теории графов
- •Библиографический список
- •Любовь Васильевна Архипова Елена Сергеевна Дернович
- •Дискретная математика
Федеральное агентство по образованию Хакасский государственный университет им. Н. Ф. Катанова
ДИСКРЕТНАЯ МАТЕМАТИКА
Учебное пособие для студентов, обучающихся по специальности 230105 – Программное обеспечение вычислительной техники и автоматизированных систем
Абакан
2007
ББК 22.176я73
Д 482
Печатается по рекомендации Методического совета
и по решению Редакционно-издательского совета
Хакасского государственного университета им. Н. Ф. Катанова
Рецензент: Авдеев Л. А., кф-мн, доцент, зав.кафедрой информационной безопасности Хакасского государственного университета им. Н. Ф. Катанова
Д 482 Дискретная математика: учебное пособие для студентов, обучающихся по специальности 230105 – Программное обеспечение вычислительной техники и автоматизированных систем / сост. Л. В. Архипова, Е. С. Дернович. – Абакан: Издательство Хакасского государственного университета им. Н.Ф. Катанова, 2007 – 80 с.
ISBN 978-5-7810-04
Пособие предназначено для организации самостоятельной работы студентов. Основное внимание в нем уделяется закреплению базовых понятий теории множеств, теории отношений и теории графов, а также контролю за их усвоением.
ББК
ISBN 978-5-7810-04 |
© Хакасский государственный университет им. Н.Ф. Катанова, 2007 |
Содержание
Введение 4
Часть 1. Элементы теории множеств и отношений 5
§ 1. Понятие множества. Операции над множествами 5
§ 2. Декартово произведение двух или нескольких множеств. Понятие отношения. Бинарные отношения 11
§ 3. Специальные бинарные отношения. Отношения эквивалентности 14
§ 4. Отношения порядка 16
§ 5. Функциональные отношения (отображения). Виды отображений 18
Часть 2. Теория графов 21
§ 1. Основные понятия теории графов 21
§ 2. Булевы матрицы 29
§ 3. Связность графа. Компоненты связности. Матрица связности 31
§ 4. Полные графы. Двудольные графы. Однородные и реберные графы 34
§ 5. Поиск путей (маршрутов) с минимальным числом дуг (ребер) 38
§ 6. Расстояние в графах 40
§ 7. Нагруженные графы. Расстояния в нагруженном графе 42
§ 8. Эйлеровы цепи и циклы в графах. Эйлеровы графы. Гамильтоновы цепи и циклы в графах. Гамильтоновы графы 46
§ 9. Деревья. Остов графа. Цикловой базис графа 51
§ 10. Раскраска графов. Планарные графы 58
варианты контрольных работ 64
тест по теории множеств и отношений 79
тест по теории графов 80
Библиографический список 83
Введение
Настоящее пособие составлено в соответствии с требованиями, предъявляемыми государственным образовательным стандартом высшего профессионального образования к обязательному минимуму содержания дисциплины «Дискретная математика» по образовательной программе специальности 230105 – Программное обеспечение вычислительной техники и автоматизированных систем.
Пособие состоит из двух частей: «Теория множеств и отношений» и «Теория графов» и структурировано таким образом, что позволяет преподавателю использовать его на занятиях, но и организовать самостоятельную работу студентов по изучению материала. Каждый параграф содержит необходимый теоретический материал, а также задачи и упражнения для усвоения и закрепления полученных знаний. Предлагаемые задачи имеют различную степень сложности. Почти все задачи снабжены ответами. Для самоконтроля в пособии приводится 6 вариантов контрольной работы по каждой части, что дает возможность оценить уровень полученных умений и навыков.
Это пособие может быть полезно также студентам, обучающимся по другим информационным специальностям.
В пособии приводится библиографический список, который содержит учебную литературу и сборники задач, необходимые студентам для самостоятельной работы.
Часть 1. Элементы теории множеств и отношений § 1. Понятие множества. Операции над множествами
Под множеством будем понимать совокупность определённых и различимых между собой объектов, которая рассматривается как единое целое. Эти объекты называются элементами множества.
Понятие множества принимается как исходное, первичное, т.е. не сводимое к другим понятиям. Множества будем обозначать большими буквами латинского алфавита: A, B, C… , а элементы множества – малыми буквами: a, b, c… .
Определение: Множество, не содержащее ни одного элемента, называется пустым множеством. Обозначается символом .
Определение: Некоторое фиксированное множество, которое содержит все рассмотренные в данной теории множества, называется универсальным и обозначается U.
Определение: Два множества A и B называются равными и обозначаются A=B, если A и B содержат одни и те же элементы, т.е. если каждый элемент множества A является элементом множества B, и каждый элемент множества B является элементом множества A.
Определение: Множество A называется подмножеством множества B, если каждый элемент множества A принадлежит множеству B. В этом случае пишут . Символ называется знаком включения. Если и , то говорят, что A есть собственное подмножество множества B. В этом случае пишут .
Множество всех подмножеств множества A называется множеством-степенью и обозначается P(A).
Для доказательства равенства двух множеств A и B достаточно доказать, что и , т.е. доказательство равенства двух множеств состоит из доказательства двух утверждений:
1.
2.
Для графического изображения множеств и их свойств, а также отношений между ними используются так называемые диаграммы Эйлера-Венна. Множество изображается кругом (или другой связной фигурой) на плоскости и мыслится как множество точек круга (фигуры).