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

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

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

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

.

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

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

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

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

, ?

5. Сколькими способами можно выбрать 12 человек из 17, если данные двое человек из этих 17 не могут быть выбраны вместе?

6. Сколькими способами можно переставить буквы слова «перешеек» так, чтобы четыре буквы «е» не шли подряд?

7. Шестеро студентов сдают экзамен. Сколькими способами могут быть поставлены им оценки, если известно, что никто из них не получил неудовлетворительной оценки?

8. Сколько можно построить различных четырехугольников, длина каждой стороны которых является целым числом от 1 до 5?

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

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

; , .

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

.

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

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

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

10

1 10 1 2 5

_{10 4 2}

_{6 4 1 5 8}

_{3 5}

3 2 6 3

₈

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

.

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

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

_{10 12}

2 2 2 6

_{1 4 6}

_{6 2 4 4}

_{14 10}

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

.

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

_{5 3}

_{7 7 2}

_{5 10 4 9 7}

3 1 5 _{12 15 конец}

2 5 5

_{5 2 9 5}

начало 7 11 5 1 ₅

_{3 11 5}

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

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