Вопросы к зачёту по Дискретной математике

Высказывания, операции над высказываниями.

Формулы ИВ и таблицы истинности. Логическое следствие и равносильность формул ИВ.

Тавтологии. Список основных тавтологий.

Множества. Способы задания множеств. Подмножества. Равенство множеств. Пустое множество. Универсальное множество.

Теоретико-множественные операции и их свойства.

Декартово произведение множеств. Соответствия. Язык стрелок. Виды соответствий. Отображения и их виды.

Композиция соответствий и отображений. Ассоциативность композиции. Обратное соответствие и отображение. Критерий обратимости отображения. Алгебраические операции. Арность операции. Свойства бинарных операций.

Бинарные отношения и их свойства. Отношение порядка. Виды порядков.

Отношение эквивалентности. Свойства классов эквивалентности. Фактормножество.

Понятие предиката. Местность предиката Область определения, и область истинности. Кванторы. Формулы ИП.

Взаимодействие кванторов и логических связок. Логическая зависимость формул ИП.

Предмет комбинаторики. Правила умножения и сложения. Лексико-графический порядок и перебор.

Основные комбинаторные соединения. Формулы для подсчета числа размещений, перестановок, размещений с повторениями и сочетаний.

Формула для подсчета числа сочетаний с повторениями.

Формула бинома. Свойства биномиальных коэффициентов. Треугольник Паскаля.

Вычисление количества подмножеств конечного множества.

Полиномиальная формула.

Разбиения чисел. Разбиения множеств. Числа Стирлинга второго рода. Треугольник Стирлинга.

Подсчет количества соответствий, отображений, инъективных отображений, биекций.

Метод включения и исключения и подсчет количества сюръективных отображений. Связь количества сюръективных отображений и чисел Стирлинга второго рода. Числа Белла.

Подсчет количества элементов в объединении нескольких множеств.

Рекуррентные соотношения. Решение линейных однородных рекуррентных соотношений второго порядка.

Рекуррентное и явное задание чисел Фибоначчи.

Графы. Пустые и полные графы. Инцидентность, смежность, степени вершин. Лемма о рукопожатиях. Двудольные графы. Подграфы.

Изоморфизм графов.

Маршруты, пути, простые пути, циклы, простые циклы.

Связность. Компоненты связности.

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

Расстояние в связных графах. Эксцентриситет вершины. Диаметр и радиус графа. Соотношение между диаметром и радиусом.

Деревья. Критерии дерева.

Эйлеровы графы. Критерий эйлеровости.

Гамильтоновы графы.

Планарные графы. графы. Формула Эйлера.

Непланарность графов K₅ и K_3,3. Критерий планарности графов.

Вершинная и реберная раскраска графов. Хроматическое число и хроматический индекс графа. Проблема четырех красок.

Элементы теории Рамсея.

Обобщение понятия графа. Псевдографы. Мультиграфы. Орграфы. Бинарные отношения и их свойства с позиций теории графов. Взвешенные графы. Обобщенные графы.

Способы задания графов и обобщенных графов.

Поиск в глубину в графе. Задачи, решаемые с помощью поиска в глубину.

Поиск в ширину в графе. Задачи, решаемые с помощью поиска в ширину.

Остов графа.

Образцы задач:

1. Сколькими способами из колоды (52 карты) можно взять пять карт, чтобы достоинства этих карт шли через одно (например, четверка, шестерка, восьмерка десятка, дама)?

2. Сколько существует семизначных натуральных чисел, у которых первая цифра строго больше всех остальных и равна сумме двух последних цифр?

3. Сколько существует семизначных натуральных чисел, у которых первая и последняя цифра уникальны (т.е. больше не встречается в записи числа)?

4. Сколько существует подмножеств множества {1, 2, 3, ... 50}, в которых сумма всех элементов четна?

5. Сколько существует подмножеств множества {1, 2, 3, ... 13}, в которых четных чисел больше, чем нечетных?

6. Сколько существует отображений множества {1, 2,..., 50} во множество {1, 2,..., 100}, при которых числа кратные 3 переходят в числа не кратные 3 и наоборот, числа не кратные 3 переходят в числа кратные 3?

7. Сколько существует четырехзначных натуральных чисел, у которых первая цифра в тринадцать раз меньше суммы всех остальных?

8. Сколько существует восьмизначных натуральных чисел, у которых первая цифра в два раза больше произведения всех остальных?

9. Сколько существует матриц размерности 5х5, каждый элемент которых цифра, и таких, что в каждой строке встречаются ровно две цифры?

10. Сколько существует матриц размерности 5х5, каждый элемент которых цифра, и таких, что произведение элементов главной диагонали и каждой строки равно 105?

11. Сколько существует пятизначных натуральных чисел, у которых сумма цифр больше их произведения?

12. Сколько существует пятизначных натуральных чисел, цифры которых в порядке следования в числе образуют арифметическую прогрессию?

13. Сколько вершин эксцентриситета 17 может быть в 20-вершинном графе?

14. Сколько висячих вершин может быть в 12-вершинном дереве диаметра 5:

15. Сколько компонент связности может быть у 14-вершинного графа, все степени вершин которого равны 3?

16. Граф G =<V,E> задан на множестве V = {1, 2,..., 200} по правилу: {a, b}  E  a+b = 198  a+b = 199. Сколько компонент связности содержит этот граф?

17. В 20-вершинном графе 4 компоненты связности, каждая из которых не является деревом. Сколько ребер может быть в таком графе?

18. Две вершины 12-вершинного дерева диаметра 6 соединили ребром, образовав цикл. Каким может оказаться диаметр полученного графа?

19. Граф G =<V,E> задан на множестве V = {1, 2,..., 200} по правилу: {a, b}  E  a  b > 101. Сколько компонент связности содержит этот граф?

20. Граф G =<V,E> задан на множестве V = {1, 2,..., 30} по правилу: {a, b}  E  a  b = 5  a-b = 2. Каков диаметр этого графа?

21. Граф G =<V,E> задан на множестве V = {1, 2,..., 200} по правилу: {a, b}  E  ab = 20  ab = 8. Сколько компонент связности содержит этот граф?

22. Граф G =<V,E> задан на множестве V = {1, 2,..., 100} по правилу: {a, b}  E  сумма цифр a равна b или сумма цифр b равна a. Сколько компонент связности содержит этот граф? Каков диаметр каждой компоненты?

23. Какое наибольшее количество вершин степени 5 может содержать 30-вершинное дерево?

24. Какое наибольшее количество вершин степени 5 может содержать 30-реберный граф?

25. Какое наименьшее количество вершин граф, у которого есть вершины степеней 1, 2, 3, 4, 5, 6, 7 и 8?

26. Какое минимальное количество вершин может содержать граф, если у него 5 компонент связности, каждая из которых не является пустым графом а число ребер в 5 раз больше числа вершин?