Материал: Ответы на экзаменационные вопросы по дискретной математике

Экзаменационные вопросы © Kovalenko Leonid

По дискретной математике

Весь материал взят с книг и научных работ. Ничего не придумано☺

0. Введение. Граф 2

1. Сеть. Потоки в сети. Теорема Форда — Фалкерсона 12

2. Функция. Бинарное отношение. Тотальность, сюръективность, инъективность, биективность. Примеры 16

3. Бинарное отношение. Свойства. Матрица смежности и граф отношения. Отношение эквивалентности. Примеры 25

4. Алгебраическая структура. Полугруппа, моноид, группа. Примеры 30

5. Группа. Абелева группа. Аддитивная группа. Мультипликативная группа. Конечная группа. Таблица Кэли. Циклическая группа. Декартово произведение групп 37

6. Группа подстановок. Симметрическая группа . Умножение подстановок. Нейтральный элемент. Обратная подстановка. Число элементов группы 41

7. Цикл. Теорема о представлении подстановки в виде произведения независимых циклов. Транспозиция. Чётные и нечётные подстановки. Знакопеременная группа 43

8. Кольцо. Свойства. Коммутативное кольцо. Делители 0. Область целостности. Примеры. Подкольцо. Единица кольца. Поле. Примеры 46

9. Идеал. Главный идеал. Теорема об идеалах поля (только и ). Следствие об идеалах в кольце 50

10. Сравнения. Классы вычетов по модулю (по идеалу ). Свойства. Малая теорема Ферма. Функция Эйлера. Теорема Эйлера (теория чисел) 51

11. Характеристика кольца. Теорема о характеристике кольца без делителей 0. Примеры. Кольцо классов вычетов. Примеры 56

12. Простой идеал. Необходимое и достаточное условие того, что идеал кольца — простой 56

13. Поле классов вычетов. Минимальное поле. Примеры 57

14. Евклидово кольцо. Свойства (8 свойств). Примеры 57

15. Кольцо многочленов . Условия того, что кольцо — евклидово кольцо 60

16. Приводимые и неприводимые многочлены в кольце . Примеры. Теорема о разложении в на произведение неприводимых множителей. Теорема Безу 61

17. Расширение поля (надполе). Теорема о том, что кольцо классов вычетов по модулю неприводимого многочлена есть поле. Степень расширения. Число элементов этого поля 62

18. Поле Галуа. Примеры полей Галуа как расширения полей. Таблицы сложения и умножения 63

Литература 68

0. Введение. Граф

Граф (в широком смысле) — конечный набор объектов любой природы, которые называются вершинами, некоторые пары из которых могут быть соединены.

Граф — множество вершин и набор неупорядоченных и упорядоченных пар вершин, где — , — . Обозначается . Неупорядоченная пара вершин называется ребром, упорядоченная пара — дугой.

Смежные (соседние) вершины — две вершины, которые соединены ребром.

Смежные (соседние) рёбра (дуги) — два ребра (две дуги), у которых есть общая вершина.

Кратные рёбра (дуги) — рёбра (дуги), соединяющие одну и ту же пару вершин.

Петля — ребро, которое начинается и кончается в одной и той же вершине.

Инцидентность — понятие, используемое только в отношении ребра (дуги) и вершины: если — вершины, а — соединяющее их ребро (дуга), тогда вершина и ребро инцидентны, вершина и ребро тоже инцидентны. Две вершины или два ребра (дуги) инцидентными быть не могут. Понятие инцидентности для орграфов сохраняется (то есть начальная или конечная вершина — не имеет значение), но различается в особых случаях — положительная инцидентность (дуга исходит из вершины) и отрицательная инцидентность (дуга заходит в вершину).

Изоморфизм двух графов — понятие, используемое в случае, если существует перестановка вершин, при которой два графа совпадают. Иначе говоря, два графа называются изоморфными, если существует взаимно-однозначное соответствие между их вершинами и рёбрами, которое сохраняет смежность и инцидентность (то есть графы отличаются только названиями своих вершин). В случае матрицы смежности: графы являются изоморфными, если путём перестановки строк и столбцов матрицы смежности первого графа удаётся получить матрицу смежности второго графа.

Рисунок 1. Все три графа — изоморфны

Порядок графа — число вершин в графе: .

Размер графа — число рёбер (дуг) в графе: .

