1.Для каждого из приведенных ниже множеств используйте диаграммы Венна для двух множеств и заштрихуйте те ее части , которые изображают заданные множества (A ) )) Рассмотрим множества A={ Выпишите множества A A , A .
2.Построить на координатной плоскости отношения r и s , если r R , r={(x,y) : x2+y2 }, s R , s={(x ,y) : y . Найти отношения, r ⃘s, r ⃘ . Построить указанные отношения на координатной плоскости.
3. Существует ли пример симметричного и транзитивного, но не рефлексивного отношения. Если существует, то привести пример.
4.Найдите код Прюфера дерева
5. Найти решение рекуррентного соотношения = +3 +1, n>2, =2 , =6 .
Стоит рассмотреть матрицы смежности графов, поскольку из каждой вершины каждого графа выходит три ребра.
Рассмотрим матрицы:
Для первого графа:
1
2
3
4
1
0
1
1
1
2
1
0
1
1
3
1
1
0
1
4
1
1
1
0
Для второго графа:
a
b
c
d
a
0
1
1
1
b
1
0
1
1
c
1
1
0
1
d
1
1
1
0
Матрицы равны => графы А и В изоморфны.
7. Определить являются ли данные последовательности графическими. В случае положительного ответа нарисовать соответствующий граф (4,4,4,4,3,3,2,2,2) , (4,4,4,3,3,2,1 ) .
9. Доказать, что всякое дерево с n>1 вершинами есть двудольный граф . Двудольный граф - это граф, множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет вершину из одной части с какой-то вершиной другой части, то есть не существует рёбер между вершинами одной и той же части графа. Теорема о двудольном графе – двудольный граф тогда и только тогда, когда все его простые циклы имеют четную длину. Доказательство:
1. Раскрасим вершины графа в два цвета.
2. Возьмем какой-то простой цикл.
3. Все вершины разбились на пары => граф четной длины.
10. Определите хроматическое число графа Хром. Число = 2 b
a c
h d
g e
f
12. По каналу связи передаются шесть различных символов . Между этими символами нужно поместить 12 пробелов, по крайней мере по два пробела между каждой парой символов . Сколько имеется различных способов расположить символы и пробелы?
