Дискретная математика
1. Дано: универсальное множество U и X, Y,
Z Í
U.
U = {a,
b, c, d} X = {a,
c} Y = {a,
b, d} Z = {b,
c};
Найти: a) (XÈZ)Ç`Y b)`X
ÇY c) X \ (`ZÈY);
Решение:
a)`Y
= U\Y `Y = (abcd)\(abd) `Y
= c;ÈZ = (ac) È
(bc) = (abc);
(abc) Ç
c = c;) `X = U\X, `X
= (abcd)\(ac), `X = (bd);
`XÇY, (bd)Ç(abd)
= bd;) `Z = U\Z, `Z
= (abcd)\(bc), `Z = ad;
`ZÈY
= (ad)È(abd) = (abd)\(`ZÈY), (ac)\(abd)
= c;
Ответ: a) c; b)
bd; c) c.
2. Пусть множества A,
B, C
Í U;
Продемонстрировать диаграммами Эйлера - Венна
что:
a) A È
(B \ C) = (A È B) \ (C \ A);) A \ (B È
C) = (A \ B) Ç (A \ C);
Рассмотрим левую часть равенства (а);
Найдем сперва разность множеств В и С;
Рис.
Теперь найдем объединенное множество А È
(В \ C);
Рис.
Теперь рассмотрим правую часть равенства (а);
Найдем разность множеств С и A;
Рис.
Теперь найдем объединение А и В;
Рис.
Затем найдем разность множеств (AÈB)
и (C \ A);
Рис.
И сравним полученные диаграммы из левой и правой
части:
Рис.
Мы видим, что левая и правая части действительно
равны.
Перейдем теперь к равенству (b) и рассмотрим его
левую часть;
Покажем объединение множеств В и С:
Рис.
И вычтем из множества А полученное множество (BÈC):
Рис.
Перейдем к правой части равенства, и найдем
разности множеств (A \ B) и множеств (А \ C);
Рис.
И найдем пересечение полученных множеств;
Рис.
А теперь сравним полученные диаграммы из левой и
правой частей:
Рис.
И вновь мы видим равенство левой и правой
частей.
. Доказать справедливость:
`A`È`B
= `A
Ç`B;
Доказательство:
Рассмотрим левую часть равенства;
`A`È`B
= U \ AÈB
= U,
поскольку другие множества не включены в
универсальное множество U, то результатом вычитания из универсального множества
включенных в него множеств А и В, объединенных во множество АÈВ,
будет само универсальное множество U.
Теперь рассмотрим правую часть равенства;
`А = U\A = B;
`B
= U\B
= A;
А Ç В = U,
поскольку другие множества не включены в
универсальное множество U и по условию задачи множества Аи В не имеют общих
множеств, то и результатом пересечения двух имеющихся множеств будет само
универсальное множество U.
И поскольку, левая и правая части равенства
равны U, значит они равны друг другу, ч.т.д.
4. Это задача на перестановки с повторениями
Значит вычисляем по формуле:
Р(n1!n2!...nk!)
= n!/ n1!n2!...nk!
Тогда
Р = 17! / 5!5!4!3! = 24504480
Ответ: 24504480
. Имеем буквы с выборкой по 3 из 30 букв, и
цифры с выборкой по 4 из 10.
Так как в комбинации букв цифры не входят,
комбинации можно искать по отдельности, но общее количество комбинаций должно
быть перемножено.
А330 = 30!/(30 - 3)! = 30
* 29 * 28 = 24360;
А410 = 10!/(10 - 4)! = 10
* 9 * 8 * 7 = 5040;
И найдем произведение:
* 5040 = 122774400;
Ответ: 122774400.
. Для того, чтобы число, составленное из
заданных цифр, делилось на 5, достаточно, чтобы цифра 5 стояла на последнем
месте. Остальные пять цифр могут стоять на оставшихся местах в любом порядке.
Значит, искомое число шестизначных чисел, кратных пяти, равно числу
перестановок из пяти элементов, т.е.
Ответ: 120.
7.составим рекуррентное соотношение:
составим характеристическое
уравнение:
имеем корни
по формулам находи общее решение:
, где
получим
. Построим по матрице весов граф.
Рис.
Затем выберем начальной вершиной вершину В, и
расслабим соседние вершины D
и E.
Рис.
Затем, выбираем наименьшую вершину, т.е. Е, и
продолжаем выполнение алгоритма поиска минимального покрывающего дерева.
Рис.
Рис.
Рис.
Рис.
. Построим дерево кратчайших расстояний из
вершины V0, используя
алгоритм Дейкстры
Рис.
величина задача
дискретный математика
Рис.
Маршрут V0
,
V3,
V4,
V1,
V2,
V5 является
кратчайшим, т.к. его длина равняется 5, в то время как длина маршрутов V0,
V5; V0
, V3
, V4
, V5
; V0
, V1
, V2
, V5
; V0
, V3
, V2
, V5
равна 6.
. Найдем величину максимального потока в сети,
используя алгоритм Форда - Фалкерсона.
Рис.
Для начала заполним все потоки так:
Рис.
И так:
Рис.
В результате мы имеем полностью заполненную
сеть, где пропускная способность инкрементых вершине Т дуг полностью истрачена,
и значит больше пропустить через эту вершину уже невозможно.
Рис.
Таким образом величина максимального потока в
сети равна сумме величин потоков на дугах инкрементных выходной вершине Т, т.е.
равна 6.
Если провести проверку, то мы увидим, что в
каждую вершину сколько потоков вошло, столько же и вышло, как и во всей сети в
целом: вошло шесть и вышло шесть.
Мое мнение об этом примере таково, что он не
удачен для демонстрации работы алгоритма, поскольку вся сеть заполняется всего
за один подход, и дальнейшие вычисления, которые есть суть алгоритма,
становятся лишними.
3.