Указания к выполнению лабораторных работ

Тема 4.

Тема 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. Нахождение минимального остовного дерева.

1. а)2² ; б) 2ⁿ.

2. а).

3. а) бесконечно много; б) ноль или одна; в) бесконечно много; г) ноль или одна.

4. а)ДНФ; б)ДНФ, СДНФ, КНФ; в)КНФ; г)ДНФ, КНФ, СКНФ; д)ДНФ; е)ДНФ, КНФ; ж)ДНФ, КНФ.

11. а) и б).

Лабораторные работы проводятся с помощью обучающей компьютерной системы "Теория графов". В лабораторных работах используются следующие разделы этой системы: "Основные понятия теории графов", "Экстремальные пути в графах".

Чтобы приступить к выполнению лабораторной работы необходимо запустить систему с помощью файла run.bat; выбрать в главном меню пункт "Обучающие программы"; указать раздел; выбрать пункт "Упражнения".

В процессе работы возможно обращение к теоретическому материалу, используя соответствующие пункты меню, а также алфавитный указатель.