Федеральное агентство по образованию
Пермский государственный технический университет
Кафедра информационных технологий и автоматизированных систем
Контрольная работа
по дисциплине
Математическая логика
Вариант №3
Выполнил:студентгр.АСУз-05-1уск
Мартемьянов С.Н.
Проверил: Файзрахманов Р.А.
Пермь 2007
1. Комбинаторика
2.2 Бросают три игральные кости (с шесть гранями каждая). Сколькими способами они могут упасть так, что либо все оказавшиеся вверху грани одинаковы, либо все попарно различны?
6 вариантов, когда все одинаковы и 6*5*4=120, когда все попарно различны
Итого: 126 вариантов
6.5. Предложить алгоритм бесповторного перечисления всех (n,n) перестановок чисел 1,2,…,n.
Может быть n вариантов первой цифры, n-1 второй и т.д. Следовательно число вариантов равно
1*2*3*…*n=n!
2. Графы
3. Записать следующие графы матрицами инцидентности и смежности.(Рис.3.).
Х3
а) б) в)
|
|
Х1 |
Х2 |
Х3 |
Х4 |
Х5 |
|
Х1 |
0 |
1 |
0 |
0 |
0 |
|
Х2 |
1 |
0 |
1 |
0 |
0 |
|
Х3 |
0 |
1 |
0 |
1 |
0 |
|
Х4 |
0 |
0 |
1 |
0 |
1 |
|
Х5 |
0 |
0 |
0 |
1 |
0 |
|
|
Е1 |
Е2 |
Е3 |
Е4 |
|
Х1 |
1 |
0 |
0 |
0 |
|
Х2 |
1 |
0 |
0 |
1 |
|
Х3 |
0 |
0 |
1 |
1 |
|
Х4 |
0 |
1 |
1 |
0 |
|
Х5 |
0 |
1 |
0 |
0 |
б)матрица инцидентности матрица смежности
|
|
Х1 |
Х2 |
Х3 |
Х4 |
Х5 |
|
Х1 |
0 |
1 |
0 |
0 |
0 |
|
Х2 |
1 |
0 |
1 |
0 |
0 |
|
Х3 |
0 |
1 |
0 |
1 |
0 |
|
Х4 |
0 |
0 |
1 |
0 |
1 |
|
Х5 |
0 |
0 |
0 |
1 |
0 |
|
|
Е1 |
Е2 |
Е3 |
Е4 |
|
Х1 |
1 |
0 |
0 |
0 |
|
Х2 |
1 |
1 |
0 |
0 |
|
Х3 |
0 |
1 |
1 |
0 |
|
Х4 |
0 |
0 |
1 |
1 |
|
Х5 |
0 |
0 |
0 |
1 |
в)матрица инцидентности матрица смежности
|
|
Х1 |
Х2 |
Х3 |
Х4 |
Х5 |
|
Х1 |
0 |
1 |
0 |
0 |
0 |
|
Х2 |
0 |
0 |
0 |
0 |
0 |
|
Х3 |
0 |
1 |
0 |
0 |
0 |
|
Х4 |
0 |
0 |
1 |
0 |
0 |
|
Х5 |
0 |
0 |
0 |
1 |
0 |
|
|
Е1 |
Е2 |
Е3 |
Е4 |
|
Х1 |
-1 |
0 |
0 |
0 |
|
Х2 |
+1 |
+1 |
0 |
0 |
|
Х3 |
0 |
-1 |
+1 |
0 |
|
Х4 |
0 |
0 |
-1 |
+1 |
|
Х5 |
0 |
0 |
0 |
-1 |
8. Даны графы типа дерева на рис.7. Для каждого графа выполнить следующее задание. Сколько вершин максимального типа имеется в данном графе? Какое цикломатическое число графа? Чему равно цикломатическое число графа G', являющегося лесом и представленного двумя одинаковыми деревьями рассматриваемого типа графа? Построить ориентированное дерево с корнем 0, являющимся вершиной максимального типа.
Рис. 7
Цикломатическое число v(G)= m-n+1
m- кол-во ребер
n- кол-во вершин
G1)v(G)=20-20+1 =1
G2)v(G)=18-19+1 =0 => G2 уже дерево
G3)v(G)=18-19+1 =0 => G3 уже дерево
Кол-во вершин максимального типа:
G1)7
G2)4
G3)2
Цикломатическое число леса:
G1)1*2=2
G2)0*2=0
G3)0*2=0
Ориентированные деревья:
