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

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

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

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

.

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

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

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

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

, ?

5. Найти число целых положительных чисел, не превосходящих 1000 и не делящихся ни на одно из чисел 6, 10 и 15?

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

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

8. В комнате студенческого общежития живут трое студентов. У них есть 4 чашки, 5 блюдец и 6 чайных ложек (все чашки, блюдца и ложки отличаются друг от друга). Сколькими способами они могут накрыть стол для чаепития (каждый получает одну чашку, одно блюдце и одну ложку).

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

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

; ,.

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

.

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

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

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

1

7

_{2 2 3 5 2}

_{5 1 6}

₁

1 2 5 4 8

₂

15. Построить кратчайший остов для графа, заданного матрицей расстояний между его вершинами:

.

16. Для данного графа построить две системы базисных циклов. Выразить циклы одной системы через циклы другой.

17. Построить максимальный поток в транспортной сети:

_{15 12 4}

7 3 7

_{4 4 2}

_{6 6 3 8}

_{12 15}

18. Определить словарный ранг матрицы:

.

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

_{7 3}

_{6 8 16}

_{5 6 12 16 4 8}

6 4 5 _{12 15}

2 4 6 7

_{7 2 4 7 5 5}

начало 4 10 9 3 _{4 конец}

_{8 7 4 6}

20. Построить сетевой график по заданной упорядоченности работ и определить критическое время выполнения всей совокупности работ:

Работа
Предшественники	–	–
Продолжительность	3	4	3	6	2	5	4	2	2