СОДЕРЖАНИЕ

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

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

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

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

Д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