Ответы на контрольные вопросы
Тема 1
1. Да.
2. Если А
В.
3. Пустое множество.
4. Да. Например, множество целых чисел эквивалентно множеству четных чисел.
5. Мощность множества точек отрезка [0, 1] больше. Это множество имеет мощность континнуума, а множество натуральных чисел является счетным множеством.
Тема 2.
1. Перечислением упорядоченных пар, указанием общего свойства упорядоченных пар, матрицей бинарного отношения.
2. Рефлексивного.
3. Для симметричного.
4. Для транзитивного.
5. Например, отношение параллельности прямых есть отношение эквивалентности. Пусть x и y – углы наклона прямых x и y с осью абсцисс. Тогда отношение = {x, y x y} есть отношение частичного порядка.
6. Функция может быть задана таблицей, формулой, рекурсивной процедурой, с помощью описания.
7. б).
Тема 3.
1. б).
7. Нет. Только для неориентированного графа.
8. Нужно сложить все элементы матрицы и полученную сумму разделить на 2.
10. Нет.
11. а) и б).
12. Нет.
15. Да .
16. а), д)
17. г).
18. Нет.
19. Нет.
21. г).
22. n – 1.
23. Наименьшее – n – 1 (дерево), наибольшее – n( n – 1) 2 (полный граф).
24. Наименьшее – 0 (несвязный граф), наибольшее – n( n – 1) 2 (полный граф).
25. Нет.
27. Одну.
28. Нет.
29. Нахождение минимального пути.
30. Нахождение минимального пути.
31. Нахождение минимального остовного дерева.
32. Нахождение минимального остовного дерева.
33. Нахождение минимального остовного дерева.
34. Нахождение минимального остовного дерева.
Тема 4.
1.
а)22
;
б) 2n.
2. а).
3. а) бесконечно много; б) ноль или одна; в) бесконечно много; г) ноль или одна.
4. а)ДНФ; б)ДНФ, СДНФ, КНФ; в)КНФ; г)ДНФ, КНФ, СКНФ; д)ДНФ; е)ДНФ, КНФ; ж)ДНФ, КНФ.
11. а) и б).
Указания к выполнению лабораторных работ
Лабораторные работы проводятся с помощью обучающей компьютерной системы "Теория графов". В лабораторных работах используются следующие разделы этой системы: "Основные понятия теории графов", "Экстремальные пути в графах".
Чтобы приступить к выполнению лабораторной работы необходимо запустить систему с помощью файла run.bat; выбрать в главном меню пункт "Обучающие программы"; указать раздел; выбрать пункт "Упражнения".
В процессе работы возможно обращение к теоретическому материалу, используя соответствующие пункты меню, а также алфавитный указатель.
Лабораторная работа №1. Основные понятия. Ориентированные графы
Для выполнения этой работы требуется изучить следующие понятия для ориентированного графа: определения дуги, пути, контура, односторонней и сильной связности, компоненты сильной связности, матриц смежности, инцидентности, сильной связности.
Лабораторная работа №2. Основные понятия. Неориентированные графы
Для выполнения этой работы требуется изучить следующие понятия для неориентированного графа: определения ребра, маршрута, цикла, связности, компоненты связности, матриц смежности, инцидентности, связности.
Лабораторная работа №3. Экстремальные пути в графах
Для выполнения этой работы требуется изучить определения нагруженного графа, минимального пути, максимального пути, кратчайшего пути, а также алгоритм Форда – Беллмана.