Степанов В.Н. Дискретная математика: множества, комбинаторика, алгебраические структуры, графы

Учебное пособие. — Омск: Омский государственный технический университет (ОмГТУ), 2009. — 195 с.Основное назначение данного учебного пособия – методическое обеспечение курса "Дискретная математика". В пособии излагаются основы теории множеств, комбинаторики, алгебраических структур, теории графов. Для студентов инженерных специальностей.Теория множеств.
Множества и основные операции над ними.
Понятие множества и подмножества.
Способы задания множества.
Операции над множествами.
Кортежи.
Прямое произведение множеств.
Отношения.
Бинарные отношения.
Операции над отношениями.
Функции.
Матрицы бинарных отношений.
Специальные типы бинарных отношений.
Рефлексивные, симметричные и транзитивные отношения.
Разбиение. Отношение эквивалентности.
Разбиение множества.
Отношение эквивалентности.
Отношения порядка.
Отношения нестрогого и сторгого порядка.
Экстремальные элементы.
Мощность.
Эквивалентные множества. Мощность множества.
Основные свойства счетных множеств.
Теорема Кантора - Бернштейна.
Двоичные дроби.
Множества мощности континуума.
Теорема Кантора о мощности множества всех своих подмножеств.
О парадоксах в канторовой теории множеств и аксиомах теории множеств.
Аксиомы теории множеств.
Задачи и упражнения.
Комбинаторика.
Основные комбинаторные схемы.
Правило суммы.
Правило произведения.
Формула включения - исключения.
Функция Эйлера.
Выборки.
Размещения с повторениями.
Размещения без повторений.
Перестановки без повторений.
Сочетания без повторений.
Сочетания с повторениями.
Перестановки с повторениями.
Полиноминальная формула и бином Ньютона.
Метод рекуррентных соотношений.
Рекуррентные соотношения.
Числа Фибоначчи.
Процесс последовательных разбиений.
Метод производящих функций.
Производящие функции.
Производящая функция чисел Фибоначчи.
Производящая функция для числа процессов последовательных разбиений.
Задачи и упражнения.
Алгебраические структуры.
Определение и примеры алгебр.
n-арная алгебраическая операция.
Определение алгебры и подалгебры.
Примеры алгебр и подалгебр.
Свойства бинарных алгебраических операций.
Коммутативные, ассоциативные, дистрибутивные алгебраические операции.
Морфизмы.
Гомоморфизмы и изоморфизмы алгебр.
Алгебры с одной бинарной операцией.
Полугруппы и моноиды.
Группы и подгруппы.
Основные свойства группы.
Примеры групп, подгрупп и гомоморфизмов.
Группы самосовмещений многоугольников и многогранников.
Группа подстановок. Теорема Кэли.
Классы смежности. Нормальный делитель.
Алгебры с двумя бинарными операциями.
Определение и примеры колец.
Свойства колец.
Область целостности.
Поля и тела.
Определение и примеры полей.
Свойства полей.
Определение и примеры тел.
Решетки.
Определение решетки.
Булевы алгебры.
Задачи и упражнения.
Теория графов.
Основные понятия теории графов.
Граф и его разновидности.
Морфизмы графов.
Степени вершин.
Маршруты, цепи, циклы, связность.
Операции над графами.
Примеры графов.
Метрические характеристики графов.
Представления графов.
Обходы графов.
Деревья.
Деревья. Свойства деревьев.
Теорема Кэли.
Остовы. Теорема Кирхгофа.
Фундаментальная система циклов. Цикломатическое число.
Остов минимального веса. Алгоритм Краскала и Прима.
Кратчайшие маршруты на графе.
Алгоритм Дейкстры.
Эйлеровы графы.
Теорема Эйлера.
Алгоритм Флёри.
Гамильтоновы графы.
Гамильтоновы маршруты. Задача коммивояжера.
Существование гамильтоновых маршрутов.
Метод ветвей и границ.
Схема метода ветвей и границ.
Оценка снизу длин всех гамильтоновых контуров. Операция приведения матрицы.
Ветвление множества . Оценки снизу подмножеств и общий случай определения оценок снизу.
Выбор дуги ветвления.
Описание алгоритма.
Пример.
Метод Монте–Карло.
Планарные графы.
Укладки графов.
Теорема Эйлера о плоских графах и следствия.
Критерий планарности.
Планарность и двойственность.
Раскрашивание графов.
Хроматическое число графа.
Раскраска карт.
Задачи и упражнения.
Список литературы.
Предметный указатель.