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