- •Русаков Алексей Михайлович
- •Лекции по дисциплине «Дискретная математика»
- •Введение.
- •Теория множеств.
- •Понятие множества. Операции над множествами.
- •Определение.
- •Определение.
- •Определение.
- •Пример.
- •Свойства операций сложения и пересечения множеств.
- •Определение.
- •Замечание.
- •Примеры.
- •Счётные множества. Теорема Кантора.
- •Определение.
- •Примеры счётных множеств.
- •Замечания.
- •Теорема.
- •Доказательство:
- •Задачи для самостоятельного решения.
- •Решите задачи № 1.30 1.39 с использованием диаграммы Эйлера-Венна.
- •Бинарные отношения в теории графов.
- •Например:
- •Матрицы смежности и инцидентности.
- •Пример.
- •Маршруты, цепи и простые цепи.
- •Определение
- •Расстояние и протяжённость в графе.
- •Деревья.
- •Примеры:
- •Например:
- •Помеченные графы. Перечисление помеченных деревьев.
- •Пример:
- •Теорема Келли.
- •Задача о кратчайшем соединении.
- •Задача о кратчайших путях.
- •Эйлеровы цепи, критерий Эйлеровости. Задача о Кёнигсбергских мостах.
- •Доказательство:
- •Достаточность.
- •Индуктивный переход.
- •Гамильтовы циклы.
- •Пример:
- •Примеры задач и упражнений.
- •Решение.
- •Задачи для самостоятельного решения.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение группы.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение и способы описания формальных грамматик.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Теория автоматов.
- •Основные понятия теории автоматов.
- •Определение.
- •Способы задания автоматов. Таблица переходов.
- •Определение.
- •Определение.
- •Способы задания автоматов. Граф автомата.
- •Определение.
- •Способы задания автоматов. Матрица переходов и выходов. Определение.
- •Машины Тьюринга и конечные автоматы. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Машины Тьюринга с двумя выходами.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Автоматы с магазинной памятью и бесконтекстные языки.
- •Определение.
- •Определение.
- •Модель дискретного преобразователя Глушкова в. М. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Понятие об абстрактном автомате и индуцируемом им отображении. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Определение.
- •Автоматные отображения и события. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Теорема.
- •Регулярные языки и конечные автоматы. Определение.
- •Определение.
- •Определение.
- •Определение.
- •Правила подчинения мест в регулярных выражениях.
- •Определение.
- •Определение.
- •Правила построения основного алгоритма синтеза конечных автоматов.
- •Пример.
- •Автомат Мили.
- •Определение.
- •Определение.
- •Автомат Мура.
- •Определение.
- •Определение.
- •Теория булевых функций.
- •Связь булевых функций и схем из функциональных элементов и контактных схем. Определение.
- •Замечания.
- •Теорема.
- •Доказательство:
- •Замечание.
- •Теорема. (Формулы разложения Клода Шеннона.)
- •Доказательство:
- •Замечания.
- •Основные свойства булевых функций. Замечание.
- •Определение.
- •Примеры задач и упражнений. Пример 1
- •Доказательство
- •Задачи для самостоятельного решения.
- •Элементы комбинаторики.
- •Основные понятия комбинаторики. Определение.
- •Определение.
- •Доказательство.
- •Теорема – правило включения-исключения.
- •Доказательство.
- •Доказательство.
- •8.2. Формулировка задания.
- •Определение.
- •Пример.
- •Переходы можно представить также с помощью таблицы и схематически:
- •Определение.
- •Последовательность выполнения.
- •Методический пример.
- •Контрольная распечатка.
- •Замечания.
- •Отчет по практической работе.
- •Контрольные вопросы
- •Варианты заданий.
- •Домашняя работа №1. По всей теории
- •Домашняя работа №2. Способы задания графов
- •8.03.2. Правила регулярного выражения.
- •Установка необходимого программного обеспечения.
- •Замечания.
- •Методический пример.
- •Контрольная распечатка.
- •Отчет по практической работе.
- •Контрольные вопросы.
- •Варианты заданий.
- •Дополнительные материалы.
- •Биография Георга Кантора (основатель теории множеств).
- •Город Калининград (Кёнигсберг).
- •Список литературы.
Задача о кратчайших путях.
Пусть дан граф с неотрицательными весами на дугах. Нас будут интересовать две задачи:
-
Какова длина кратчайшего пути, ведущего из одной выделенной вершины к другой? Каков этот путь?
-
Каковы длины кратчайших путей от выделенной вершины до всех остальных вершин графа? Каковы эти пути?
Задачи 1) и 2) очень похожи, и решение задачи 1) получается в результате прерывания в нужном месте решения задачи 2).
Решение поставленных задач даёт алгоритм Дейкстры – один из первых известных динамических алгоритмов.
-
Эйлеровы цепи, критерий Эйлеровости. Задача о Кёнигсбергских мостах.
Семь мостов города Кёнигсберг расположены на реке Преголи так, как изображено на рисунке, соединяя его части A,B,C,D.
Задача состоит в следующем: «Найти такую точку города, выйдя из которой можно пройти по всем мостам по одному разу и вернуться в неё обратно».
Эйлер показал, что эта задача не имеет решения.
Определение.
Связный граф называется эйлеровым, если в нём существует простой цикл, проходящий через все дуги графа (простой, проходящий через все дуги, то есть проходящий по одному разу через каждую дугу.)
Лемма:
Если степень каждой вершины конечного графа чётна, то на графе существует, хотя бы один простой цикл.
Доказательство:
Наличие хотя бы одной петли делает лемму тривиальной. Осталось рассмотреть графы без петель. Возьмём произвольную вершину графа. Так как её степень чётна, то существует по крайней мере две дуги, для которых она является граничной. Выйдем по одной из этих дуг из этой вершины (не обязательно по её ориентации). Вершина, в которую мы придём, так же имеет чётную степень, и значит, кроме дуги, по которой мы пришли есть ещё хотя бы одна, по которой можно из этой вершины уйти. Уничтожим после прохождения через вершину дуги прихода и ухода. При этом степень пройденной вершины уменьшилась на 2, а значит осталась чётной. Таким образом, мы показали, что условие чётности степеней вершин – это условие «незастревания» в них, и оно наследуется при уничтожении пройденных дуг. Двигаясь таким образом по конечному графу, не застревая в его вершинах, мы можем всё время оказываться в вершинах, в которых мы не побывали ранее (так как в конечном графе конечное число вершин). Тогда на каком-то из шагов такого «путешествия» мы окажемся в вершине графа, в которой уже были до этого. Отрезок простой цепи, заключённый между первым и втором прохождением через такую вершину, являются простым циклом на исходном графе.
Теорема (критерий Эйлеровости графа).
Для того, чтобы конечный связный граф был эйлеровым, необходимо и достаточно, чтобы степени всех его вершин были чётными числами.
Необходимость очевидна, так как, двигаясь по эйлеровому циклу, войдя в вершину по одной дуге, мы выходим из неё по другой дуге, т.е. каждой «дуге выхода» соответствует «дуга входа». Каждая пара дуг даёт вклад, равный двум, в степень вершины, а поскольку эйлеров цикл содержит все дуги, то степень каждой вершины представлена суммой двоек, и значит чётна.
Достаточность.
Достаточность будем доказывать по индукции, взяв в качестве параметра индукции числа дуг графа.
Шаг 1. . Единственный граф, удовлетворяющий условиям теоремы изображён на рисунке.
Очевидно, его единственная дуга и образует эйлеров цикл.