Вопросы к экзамену по курсу “Дискретная математика” (стр. 1 )

Вопросы к экзамену по курсу “Дискретная математика”

Множества, способы их задания, операции над множествами, алгебра множеств. Алгоритм Дейкстры маршрутизации в графе. Специальные отношения: отношение эквивалентности, разбиение на  классы. Специальные отношения: отношение порядка. Деревья,  остовные деревья. Алгоритм построения остовного дерева минимального веса. Отношения, задание отношений матричным способом, граф отношений, операции над отношениями, виды отношений. Основные понятия комбинаторики, сочетания, перестановки, размещения.. Основные понятия комбинаторики, перестановки с повторениями. Основные понятия комбинаторики, композиции, сочетания с повторениями. Свойства биномиальных коэффициентов, формула бинома Ньютона. Понятие функции, область определения, область значений, композиция функций, образ-прообраз множества при действии функции. Радиус графа, центр графа, диаметр графа. Понятие сети, потока, алгоритм Форда Фалкерсона. Формула включения-исключения. Лексиографический порядок, лексиографически-следующая перестановка. Независимые множества в графе, алгоритм построения дерева вариантов при нахожднгии всех независимых подмножеств.

Задачи к экзамену по курсу “Дискретная математика”.

Бинарные отношения и действия над ними.

Бинарные отношения на универсуме даны следующим образом: Отношение дано своей матрицей, например, , а бинарные отношения заданы перечислением своих кортежей
например, следующим образом., .

Найти бинарные отношения – результаты следующих операций

1) ;

2) ;

3) ;

4) ;

5) ;

Пример выполнения. Выполним сначала требуемые операции в ручную, используя для их выполнения матричное представление отношений.

Сначала сформируем матрицы отношений . Имеем: , 

1) Имеем:

Итак, найдена матрица первого расчетного отношения:. Из матричного представления получаем кортежный состав отношения

Для выполнения второй операции имеем:

Таким образом, получен ответ относительно результата во втором задании:

. Отсюда получаем кортежный состав отношения : . Также мы можем выразить состав отношения в виде ориентированного графа:

Аналогично выполняем расчет состава отношения третьего пункта. Имеем:

Таким образом, нашли, что . Отсюда, далее, получаем:

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

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

, т. е. каждую строку первой матрицы умножаем на каждый столбец второй матрицы и применяем функцию . Получаем

Получаем состав отношения его граф:

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

Рассматривая составной переход, сначала по стрелкам отношения , а затем по стрелкам отношения

2. Отношение порядка.

Частично-упорядоченное множество задано своей диаграммой Хассе. Выполнить следующие действия.

1) Для каждого элемента множества указать его высоту в структуре упорядоченного множества ;

2) Найти высоту данного упорядоченного  множества;

3) Указать множества всех максимальных элементов посет и множество минимальных элементов;

4) Выписать множество всех максимальных цепей упорядоченного множества;

5) Выписать матрицу отношения сравнимости и матрицу отношения независимости для элементов посет;

6) Для всех элементов выписать левые интервалы и правые интервалы в структуре упорядоченного множества, где ;

7) Для всех пар элементов таких, что выписать интервалы , где ;

8) Выписать матрицу отношения накрытия;

9) Выписать множество всех максимальных антицепей упорядоченного множества;

10) Определить ширину упорядоченного множества как максимальную мощность его антицепей;