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. Построить сетевой график по заданной упорядоченности работ и определить критическое время выполнения всей совокупности работ:

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

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

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

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

.

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

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

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

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

, ?

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

6. Сколькими способами можно выстроить 9 человек в колонну по 3, если в каждой шеренге люди выстраиваются по росту и нет людей одинакового роста?

7. Сколькими способами можно разбить 30 рабочих на 3 бригады по 10 человек в каждой бригаде?

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

9. Найти производящую функцию последовательности

,

где .

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

; , .

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

.

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

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