Типовой расчет по дискретной математике множества. Комбинаторика. Графы и сети вариант 2

1. Упростить, используя булевы тождества:

(после упрощения в формуле должно быть не менее трех букв).

2. Представить множество в виде суммы конституент:

.

3. Справедливо ли следующее теоретико-множественное тождество:

4. Какое из отношений

1) ; 2) ; 3) : 4) никакое из указанных в 1)-3)

имеет место для множеств и :

, ?

5. Сколькими способами можно выбрать из слова «логарифм» две согласных и одну гласную букву?

6. Сколькими способами можно составить из 9 согласных и 7 гласных слова, в которые входят 4 различных согласных и 3 различных гласных?

7. Сколькими способами можно разложить 10 книг на 5 бандеролей по 2 книги в каждой?

8. Каково число матриц из строк и столбцов с элементами из множества

{0, 1}?

9. Найти , где .

10. Найти решение линейного рекуррентного соотношения

; , .

11. Выделить компоненты связности графа, заданного матрицей смежности . Определить степени вершин и цикломатическое число графа.

.

12. Найти диаметр, радиус и центры графа:

13. Построить кратчайшую цепь между вершинами и в ненагруженном графе:

14. Построить кратчайшую цепь между вершинами и в нагруженном графе:

1

7

_{2 2 3 5 2}

_{5 1 6}

₁

1 2 5 4 8

₂