Федеральное агентство по образованию Хакасский государственный университет им. Н. Ф. Катанова

ДИСКРЕТНАЯ МАТЕМАТИКА

Учебное пособие для студентов, обучающихся по специальности 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.

Для графического изображения множеств и их свойств, а также отношений между ними используются так называемые диаграммы Эйлера-Венна. Множество изображается кругом (или другой связной фигурой) на плоскости и мыслится как множество точек круга (фигуры).