Материал: ПОДГОТОВКА К ЭКЗАМЕНУ ДИСКРЕТНАЯ МАТЕМАТИКА

13. Отношения порядка. Диаграмма Хассе.

Отношение нестрогого порядка – это отношение, обладающее свойствами рефлексивности, антисимметричности и транзитивности.

Отношение строго порядка – это отношение, обладающее свойствами антирефлексивности, антисимметричности и транзитивности.

Для обоих типов отношений порядка, элементы и сравниваются по отношению порядка , если выполняется или.

Множество, на котором задано отношение порядка, называется линейно (полностью) упорядоченным, если любые два элемента множества сравнимы, а в в противном случае - частично упорядоченным.

Пример

Отношения идля чисел являются отношениями нестрого порядка, отношения < и > – отношениями строгого порядка.

Диаграмма Хассе – это графическое изображение частично или линейно упорядоченных множеств.

Диаграмма Хассе строится сле­дующим образом. Меньшие по порядку элементы располагают ниже, а большие – выше; и проводят линии, показывающие, какой из двух элементов больше, а какой меньше другого.

14. Алгебра. Тип алгебры, сигнатура. Примеры.

Сигнатура алгебры – это множество операций.

Тип алгебры – последовательность рангов операций входящих в сигнатуру.

Ранг операции – к-во операндов.

15. Замыкания и подалгебры.

Про подалгебры:

Алгебра Вета – подалгебра однотипной ей алгебры Альфа, если B – подмножество А и тождественное отображение множества В в А является мономорфизмом, то есть каждая главная операция алгебры Вета является ограничением соответствующей операции алгебры Альфа множеством В.

Про замыкания:

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

16. Свойства бинарных операций. Примеры.

Коммутативность (переместительность)

Свойство бинарной алгебраической операции при котором выполняется условие: где — некоторое рассматриваемое множество.

Примеры:

• Сумма и произведение действительных чисел

• Конъюнкция и дизъюнкция

• объединение, пересечение и симметрическая разность множеств

Ассоциативность (сочетательность)

Свойство бинарной алгебраической операции при котором выполняется условие: где — некоторое рассматриваемое множество.

Примерами ассоциативных операций являются:

• сложение действительных чисел:

• {\displaystyle (a+b)+c=a+(b+c)}умножение действительных чисел:

• {\displaystyle (a\cdot b)\cdot c=a\cdot (b\cdot c)}композиция функций

Дистрибутивность (распределительный закон ) — свойство согласованности двух бинарных операций, определённых на одном и том же множестве.

Говорят, что две бинарные операции «+» и «×» удовлетворяют свойству дистрибутивности, если для любых трёх элементов:,

дистрибутивность слева;

дистрибутивность справа.

17. Комбинаторные задачи. Модели комбинаторных задач

Комбинаторные задачи – это задачи, требующие осуществления перебора всех возможных вариантов или подсчета их числа.

18. Правила суммы и произведения. Формула включения и исключения.

Правило суммы. Пусть некоторый объект A можно выбрать n различными способами, а другой объект B можно выбрать m способами. Тогда существует  n+m способов выбрать либо объект A, либо объект B. 

Правило произведения. Пусть объект A можно выбрать n способами и после каждого такого выбора объект B можно выбрать m способами. Тогда выбор пары (A,B) можно осуществить n*m способами.

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

Для случая из двух множеств  формула включения-исключения имеет следующий вид:

18. Основные типы наборов комбинаторики: размещения, сочетания, перестановки.

18. Подсчет разбиений в комбинаторике.

18. Биномиальные коэффициенты. Основные тождества.

Число n называется верхним индексом, а k — нижним. В соответствии с комбинаторной интерпретацией, числа n и k должны быть целыми неотрицательными.

Смысл: Выясним, сколько раз встречается многочлен при данном . Он встретится столько раз, сколькими способами можно выбрать скобок, из которых берется , т.е. .

22. Бином Ньютона — формула для разложения на отдельные слагаемые целой неотрицательной степени суммы двух переменных, имеющая вид

22. Граф. Основные понятия.

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

Неориентированный граф - это упорядоченная пара (V, E), где

V - это непустое множество вершин

E - это множество неупорядоченных пар вершин, называемых рёбрами.

Ориентированный граф (сокращённо орграф) — это упорядоченная пара (V, A), где

V — это непустое множество вершин или узлов,

A — это множество упорядоченных пар различных вершин, называемых дугами или ориентированными рёбрами.

Два ребра называются кратными, если они связуют одни и те же вершины.

Ребро называется петлей, если его концы совпадают.

Мультиграф – граф, у которого все ребра кратные.

Псевдограф – граф с петлями.

Простой граф – граф без кратных ребер и петель.

Пустой граф – граф без ребер. Ноль-граф – граф без вершин.

Два ребра называются смежными, если они имеют общую вершину.

Любое ребро инцидентно двум вершинам, которые оно соединяет, и эти вершины инциденты этому ребру.

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

Вершина называется изолированной, если она не является концом ни для одного ребра; висячей, если она является концом только одного ребра.

Операции над графами:

 Объединением    графов      и       называется граф , множество вершин которого есть объединение множеств вершин графов  и , а множество ребер является объединением множеств ребер  этих графов .

        Пересечением графов  и  называется граф , множество вершин которого , а множество ребер .

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