Степень вершины — количество инцидентных ей рёбер (при этом петли считают дважды).

Изолированная вершина — вершина, которая не является концом ни одного ребра.

Висячая вершина (или лист) — вершина, которая является концом ровно одного ребра.

Путь — конечная последовательность вершин, в которой каждая вершина (кроме последней) соединена со следующей в последовательности вершиной ребром или дугой. Длина пути — число составляющих его рёбер и дуг.

Простой путь — путь, в котором рёбра (дуги) не повторяются.

Элементарный путь — простой путь, в котором вершины не повторяются.

Цикл — путь, в котором первая и последняя вершины совпадают. Длина цикла — число составляющих его рёбер и дуг.

Простой цикл (или контур) — цикл, в котором только первая и последняя вершины совпадают, а все остальные — нет.

Цепь (или маршрут) — путь без повторяющихся рёбер.

Простая цепь (или простой маршрут) — цепь без повторяющихся вершин.

Расстояние между вершинами — минимальная длина пути, который соединяет эти вершины.

Связность означает наличие пути между любой парой вершин.

Бинарное отношение на множестве вершин графа, заданное как «существует путь из в », является отношением эквивалентности и, следовательно, разбивает это множество на классы эквивалентности, называемые компонентами связности графа. Если у графа ровно одна компонента связности, то граф связный.

Компонента связности графа — всякий максимальный связный подграф не орграфа. Слово «максимальный» означает максимальный относительно включения, то есть не содержащийся в связном подграфе с большим числом элементов.

Рисунок 2. Граф с тремя компонентами связности

Мост (перешеек) — ребро графа, удаление которого увеличивает число компонент связности. (На рисунке выше все рёбра — мосты.)

Гамильтонов маршрут — простой маршрут в графе, содержащий все вершины графа ровно по одному разу.

Гамильтонов цикл — простой цикл в графе, содержащий все вершины графа ровно по одному разу (кроме первой, естественно).

На следующем рисунке последовательности вершин: — маршрут, и — простые пути, — цикл (но не контур), — простой цикл (контур).

Рисунок 3

Виды графов

Пустой граф — граф, в котором есть только вершины (нет рёбер и дуг).

Неориентированный граф (не орграф) — граф, содержащий только рёбра.

Ориентированный граф (орграф) — граф, содержащий только дуги.

Смешанный граф — граф, содержащий рёбра и дуги.

Ориентированный и неориентированный графы являются частными случаями смешанного.

Гамильтонов граф — граф, в котором есть гамильтонов цикл. (Далее подробнее.)

Полугамильтонов граф — граф, в котором есть гамильтонов маршрут (Далее подробнее.)

Эйлеров граф — граф, в котором существует цикл без повторения рёбер (такой цикл называют эйлеровым), обходящий все вершины графа. (Далее подробнее.)

Полуэйлеров граф — граф, в котором существует маршрут (эйлеров путь), обходящий все рёбра графа ровно один раз. (Далее подробнее.)

Существуют загадки типа «можно ли нарисовать данную фигуру, не отрывая ручку от бумаги», что и соответствует эйлерову или полуэйлерову графу.

Рисунок 4. а) — эйлеров граф, б) — полуэйлеров граф, в) — граф, не являющийся ни эйлеровым, ни полуэйлеровым.

Связный граф — граф, в котором для любых двух вершин есть путь из в .

Сильно связный (ориентированно связный) граф — ориентированный граф, в котором из одной любой вершины в любую другую имеется ориентированный путь.

Ациклический граф — граф без циклов.

Нормированный граф — ориентированный граф без циклов.

Простой граф — граф без петель и кратных рёбер (дуг).

Мультиграф — граф с кратными рёбрами и без петель.

Псевдограф — мультиграф с хотя бы одной петлёй.

Полный граф — граф, в котором любые две вершины соединены одним ребром.

Турнир — ориентированный граф, в котором каждая пара вершин соединена одной дугой.

Рисунок 5. Турнир

Направленный граф — ориентированный граф, в котором две вершины соединяются не более чем одной дугой.

Дерево — связный граф без циклов.

Лес — множество деревьев.

Двудольный граф — граф, в котором все вершины можно разбить на два непересекающихся подмножества и так, что всякое ребро соединяет вершину из с вершиной из .

Полный двудольный граф — двудольный граф, в котором каждая вершина одного подмножества соединена ребром с каждой вершиной другого подмножества.

