Контрольная работа №1 по дисциплине: Дискретная математика. Онлайн

1. На карту Карно (см. рисунок) нанесены значения булевой функции f(x,y)
Запишите минимальную дизъюнктивную нормальную форму булевой функции с помощью данной карты Карно
f(x, y) = yx ∨ xy
f(x, y) = x & y
f(x, y) = x ∨ y
f(x, y) = x ∨ y

2. После пропускания потока в транспортной сети (см. рисунок) насыщенным оказались дуги: U = (s, 5), (s,2 ), (3, t), (5, 3), (5, 6), (4, t), (6, t).
Выделите дуги минимального разреза данной сети

3. Найдите все максимальные полные подграфы в графе G(X, U), где U = {(x1x2),(x1x3),(x3x4),(x2x4)}.

4. Упростите булеву формулу f(x, y, z) = x(y ∨ z)(x ∨ y ∨ z)

5. Граф G=(X, U) задан матрицей смежности D
Определите, содержит ли граф G эйлерову цепь

6. На карту Карно (см.рисунок) нанесены значения булевой функции f(x, y)
Приведите функцию f(x, y) к минимальной ДНФ
f(x, y) = (x ∨ y)(x ∨ y)(x ∨ y)
f(x, y) = yx ∨ xy
f(x, y) = x ∨ y
f(x, y) = xy

7. 1) Раскрасьте вершины графа G=(X, U), применяя метод Магу-Вейсмана, если U = {(x1x2), (x3x4), (x3x2), (x1x3), (x1x4), (x2x4)}.
2) Определите хроматическое число
3) Выделите множества вершин K(G), которым можно прописать одно и тоже натуральное число или цвет.

8. После пропускания потока в транспортной сети (см.рисунок) насыщенными оказались дуги: U = (s, 5), (s,2 ), (3, t), (s, 1), (5, 6), (4, t), (6, t).
Выделите дуги минимального разреза данной сети.

9. Вычислите значение максимального потока Фmax на сети T= , где за скобками нижний индекс соответствует пропускной способности, верхний = величине потока на дуге (xixj).

10. Запишите в форме СКНФ функцию f(x1, x2, x3), представленную таблицей истинности.

11. Универсальное множество | включает целые числа: 1, 2, ..., 100. Множество M = {35, 12, 34, 56}. Определите элементы множества

12. После пропускания потока в транспортной сети (см.рисунок) насыщенным оказались дуги: U = (1, 3), (5,3 ), (5, 6), (2, 6), (2, 4), (4, t), (3, t), (6, t).
Выделите дуги минимального разреза данной сети.

13. Определите радиус и диаметр в графе G по его матрице метрике M (см. таблицу).

14. Для графа G(X, U), где U = {(x1x2),(x3x4),(x3x2),(x1x3),(x1x4)}, по графу его дополнения напишите минимальное выражение произведения логических переменных x1, x2, x3, x4, позволяющее выделить подмножества вершин в графе G, образующие все его максимальные полные подграфы.

15. Определите периферийные и центральные вершины в графе G по его матрице метрике M (см. таблицу).

16. Укажите концевые вершины эйлеровой цепи в графе G (см. рисунок).

17. Определите, относиться ли граф G(X, U), где U = {(x1x2), (x3x4), (x1x3), (x2x4), (x1x4), (x1x1), (x3x2)}, к классу обыкновенных графов.
Не относится
Относиться к классу смешанных графов
Относится

18. После пропускания потока транспортной сети (см. рисунок) насыщенными оказались дуги: U = (s, 1), (s, 5 ), (5, 6), (3, t), (6, 3), (4, t).
Определите, имеются ли ненасыщенные пути, связывающие исток s и сток t.

19. Решите задачу с помощью диаграмм Эйлера-Венна (см. рисунок).
Из 100 приехавших туристов 75 знали немецкий язык и 83 - французский, 10 человек не знали ни немецкого, ни французского. Сколько туристов знали оба языка?
70 человек знали оба языка
74 человека знали оба языка
58 человек знали оба языка
68 человек знали оба языка

20. На карту Карно (см. рисунок) нанесены значения булевой функции f(x, y).
Запишите СКНФ булевой функции заданной картой Карно

Оценка: Зачет

Помогу с вашим вариантом, другой работой или дисциплиной.
E-mail: sneroy20@gmail.com