Пособие содержит основные разделы дискретной математики- теория множеств, комбинаторика и теория графов. Материал сопровождается изложением основных теоретических сведений. Предлагается большое число разобранных примеров и упражнений, а также задач для самостоятельного решения.
Пособие предназначено для студентов тех направлений, где изучается дискретная математика и ее приложения, и как материал для самообразования. Оно также может оказаться полезным для преподавателей, ведущих соответствующие курсы.
Предисловие
I. ТЕОРИЯ МНОЖЕСТВ
1. Задание множества. Операции над множествами
2. Бинарные отношения
3. Мощность множества
II. КОМБИНАТОРИКА
4. Основные принципы комбинаторики
5. Перестановки, сочетания, размещения
6. Перестановки с повторениями
7. Сочетания с повторениями
8. Формула включений и исключений
9. Бином Ньютона. Полиноминальная теорема
10. Рекуррентные соотношения. Производящие функции
III. ТЕОРИЯ ГРАФОВ
11. Общие понятия. Способы задания графа
12. Связность графа
13. Независимые и доминирующие множества
14. Деревья
15. Эйлеровы и гамильтоновы графы
16. Плоские графы
17. Алгоритмические задачи на графах
Список литературы