-дольный граф — граф, в котором все вершины можно разбить на непересекающихся подмножеств так, что не будет рёбер, соединяющих вершины одного и того же подмножества.

Планарный граф — граф, который можно изобразить диаграммой на плоскости без пересечений рёбер.

Взвешенный граф — граф, в котором каждому ребру поставлено в соответствие некоторое число, называемое весом ребра.

-регулярный граф — граф, в котором степени всех вершин равны .

ВНИМАНИЕ! К сожалению, некоторые из этих терминов не вполне устоялись, так как нет чётких стандартов. В большинстве случаев терминология определяется во вводной части большинства книг по теории графов.

Например, некоторые авторы разрешают мультиграфам иметь петли, а некоторые не разрешают; определения пути и маршрута разнятся…

Основная информация

Лемма 1. Если степени всех вершин в графе больше или равны двум, то граф обязательно содержит контур.

Доказательство. Действительно, выйдя из некоторой вершины и войдя в другую, всегда можно выйти из неё по другому ребру, так как степень каждой вершины больше или равна двум. Выйти из вершины по новому ребру невозможно только в том случае, если эта вершина уже встречалась, а это означает, что можно выделить контур из вершин этого графа.

Теорема (Эйлер). Для того, чтобы данный связный неориентированный граф (возможно, мультиграф без петель) был эйлеровым, необходимо и достаточно, чтобы степени всех вершин были чётными. Данный связный граф будет полуэйлеровым тогда и только тогда, когда степени двух вершин будут нечётными, а степени остальных вершин — чётными.

Доказательство этой теоремы начнём с так называемой леммы о рукопожатиях. Название этой леммы связано с тем, что эта лемма отвечает на следующий вопрос: «У вас собрались гости. Некоторые из них здороваются друг с другом посредством рукопожатий. Какими свойствами обладает число таких людей?» Ответ даётся следующей достаточно простой леммой.

Лемма о рукопожатиях (для неориентированного графа). Сумма степеней всех вершин графа — чётное число, равное удвоенному числу рёбер:

Доказательство. Возьмём пустой граф (есть вершины, но нет рёбер). Сумма степеней вершин такого графа равна нулю. При добавлении ребра, связывающего любые две вершины, сумма степеней всех вершин увеличивается на 2 (у одной вершины добавилась 1, у второй добавилась 1, в итоге 2, остальные по нулям). Продолжая добавления рёбер, на любом шаге получим, что сумма всех степеней вершин чётна и равна удвоенному числу рёбер (добавление ребра увеличивает сумму степеней всех вершин на 2, удаление ребра — уменьшает на 2). Лемма доказана.

Лемма о рукопожатиях (для ориентированного графа). Сумма входящих и исходящих степеней всех вершин ориентированного графа — чётное число, равное удвоенному числу дуг:

Доказательство аналогично доказательству леммы о рукопожатиях в неориентированном графе. Возьмём пустой граф и будем добавлять в него дуги. При этом каждое добавление дуги увеличивает на единицу сумму входящих и на единицу сумму исходящих степеней. Таким образом, сумма входящих и исходящих степеней всех вершин ориентированного графа чётна и равна удвоенному числу дуг.

С точки зрения задачи о рукопожатиях это означает, что число гостей, которые поздоровались за руку нечётное число раз, должно быть чётным.

Перейдём к доказательству теоремы Эйлера.

А) Необходимость. Пусть граф является эйлеровым. Тогда в нем имеется эйлеров цикл. Двигаясь по циклу, будем подсчитывать степени вершин. Так как все рёбра в цикле различны, прохождение каждой вершины добавляет 2 в степень этой вершины (то есть каждый «заход» в вершину и «выход» из неё даёт 2 степени вершины). Так как в цикл входят все рёбра, то, когда обход будет закончен, будут определены степени всех вершин, которые будут чётными. Таким образом, сумма степеней всех вершин чётна.

Б) Достаточность. Индукция по числу вершин . При связный граф имеет одну вершину, степень которой чётна, а в таком графе есть эйлеров цикл. В случае, когда в связном графе всего 2 вершины и обе они имеют чётную степень (в этом случае имеем мультиграф, один из которых изображён на следующем рисунке), ясно, что в этом случае имеется эйлеров цикл (при любой чётной степени этих двух вершин).