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