Примеры решения задач по курсу
Дискретная математика
Задания на понимание понятия множества и операций над множествами.
Могут ли иметь непустое пересечение множество красных яблок и множество зеленых фруктов?
Ответ. Нет
Если множество X содержит 10 элементов, а множество Y содержит 7 элементов, то сколько элементов может содержать их пересечение, объединение, разность?
Ответ. Пересечение от 0 до 7 элементов, объединение от 10 до 17 элементов, разность от 3 до 10 элементов
Множество зеленых яблок состоит из 6 элементов, а множество красных фруктов из 8 элементов. Сколько элементов может содержать их объединение, пересечение и разность.
Ответ. Пересечение 0 элементов, объединение 14 элементов, разность 6 элементов
Задать множество
Задать множество пар натуральных чисел, сумма которых равна 100.
Решение.
Задать множество всех натуральных чисел, являющихся числами Фибоначчи
Решение. Решением является алгоритм построения чисел Фибоначчи, а именно, взять числа 1 и 2. Далее, брать два последних добавленных числа, находить их сумму и добавлять в множество.
Проверить на диаграмме Венна справедливость тождества
Пример
Решение
Ответ: Тождество справедливо.
Найти пересечение, объединение, разность, декартово произведение множеств
Пример.
Решение
Определить какими свойствами обладает отношение на множестве и является ли оно отношением эквивалентности или порядка
Пример
Решение. Отношение симметрично, рефлексивно, транзитивно. Отношение не антисимметрично. Отношение является отношением эквивалентности
Задать отношение на множестве с заданными свойствами.
Пример.
На множестве
задать
отношение эквивалентности, разбивающее
множество на 3 класса
Решение:
Найти суперпозицию функций
Пример
Решение
Доказать, что множество имеет счетную мощность
Пример Доказать, что
множество
имеет
счетную мощность.
Решение. Отобразим
каждую пару на множество натуральных
чисел, используя функцию
.
Докажем, что эта функция отображает
каждую пару натуральных чисел в различные
натуральные числа.
Для графа, заданного отношением на множестве построить матрицу смежности, списки смежных вершин и нарисовать граф.
Пример
Решение
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
2 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
3 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
4 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
5 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
6 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
7 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
8 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
2,4 |
2 |
|
3 |
3,4,5,7 |
4 |
|
5 |
7 |
6 |
|
7 |
3 |
8 |
1,4 |
Для заданного графа перечислить вершины в порядке их обхода в ширину и в глубину
Пример. Граф задан списком смежных вершин. Обойти граф, начиная с вершины 1.
1 |
2,3,5 |
2 |
1,3 |
3 |
3,4,5,7 |
4 |
2,5,8 |
5 |
7 |
6 |
1,5,7 |
7 |
3,5,8 |
8 |
1,4 |
Ответ. Обход в ширину 1 2 3 5 4 7 8. Обход в глубину 1 2 3 4 5 7 8.
Построить Эйлеров цикл или Эйлеров путь в графе. Если путь или цикл не может быть построен доказать невозможность построения. Построить Гамильтонов цикл.
Пример Граф задан списком смежных вершин.
1 |
2,4 |
2 |
1,3,6 |
3 |
2,4,7,8 |
4 |
1,3,5,7 |
5 |
4,6,8 |
6 |
2,5,7,8 |
7 |
3,4,6,8 |
8 |
3,5,6,7 |
Ответ. Есть Эйлеров путь (2,1)(1,4),(4,7),(7,3),(3,2),(2,6),(6,7),(7,8),(8,3),(3,4),(4,5),(5,8),(8,6),(6,5)
Есть Гамильтонов цикл (1,2),(2,3),(3,7),(7,8),(8,6),(6,5),(5,4),(4,1)
Построить матрицу достижимости, найти области сильной связности и построить диаграмму порядка графа
Пример Граф задан списком смежных вершин
1 |
2,6 |
2 |
4,7 |
3 |
|
4 |
2,5,8 |
5 |
6 |
6 |
5 |
7 |
3,5 |
8 |
2 |
Ответ. Матрица достижимости
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
2 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
3 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
4 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
5 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
6 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
7 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
8 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
Области сильной связности A={1,2,4,8}, B={5,6}, C={3}, D={7}
Матрица смежности диаграммы порядка
|
A |
B |
C |
D |
A |
0 |
1 |
0 |
1 |
B |
0 |
0 |
0 |
0 |
C |
0 |
0 |
0 |
0 |
D |
0 |
1 |
1 |
0 |