Дискретная математика – это цикл математических наук, изучающих свойства конечных множеств. <...> Пособие предназначено для ознакомления студентов с основными понятиями разделов дискретной математики, объединенных в рамках дисциплины «Теория графов и математическая логика»: теория множеств, комплектов и нечетких множеств, отношений и функций, теория графов. <...> Согласно ФГОС ВПО в результате освоения дисциплины студент должен знать: основные принципы перечисления объектов; основные характеристики графов; специальные цепи и циклы в графе; понятие остовного дерева 5 в графе; основные понятия теории множеств (операции над множествами, законы теории множеств); уметь: строить граф по его матрицам смежности и инциденций и решать обратную задачу; строить циклы специального вида в графе; применять математический аппарат при решении типовых задач, а также обнаруживать применимость аппарата теории графов для решения задач из родственных областей науки и ее приложений; владеть: аппаратом и методами теории графов для грамотной математической постановки и анализа конкретных задач, возникающих в профессиональной деятельности; способностью и готовностью к изучению дальнейших понятий и теорий, разработанных в современной математике, а также к оценке степени адекватности предлагаемого аппарата к решению прикладных задач. <...> Понятие множества Основателем теории множеств является немецкий математик Георг Кантор (1845 – 1918 гг.) <...> . Его понятие множества звучало примерно так: «Множество – это объединение в одно целое объектов, хорошо различимых нашей интуицией или мыслью». <...> Множество, содержащее все несамопринадлежащие множества, выделяет из множества всех множеств (самопринадлежащего) не только все несамопринадлежащие объекты, но и ещѐ само себя (самопринадлежащее), а так7 же все свои внутренние множества (также самопринадлежащие), так что убывающий ряд внутренностей не обрывается. <...> XX в. было направлено на то <...>
Множества._Отношения._Графы_.pdf
УДК 517(07)
Рецензенты: кафедра прикладной математики и информационных технологий
ФГОБУ ВПО «Липецкий государственный педагогический университет»;
Скуратов
А.П. – канд. техн. наук, доцент Липецкого филиала НОУ
ВПО «Международный институт компьютерных технологий».
Т 484 Ткаченко, С.В. Множества. Отношения. Графы. [Текст]: учеб. пособие /
С.В. Ткаченко, А.С. Сысоев – Липецк: Изд-во ЛГТУ, 2012. – 112 с.
ISBN
Пособие является одной из частей системы учебных пособий по дискретной
математике. Рассматриваются основные разделы дисциплины «Теория
графов и математическая логика», в частности теория множеств, комплектов и
нечетких множеств, теория функций и отношений, и теория графов.
Все темы содержат достаточное количество примеров и задач с решениями.
Приведены варианты индивидуальных домашних заданий, контрольных
работ, тесты для текущего контроля знаний.
Данное пособие может быть рекомендовано студентам направлений
231300.62 «Прикладная математика», 221400.62 «Управление качеством»,
221700.62 «Стандартизация и метрология», а также преподавателям, которые
преподают теорию множеств, отношений и графов студентам всех направлений.
ISBN
©
Липецкий государственный
технический университет, 2012
© Ткаченко С.В., Сысоев А.С., 2012
Стр.4
СОДЕРЖАНИЕ
ВВЕДЕНИЕ .................................................................................................................. 5
ТЕМА 1. МНОЖЕСТВА И ИХ СПЕЦИФИКАЦИИ ............................................... 7
1.1. Множества ......................................................................................................... 7
1.1.1. Понятие множества ................................................................................... 7
1.1.2. Операции над множествами ................................................................... 11
1.1.3. Законы теории множеств ........................................................................ 14
1.2. Комплекты ....................................................................................................... 15
1.2.1. Понятие комплекта .................................................................................. 15
1.2.2. Операции над комплектами ................................................................... 16
1.3. Нечеткие множества ....................................................................................... 18
1.3.1. Понятие нечеткого множества ............................................................... 18
1.3.2. Операции над нечеткими множествами ............................................... 20
ТЕМА 2. ОТНОШЕНИЯ И ФУНКЦИИ ................................................................. 22
2.1. Отношения ...................................................................................................... 22
2.2. Функции и отображения ................................................................................ 25
2.3. Специальные бинарные отношения ............................................................. 29
ТЕМА 3. ТЕОРИЯ ГРАФОВ .................................................................................... 32
3.1. Определение графа ......................................................................................... 32
3.2. Основные характеристики графа и его элементов ...................................... 36
3.3. Матричное представление графов. Степени вершин ................................. 37
3.4. Элементы графов: подграфы, маршруты, цепи, циклы .............................. 41
3.5. Связные графы. Компоненты связности ...................................................... 45
3.5.1. Понятие связности .................................................................................. 45
3.5.2. Вершинная и реберная связность .......................................................... 49
3.5.3. Двусвязные графы ................................................................................... 51
3.5.4. Связность в орграфах .............................................................................. 53
3.5.5. Метрические характеристики графа ..................................................... 55
3
Стр.5
3.6. Виды графов и операции над графами ......................................................... 56
3.6.1. Виды графов ............................................................................................. 56
3.6.2. Операции над графами ........................................................................... 60
ИНДИВИДУАЛЬНОЕ ДОМАШНИЕ ЗАДАНИЕ (ВАРИАНТЫ) ....................... 64
ИДЗ 1. Проверка законов теории множеств, комплектов, нечетких множеств ... 64
ИДЗ 2. Отношения и функции ............................................................................. 65
ИДЗ 3. Основные понятия теории графов .......................................................... 67
ИДЗ 4. Связность в орграфах ............................................................................... 75
ИДЗ 5. Связность в неориентированных графах................................................ 75
ИНДИВИДУАЛЬНОЕ ДОМАШНЕЕ ЗАДАНИЕ (ПРИМЕР ВЫПОЛНЕНИЯ) .... 76
Пример выполнения ИДЗ 1 .................................................................................. 76
Пример выполнения ИДЗ 2 .................................................................................. 84
Пример выполнения ИДЗ 3 .................................................................................. 91
Пример выполнения ИДЗ 4 .................................................................................. 95
Пример выполнения ИДЗ 5 .................................................................................. 97
ПРОМЕЖУТОЧНЫЙ КОНТРОЛЬ ЗНАНИЙ ...................................................... 101
Тестовые задания для защиты ИДЗ ................................................................... 101
Тест 1 ................................................................................................................ 101
Тест 2 ................................................................................................................ 101
Тест 3 ................................................................................................................ 102
Тест 4 ................................................................................................................ 103
Тест 5 ................................................................................................................ 104
Примеры контрольных работ ............................................................................. 106
Контрольная работа № 1 ................................................................................. 106
Контрольная работа № 2 ................................................................................. 107
КОНТРОЛЬНЫЕ ВОПРОСЫ ................................................................................ 109
БИБЛИОГРАФИЧЕСКИЙ СПИСОК .................................................................... 110
4
Стр.6