Дискретная математика вопросы к экзамену
.docx-
Понятие множества. Определение подмножества. Равные множества. Операции пересечения, объединения и дополнения. Примеры.
-
Законы алгебры множеств. С доказательством одного из законов.
-
Последовательности. Декартово произведение двух множеств. Примеры. Декартово произведение n-множеств. Примеры.
-
Определение соответствия. Функциональное, полное, сюръективное, инъективное, биективное (взаимно-однозначное) соответствие. Примеры.
-
Определение отображения. Инъективные, сюръективные, биективные отображения. Примеры.
-
Определение отношения. Свойства бинарных отношений. N-местное отношение на множестве А. Примеры.
-
Отношение эквивалентности. Классы эквивалентности. Фактор-множество. Примеры.
-
Отношение частичного порядка. Частично упорядоченное множество. Диаграммы Хоссе. Примеры.
-
Частично упорядоченное множество. Наименьший, наибольший, максимальные, минимальные элементы частично упорядоченного множества.
-
Частично упорядоченное множество. Верхняя (наименьшая верхняя) и нижняя (наибольшая нижняя) грани подмножества В в множестве А. Примеры.
-
Понятие равномощных множеств. Мощность конечного множества. Примеры.
-
Счетное множество. Свойства счетных множеств. С доказательством одного из свойств.
-
Представление множества в алгебре множеств, порожденной системой образующих. Конституэнта, первичный терм, элементарное пересечение, нормальная форма кантора. Совершенная нормальная форма кантора. Примеры
-
Алгоритм нахождения минимальной формы кантора. Нахождение простых импликант. Таблица Квайна. Покрытие строк столбцами. Ядро покрытия. Пример.
-
Алгоритм нахождения минимальной формы кантора. Нахождение простых импликант. Сокращенная нормальная форма кантора. Таблица Квайна. Пример.
-
Граф ориентированный и не ориентированный – основные определения. Понятие псевдографа, мультиграфа.
-
Пустой, полный, двудольный графы, полный двудольный граф. Плоский и планарный граф. Примеры.
-
Степени вершин. Расстояние между вершинами, диаметр графа. Четные (нечетные) вершины. Число нечетных вершин в графе. Примеры.
-
Степени вершин графа. Связь между суммой степеней всех вершин и количеством ребер. Количество нечетных вершин графа.
-
Изоморфизм графов. Свойства изоморфизма графа. Примеры.
-
Способы задания графа. Примеры.
-
Маршруты, цепи, циклы. Способы записи маршрутов. Простые цепи и циклы. Примеры.
-
Связный граф. Компоненты связности графа. Разделяющее множество, разрез, перешеек. Точки сочленения. Примеры.
-
Ориентированный граф. Понятие слабой и сильной связности ориентированного графа. Примеры.
-
Теорема о возможности выделения простой цепи в маршруте соединяющем две разные вершины.
-
Алгоритм Терри. Первая часть обоснования алгоритма Терри.
-
Признак существования эйлерова цикла в связном графе. Алгоритм выделения эйлерова цикла.
-
Двудольный граф. Признак двудольности графа. Доказательство достаточности.
-
Двудольный граф. Признак двудольности графа. Доказательство необходимости.
-
Доказательство того, что связный граф, имеющий число ребер на единицу меньше чем вершин является деревом.
-
Доказать равносильность двух определений дерева:
а) граф у которого две любые вершины соединяются единственной и притом простой цепью
б) связный граф, не имеющий циклов.
-
Доказательство того, что у дерева число ребер на единицу меньше, чем вершин.
-
Остовное дерево связного графа. Алгоритм выделения остовного дерева связного графа с обоснованием.
-
Определение взвешенного графа. Алгоритм №1 нахождения кратчайшего маршрута во взвешенном графе.
-
Определение взвешенного графа. Алгоритм №2 нахождения кратчайшего маршрута во взвешенном графе.
-
Цикломатика. Базисная система циклов. Цикломатическое число.
-
Алгоритм нахождения базисной системы циклов.
-
Определение взвешенного графа. Алгоритм Дейкстора нахождения кратчайшего маршрута во взвешенном графе.
-
Определение взвешенного графа. Безымянный алгоритм нахождения кратчайшего маршрута во взвешенном графе.