Введение. Учебное пособие для студентов, обучающихся по специальности 230105 – Программное обеспечение вычислительной техники и автоматизированных систем

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

Учебное пособие для студентов,
обучающихся по специальности
230105 – Программное обеспечение вычислительной техники и автоматизированных систем

Абакан

ББК 22.176я73

Д 482

Печатается по рекомендации Методического совета

И по решению Редакционно-издательского совета

Хакасского государственного университета им. Н. Ф. Катанова

Рецензент: Авдеев Л. А., кф-мн, доцент, зав.кафедрой информационной безопасности Хакасского государственного университета им. Н. Ф. Катанова

Д482 Дискретная математика:учебное пособие для студентов, обучающихся по специальности 230105 – Программное обеспечение вычислительной техники и автоматизированных систем / сост. Л. В. Архипова, Е. С. Дернович. – Абакан: Издательство Хакасского государственного университета им. Н.Ф. Катанова, 2007 – 80 с.

ISBN 978-5-7810-04

Пособие предназначено для организации самостоятельной работы студентов. Основное внимание в нем уделяется закреплению базовых понятий теории множеств, теории отношений и теории графов, а также контролю за их усвоением.

ББК

СОДЕРЖАНИЕ

Введение. 4

Часть 1. Элементы теории множеств и отношений. 5

§ 1. Понятие множества. Операции над множествами. 5

§ 2. Декартово произведение двух или нескольких множеств.
Понятие отношения. Бинарные отношения. 10

§ 3. Специальные бинарные отношения. Отношения эквивалент-
ности. 13

§ 4. Отношения порядка. 14

§ 5. Функциональные отношения (отображения). Виды отобра-
жений. 14

Часть 2. Теория графов. 14

§ 1. Основные понятия теории графов. 14

§ 2. Булевы матрицы.. 14

§ 3. Связность графа. Компоненты связности. Матрица связности. 14

§ 4. Полные графы. Двудольные графы. Однородные и реберные
графы.. 14

§ 5. Поиск путей (маршрутов) с минимальным числом дуг (ребер) 14

§ 6. Расстояние в графах. 14

§ 7. Нагруженные графы. Расстояния в нагруженном графе. 14

§ 8. Эйлеровы цепи и циклы в графах. Эйлеровы графы. Гамильто-новы цепи и циклы в графах. Гамильтоновы графы 14

§ 9. Деревья. Остов графа. Цикловой базис графа. 14

§ 10. Раскраска графов. Планарные графы.. 14

Варианты контрольных работ. 14

Тест по теории множеств и отношений. 14

Тест по теории графов. 14

Библиографический список. 14

Введение

Настоящее пособие составлено в соответствии с требованиями, предъявляемыми государственным образовательным стандартом высшего профессионального образования к обязательному минимуму содержания дисциплины «Дискретная математика» по образовательной программе специальности 230105 – Программное обеспечение вычислительной техники и автоматизированных систем.

Пособие состоит из двух частей: «Теория множеств и отношений» и «Теория графов» и структурировано таким образом, что позволяет преподавателю использовать его на занятиях, но и организовать самостоятельную работу студентов по изучению материала. Каждый параграф содержит необходимый теоретический материал, а также задачи и упражнения для усвоения и закрепления полученных знаний. Предлагаемые задачи имеют различную степень сложности. Почти все задачи снабжены ответами. Для самоконтроля в пособии приводится 6 вариантов контрольной работы по каждой части, что дает возможность оценить уровень полученных умений и навыков.

Это пособие может быть полезно также студентам, обучающимся по другим информационным специальностям.

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