- •Введение
- •Предисловие
- •1. Теория множеств
- •1.1. Понятие множества
- •1.2. Операции над множествами
- •1.3. Основные тождества алгебры множеств
- •1.4. Кортежи и декартово произведение множеств
- •1.5. Бинарные отношения. Свойства отношений
- •1.6. Соответствия. Отображения. Функции
- •Вопросы для самопроверки
- •2. Элементы комбинаторики
- •Вопросы для самопроверки
- •3. Логические операции
- •3.1. Основные понятия
- •3.2. Простейшие связки (операции)
- •3.3. Другие связки (операции)
- •3.4. Основные законы, определяющие свойства введенных логических операций.
- •4. Булевы функции
- •4.1. Основные понятия
- •4.2. Свойства элементарных булевых функций
- •4.3. Дизъюнктивные и конъюнктивные нормальные формы алгебры высказываний
- •4.4. Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы
- •Задачи по теме «Булевы функции.»
- •Вопросы для самопроверки
- •5. Теория графов
- •5.1. Ориентированные графы
- •5.2. Неориентированные графы
- •5.3. Матричное задание ориентированных графов
- •5.4. Матричное задание неориентированных графов
- •5.5. Изоморфизм графов
- •5.6. Операции над графами
- •5.7. Пути, контуры, маршруты, цепи, циклы
- •5.8. Расстояние в графах
- •5.9. Связность в неориентированных графах
- •5.10. Связность в ориентированных графах
- •5.11. Эйлеровы графы
- •5.12. Гамильтоновы графы
- •5.13. Деревья
- •5.14. Остовные деревья
- •5.15 Взвешенные графы. Экстремальные остовы графов
- •5.16 Поиск кратчайшего пути между вершинами. Алгоритм Дейкстры
- •5.17 Раскраска графов. Раскраска вершин графа
- •Вопросы для самопроверки
- •Библиографический список
- •Оглавление
- •Подписано к изданию «8» октября 2014.
- •394026 Воронеж, Московский просп., 14
Библиографический список
1. Кристофидес, Н. Теория графов. Алгоритмический подход / Н. Кристофидес. - М.: Мир, 1978. - 432 с.
2. Оре, О. Теория графов / О. Оре. - М.: Наука, 1980. – 336с.
3. Харари, Ф. Теория графов / Ф. Харари. - М.: Едиториал УРСС, 2007. - 300 с.
4. Новиков, Ф.А. Дискретная математика для программистов / Ф. А. Новиков. – СПб.: Питер, 2007. - 363 с.
5. Емеличев, В.А. Лекции по теории графов /В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич. – М.: Наука, 1990. – 382 с.
6. Судоплатов С.В. Элементы дискретной математики: учебник / С.В. Судоплатов, Е.В. Овчинникова. М.: ИНФРА-М, 2002. – 280 с.
Оглавление
Введение…………………………………………………… Предисловие………………………………………………. |
3 4 |
||
1. |
Теория множеств……………………………………. |
4 |
|
|
1.1.. |
Понятие множества……………………………. |
4 |
|
1.2. |
Операции над множествами …………………. |
7 |
|
1.3. |
Основные тождества алгебры множеств……... |
10 |
|
1.4. |
Кортежи и декартово произведение множеств |
12 |
|
1.5. 1.6. |
Бинарные отношения. Свойства отношений… Соответствия. Отображения. Функции………. |
14 17 |
|
|
Вопросы для самопроверки………………….. Задачи по теме «Операции над множествами» |
20 21 |
2. |
Элементы комбинаторики…………………………. |
23 |
|
|
|
Вопросы для самопроверки………………….. Задачи по теме «Комбинаторные формулы. Бином Ньютона»………………………………. |
28
29 |
3. |
Логические операции………………………………. |
33 |
|
|
3.1. |
Основные понятия…………………………….. |
33 |
|
3.2. |
Простейшие связки (операции)……………… |
34 |
|
3.3. |
Другие связки (операции)……………………. |
38 |
|
3.4. |
Основные законы, определяющие свойства введенных логических операций…………….. |
40 |
|
|
Задачи по теме “Логические операции»…….. |
43 |
4. |
Булевы функции……………………………………. |
50 |
|
|
4.1. |
Основные понятия…………………………….. |
50 |
|
4.2. |
Свойства элементарных булевых функций….. |
52 |
|
4.3. |
Дизъюнктивные и конъюнктивные нормальные формы алгебры высказываний…. |
53 |
|
4.4. |
Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы…………. |
55 |
|
Задачи по теме «Булевы функции»………….. Вопросы для самопроверки…………………... |
57 63 |
|
5. |
Теория графов………………………………………… |
64 |
|
|
5.1. |
Ориентированные графы……………………… |
64 |
|
5.2. |
Неориентированные графы…………………… |
66 |
|
5.3. |
Матричное задание ориентированных графов. |
69 |
|
5.4. |
Матричное задание неориентированных графов…………………………………………... |
71 |
|
5.5. |
Изоморфизм графов…………………………… |
72 |
|
5.6. |
Операции над графами………………………… |
74 |
|
5.7. |
Пути, контуры, маршруты, цепи, циклы…….. |
77 |
|
5.8. |
Расстояние в графах…………………………… |
79 |
|
5.9. |
Связность в неориентированных графах…….. |
81 |
|
5.10. |
Связность в ориентированных графах……….. |
82 |
|
5.11. |
Эйлеровы графы……………………………….. |
86 |
|
5.12. |
Гамильтоновы графы………………………….. |
89 |
|
5.13. |
Деревья………………………………………… |
93 |
|
5.14. |
Остовные деревья |
96 |
|
5.15. |
Взвешенные графы. Экстремальные остовы графов…………………………………………... |
98 |
|
5.16. |
Поиск кратчайшего пути между вершинами. Алгоритм Дейкстры…………………………… |
101 |
|
5.17. |
Раскраска графов. Раскраска вершин графа…. |
103 |
|
|
Вопросы для самопроверки ………………….. Задачи по теме «Теория графов»…………….. |
110 111 |
Библиографический список……………………………. |
115 |
||
Учебное издание
Горбунов Валерий Викторович
Лапшина Марина Леонидовна
ДИСКРЕТНАЯ МАТЕМАТИКА
В авторской редакции
Компьютерный набор В.В. Горбунова